findZeroCrossings scales as O(N^2)

[Francesco Casella]

As demonstrated by the BreakerCircuit models of the ScalableTestSuite, the findZeroCrossing function scales as O(N²). It is currently the biggest bottleneck in our large network models, when including line breakers and current protections, which generate up to 40000 zero-crossing functions.

@hkiel reports that

findZeroCrossings uses lots of listAppend() in wrong order (mostly appending a single element). Either someone can switch the code to build the lists in reverse order (does order matter annyhow?) or use the DoubleEndedList. I'm currently too busy to do such a huge task.

In fact the order doesn't matter at all, so I guess DoubleEndedList would do the job.

[Martin Sjölund]

I also guessed the order doesn't matter, but it breaks the testsuite if I change the ordering :(

[Francesco Casella]

Probably it breaks the testsuite because there is some place where an ordered list of crossing functions is compared with a reference one, and as the two don't match, an error is generated.

I can't really see any reason why there should be a preferred ordering for these functions and what could be the ordering criterion.

[Martin Sjölund]

It broke the testsuite because the relations have indexes in them pointing to the correct zero-crossing. So if you generate them in the wrong order, the references become invalid and you get the wrong result.

[Francesco Casella]

I have added some structurally very simple test cases to the ScalableTestSuite. Please check the performance of the ScalableTestSuite.Elementary.WhenEvents.ScaledExperiments.ManyEvents_N_XXX models:

    model ManyEvents "Model with many events in when clauses"
      parameter Integer N = 5;
      Real x[N](each start = 0, each fixed = true);
      Boolean e[N](each start = false, each 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;
    end ManyEvents;

On my PC, I get the following times for running findZeroCrossings

N	Time[s]
1000	0.25
2000	1.25
4000	8.08

corresponding to O(N^2.5). Maybe this very essential test case helps sorting out the issue...

[Francesco Casella]

One way to make this manageable for large N could be allowing to optionally turn off some optimizations. For example, if we know a priori there are no duplicate conditions in the model, we could avoid looking for them in the backend.

[Martin Sjölund]

Ticket retargeted after milestone closed

[Francesco Casella]

Status update, using results obtained today with master run on libraries.openmodelica.org

N	Time[s]	Memory [GB]
1000	0.7	0.18
2000	3.9	0.68
4000	15.4	2.68
8000	63.3	10.61

Time grows as O(N²) for N >= 2000. No idea why it should be significantly faster than that for N = 1000.

Memory allocation also grows quadratically.

[Francesco Casella]

The situation is still unchanged. Any chance to fix this?

[Francesco Casella]

Milestone moved to 1.13.0 due to 1.12.0 already being released.

[Francesco Casella]

@sjoelund.se could you have another look at this? This is the last remaining major scaling issue with large models that cannot be circumvented by using --daeMode

BTW, the compilation of the generated code corresponding to the event detection is also very expensive, although it scales linearly with model size. Looking at the ​Hudson report, it takes between 15 and 25 ms per single event to compile the C code, which is a lot of time and basically makes it impossible to go above 10000 event generating functions. We need a lot more than that to manage realistic transmission grid models. Any suggestion how to make this substantially faster would be welcome.

Thanks!

[Willi Braun]

I think for an efficient findZeroCrossing module we will need to redesign the Expressions that are used for zero-crossings. Basically, by introducing an separated Expression for ZeroCrossing would make things much easier, as far as I see, therefore I started ​PR2061.

[Francesco Casella]

Rescheduled to 1.14.0 after 1.13.0 releasee

[Francesco Casella]

Releasing 1.14.0 which is stable and has many improvements w.r.t. 1.13.2. This issue is rescheduled to 1.16.0

[Francesco Casella]

Retargeted to 1.17.0 after 1.16.0 release

[Francesco Casella]

Retargeted to 1.18.0 because of 1.17.0 timed release.

[Francesco Casella]

Ticket retargeted after milestone closed