EncapsulateWhenConditions scales as O(N^3) in models where a when clause is triggered by a large vector of conditions

[Francesco Casella]

Consider the following model from the ScalableTestSuite

model ManyEventsManyConditions "Model with many events in when clauses and a when clause with many triggering conditions"
  parameter Integer N;
  Real x[N](each start = 0, each fixed = true);
  Boolean e[N](each start = false, each fixed = true);
  Integer v(start = 0, fixed = true);
equation
  for i in 1:N loop
    der(x[i]) = 1/i;
    when x[i] > 1 then
      e[i] = true;
    end when;
  end for;
  when e then
    v = pre(v) + 1;
  end when;
end ManyEventsManyConditions;

The last when clause is triggered by a boolean array e with N elements in it.

This is the performance of preOpt encapsulateWhenConditions on my PC

N	Time [s]
1000	0.8
2000	6.3
4000	54.8

which scales neatly as O(N³)

Is this really necessary, or is it just the result of a (very) inefficient algorithm?

[Lennart Ochel]

I guess that this is because of an inefficient implementation.

[Francesco Casella]

For models with a few event-triggering conditions, no big deal. However, the power network models we are considering now feature up to 10⁴ when clauses and event generation functions, and eventually we might reach numbers in excess of 10⁵.

The structure of event handling in these models is exactly the same as in this test case: many independent when clauses triggering a change of a boolean variable if some threshold is crossed, plus one master when condition that is triggered whenever any of those individual booleans changes.

[Martin Sjölund]

I believe I have been able to fix the scaling of encapsulateWhenConditions, but findZeroCrossings is very similar and very slow (at least locally; let's see if the test suite passes). It might have to do with the fact that I could not change relations to be a set since the current code depends on duplicates being added. Or the PR that was not pushed yet.

N	Time encapsulate [s]	Time findZC [s]
1000	0.026	1.6
2000	0.054	7.366
4000	0.14	31.03

I changed the representation of sets to use... AvlSetInt instead of list<Integer>.

Note: This fixes calculation of the incidence matrix, which is what seems to be the slowest part of encapsulating the when conditions. See ​https://github.com/OpenModelica/OMCompiler/pull/1034

[Martin Sjölund]

With ​PR 1033, the findZC is improved:

N	Time encapsulate [s]	Time findZC [s]
1000	0.024	0.61
2000	0.054	2.411
4000	0.14	10.28

Still bad scaling on findZC, but it got faster. I expected O(N*log(N)), but perhaps there is some part in there that is still quadratic in time (the relations perhaps).

[Martin Sjölund]

@lochel: Any idea why the incidence matrix gives different results if the order of entries in the incidence matrix changes? Is the order used somewhere? You can see the difference by simply changing:

Compiler/BackEnd/BackendDAEUtil.mo

@@ -2425 +2425 @@
       then
         fail();
   end matchcontinue;
-  outIntegerLst := listAppend(whenIntegerLst, outIntegerLst);
+  outIntegerLst := List.sort(listAppend(whenIntegerLst, outIntegerLst), intGe);
 end incidenceRow;
 
 protected function incidenceRowLst

And then running testsuite/simulation/modelica/others/Pendulum.mos.

​https://test.openmodelica.org/hudson/view/Linux/job/OpenModelica_TEST_PULL_REQUEST/3048 gave 62 failures. Some of them were just changing how many SCCs a model is reported to have (which should be fine). But some models fail to solve properly, or reach the time limit (HeatExchanger).

[Martin Sjölund]

The ​Hudson result with the above change shows 71 failures. So again, why does the result depend on the order of the elements in the incidence matrix? I could of course create an ordered set, but I am unsure why we should need a new (slower) set type added.

[Lennart Ochel]

Some modules which depend on heuristics may return different results, e.g. variable order may change which effects numerical solvers. I will have a quick look tomorrow.

[Francesco Casella]

If that is the case, then a change breaking some tests in the testsuite is just bad luck, but it shouldn't necessarily be rejected. To my understanding, the original order is a random one, and is good as any other one in principle, barring bad luck and Murphy's law.

[Francesco Casella]

The problem is addressed by ​PR 1034. @lochel should be able to look into it by end of October

[Francesco Casella]

After pushing ​PR 1034, this is the performance of preOpt encapsulateWhenConditions on the ManyEventsManyConditions models, compiled on libraries.openmodelica.org

N	Time [s]
1000	0.023
2000	0.075
4000	0.23
8000	0.40

which is roughly linear. Mission accomplished :)

I changed the milestone to 1.12.0, as PR1034 currently breaks some MSL examples due to issues with initialization of systems with dynamic state selection, see #4143, so we can't include it in 1.11.0