Inefficient translation of models with arrays

[rfranke]

See the following test example, for which OpenModelica generates inefficient code. Increasing n leads to huge increases in memory and CPU usage, until OpenModelica is not able to translate the model anymore.

package VectorTest
  constant Integer n = 10;

  function mysum
    input Real[:] u;
    output Real y;
  algorithm
    y := sum(u);
  end mysum;

  function myfor
    input Real[:] u;
    input Real[size(u, 1)] previous_x;
    output Real[size(u, 1)] x;
  algorithm
    for i in 1:size(u,1) loop
      x[i] := previous_x[i] + u[i];
    end for;
  end myfor;

  model m
    input Real[n] u(each start = 1);
    Real[size(u,1)] x1, x2;
    output Real y0, y1, y2;
  equation
    when Clock() then
      for i in 1:size(u,1) loop
        x1[i] = previous(x1[i]) + u[i];
      end for;
      x2 = myfor(u, previous(x2));
    end when;
    y0 = sum(u);
    y1 = mysum(u);
    y2 = mysum(x2);
  end m;

end VectorTest;

The bad code for y0 is:

SIMPLE_ASSIGN
y0 = u[1] + u[2] + u[3] + u[4] + u[5] + u[6] + u[7] + u[8] + u[9] + u[10]

Better code preserving arrays and for loops is generated when using functions (sometimes it's tricky to really get such code though):

SIMPLE_ASSIGN
y1 = VectorTest.mysum(u)

Unfortunately not in all cases:

ARRAY_CALL_ASSIGN
x2 = VectorTest.myfor(u, {previous(x2[1]), previous(x2[2]), previous(x2[3]), previous(x2[4]), previous(x2[5]), previous(x2[6]), previous(x2[7]), previous(x2[8]), previous(x2[9]), previous(x2[10])})

As a short term solution, it appears doable to place all array equations in functions. But OpenModelica must not roll out arrays when calling these functions -- see equation for x2 above.

In principle, a model can be formulated with functions and sorted equations, so that the front- and backend could just pass it through to the code generation. This would be a starting point for efficient code generation for models with arrays.

In the example at hand, at least the previous and maybe also the sum operator should preserve arrays.

[casella]

@rfranke, did you try what happens with -d=newInst?

Also, please check with -d=optdaedump what is the place where the unrolling is performed. Is it front-end or back-end

[adrpo]

@casella: I tried myself with -d=newInst but we don't have support for synch. features such as Clock yet, but it should be easy to add.

[perost]

The NF generates the same equation for y0, i.e. it also expands the sum call. This is because the backend expects it to do so, see e.g. #4864, but is not necessary for the frontend itself.

[rfranke]

-d=newInst improves things, except for Clock and previous. Could those two operators and firstTick be implemented in the new frontend?

[rfranke]

PR ​https://github.com/OpenModelica/OMCompiler/pull/2644/ adapts the generation of equations

$CLKPRE.x = x

in SimCodeUtil to consider arrays.

Several tests fail for the C runtime

​https://test.openmodelica.org/hudson/job/OpenModelica_TEST_PULL_REQUEST/6007/#showFailuresLink

Can someone check if this can be fixed for the C runtime?

If not, then I had to move the vectorization down from SimCode to the Cpp template.

But actually I'd like to move it up from SimCode to SynchronousFeatures and replace all previous(x) with $CLKPRE.x there, so that collapseArrayExpressions would work for function calls f(previous(x)).

[adrpo]

This is the result I get after adding Clock() to the NF.
The previous is part of the for loop so is expanded.
The sum is expanded, but I guess we can disable that on some flag.
I will add support for Clock(interval) as well, then I will commit my stuff.

adrpo33@ida-0030 MINGW64 /c/home/adrpo33/dev/OMTesting/nf
$ time ~/dev/OpenModelica/build/bin/omc +d=newInst,-nfScalarize +std=3.3 vt.mos

function VectorTest.myfor
  input Real[:] u;
  input Real[size(u, 1)] previous_x;
  output Real[size(u, 1)] x;
algorithm
  for i in 1:size(u, 1) loop
    x[i] := previous_x[i] + u[i];
  end for;
end VectorTest.myfor;

function VectorTest.mysum
  input Real[:] u;
  output Real y;
algorithm
  y := sum(u);
end VectorTest.mysum;

class VectorTest.m
  input Real[10] u;
  Real[10] x1;
  Real[10] x2;
  output Real y0;
  output Real y1;
  output Real y2;
equation
  when Clock() then
    x1[1] = previous(x1[1]) + u[1];
    x1[2] = previous(x1[2]) + u[2];
    x1[3] = previous(x1[3]) + u[3];
    x1[4] = previous(x1[4]) + u[4];
    x1[5] = previous(x1[5]) + u[5];
    x1[6] = previous(x1[6]) + u[6];
    x1[7] = previous(x1[7]) + u[7];
    x1[8] = previous(x1[8]) + u[8];
    x1[9] = previous(x1[9]) + u[9];
    x1[10] = previous(x1[10]) + u[10];
    x2 = VectorTest.myfor(u, previous(x2));
  end when;
  y0 = u[1] + u[2] + u[3] + u[4] + u[5] + u[6] + u[7] + u[8] + u[9] + u[10];
  y1 = VectorTest.mysum(u);
  y2 = VectorTest.mysum(x2);
end VectorTest.m;

[adrpo]

After 09518b/OMCompiler we get with -d=newInst,-nfScalarize --std=3.3

function VectorTest.myfor
  input Real[:] u;
  input Real[size(u, 1)] previous_x;
  output Real[size(u, 1)] x;
algorithm
  for i in 1:size(u, 1) loop
    x[i] := previous_x[i] + u[i];
  end for;
end VectorTest.myfor;

function VectorTest.mysum
  input Real[:] u;
  output Real y;
algorithm
  y := sum(u);
end VectorTest.mysum;

class VectorTest.m
  input Real[10] u;
  Real[10] x1;
  Real[10] x2;
  output Real y0;
  output Real y1;
  output Real y2;
equation
  when Clock() then
    x1[1] = previous(x1[1]) + u[1];
    x1[2] = previous(x1[2]) + u[2];
    x1[3] = previous(x1[3]) + u[3];
    x1[4] = previous(x1[4]) + u[4];
    x1[5] = previous(x1[5]) + u[5];
    x1[6] = previous(x1[6]) + u[6];
    x1[7] = previous(x1[7]) + u[7];
    x1[8] = previous(x1[8]) + u[8];
    x1[9] = previous(x1[9]) + u[9];
    x1[10] = previous(x1[10]) + u[10];
    x2 = VectorTest.myfor(u, previous(x2));
  end when;
  y0 = sum(u);
  y1 = VectorTest.mysum(u);
  y2 = VectorTest.mysum(x2);
end VectorTest.m;

[rfranke]

This looks good, also that you don't expand sum() anymore. I think it's fine that the for loop is rolled out. Modelers should use arrays in the first place, including also arrays of scalar component models, and OpenModelica should keep these arrays as much as possible -- even up to the export of simulators and fmus.

I must check how the current backend and code generation process such array models. Will you merge your changes?

How would you implement firstTick() in the new frontend for models like:

  model foo
    input Real u(start = 1);
    Real x1(start=1), x2(start=2);
  equation
    when Clock() then
      x1 = if firstTick() then previous(x1) else previous(x1) + u;
      x2 = if firstTick(u) then previous(x2) else previous(x2) + u;
    end when;
  end foo;

Would it also go into Compiler/NFFrontEnd/NFBuiltinCall.mo?

[adrpo]

@rfranke: is will add all the needed synchronous features, starting with firstTick.
I'm not sure where it will go as this function/builtin operator is weird, it takes u but the specification says nothing about what u is. I will check how is done in the current front-end.
Let me know in #5127 which functions should I add first.

[rfranke]

The u argument is just sugar for firstTick, because all variables of a clocked partition belong to the same clock. firstTick knows that clock also without u.

The following model is wrong because firstTick(u1) accesses u1 that blongs to another clock. This error would be detected during clock partitioning in the backend (SynchronousFeatures.mo).

  model bar
    input Real u1, u2;
    Real x1(start=1), x2(start=2);
  equation
    when Clock(1.0) then
      x1 = if firstTick() then previous(x1) else previous(x1) + u1;
    end when;
    when Clock(2.0) then
      x2 = if firstTick(u1) then previous(x2) else previous(x2) + u2;
    end when;
  end bar;

[casella]

Replying to rfranke:

This looks good, also that you don't expand sum() anymore. I think it's fine that the for loop is rolled out. Modelers should use arrays in the first place, including also arrays of scalar component models, and OpenModelica should keep these arrays as much as possible -- even up to the export of simulators and fmus.

See also the discussion in #3678

[adrpo]

@rfranke: I know, but actually it seems that firstTick is polymorphic with regards to the type of the first argument. I doesn't need to be Real. I found a way to specify firstTick and interval in NFModelicaBuiltin.mo so no actual compiler changes were necessary for these, only for sample. See #5127.

[rfranke]

´-d=newInst,-nfScalarize --std=3.3´ looks really good for the frontend now. A lot of work remains for the backend:

[1] 07:40:39 Symbolic Error
Too many equations, over-determined system. The model has 15 equation(s) and 6 variable(s).

[2] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 2 (size: 1) x1[10] = previous(x1[10]) + u[10] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[3] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 3 (size: 1) x1[9] = previous(x1[9]) + u[9] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[4] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 4 (size: 1) x1[8] = previous(x1[8]) + u[8] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[5] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 5 (size: 1) x1[7] = previous(x1[7]) + u[7] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[6] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 6 (size: 1) x1[6] = previous(x1[6]) + u[6] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[7] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 7 (size: 1) x1[5] = previous(x1[5]) + u[5] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[8] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 8 (size: 1) x1[4] = previous(x1[4]) + u[4] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[9] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 9 (size: 1) x1[3] = previous(x1[3]) + u[3] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[10] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 10 (size: 1) x1[2] = previous(x1[2]) + u[2] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[11] 07:40:39 Symbolic Warning
[VectorTest: 28:9-28:39]: Equation 11 (size: 1) x1[1] = previous(x1[1]) + u[1] is not big enough to solve for enough variables.
  Remaining unsolved variables are: 
  Already solved: 
  Equations used to solve those variables:

[12] 07:40:39 Symbolic Warning
[VectorTest: 23:5-23:27]: Variable x1 does not have any remaining equation to be solved in.
  The original equations were:

[rfranke]

To summarize the status:

PR ​​https://github.com/OpenModelica/OMCompiler/pull/2644/ attempts to collapse auto generated assignments of the form previous(x) := x instead of previous(x[1]) := x[1]; previous(x[2]) := x[2]; .... It causes a couple of failed tests with the C runtime that does not appear to treat arrays yet, see ​https://test.openmodelica.org/hudson//job/OpenModelica_TEST_PULL_REQUEST/6007/. This PR can be discarded if x is treated as array thoughout the translation process (see below).

1fd1dd9e67/OMCompiler and 66ceece9bfae/OMCompiler extend collapseArrayExpressions to also cover arrays with calls, like der(x) instead of {der(x[1]), der({x[2]), ...} for the Cpp runtime only.

5b5cfe87b3fb/OMCompiler adds the debug flag disableFMIDependency that speeds up the translation of large models tremendously if no FMI dependecies/Jacobian are needed.

The omc debug flags newInst and -nfScalarize let the frontend keep array variables and array expressions. The way forward is to extend the backend to also treat arrays; at least for simple models initially.

[rfranke]

PR2679 (​https://github.com/OpenModelica/OMCompiler/pull/2679) treats simple models for simulation and FMI export preserving arrays with

omc -d=newInst,-nfScalarize --std=3.3 --simCodeTarget=Cpp

model m2
  input Real[10] u(start = 1:10);
  Real[size(u, 1)] x(each start = 1);
  output Real y;
equation
  when Clock(0.1) then
    x = if firstTick(u) then previous(x) else previous(x) + u;
  end when;
  y = sum(x);
end m2;

Most effort was needed to still roll out arrays in model description xml files.

[rfranke]

With PR2685 ​https://github.com/OpenModelica/OMCompiler/pull/2685
omc -d=newInst,-nfScalarize produces:

class m
  input Real[10] u(start = 1.0);
  Real[10] x1;
  Real[10] x2;
  output Real y0;
  output Real y1;
  output Real y2;
equation
  when Clock() then
    for i in 1:10 loop
      x1[i] = previous(x1[i]) + u[i];
    end for;
    x2 = myfor(u, previous(x2));
  end when;
  y0 = sum(u);
  y1 = mysum(u);
  y2 = mysum(x2);
end m;

For loops appear attractive for arrays of components, see #5144.

[rfranke]

PR2692 ​https://github.com/OpenModelica/OMCompiler/pull/2692
activates for loops in the backend and Cpp code generation. The following model simulates with
omc --std=3.3 -d=newInst,-nfScalarize --postOptModules-=collapseArrayExpressions --simCodeTarget=Cpp. See the respective extension to the testsuite.

The model treats arrays in three different ways: for-equation, function call and array-equation:

model ArrayEquationsTest
  function myfor
    input Real[:] u;
    input Real[size(u, 1)] previous_x;
    input Boolean isFirstTick;
    output Real[size(u, 1)] x;
  algorithm
    for i in 1:size(u,1) loop
      x[i] := if isFirstTick then previous_x[i] else previous_x[i] + u[i];
    end for;
  end myfor;

  parameter Integer n = 10;
  input Real[n] u(start = 1:n);
  Real[n] x1(each start = 1);
  Real[n] x2(each start = 2);
  Real[n] x3(each start = 3);
  output Real y1, y2, y3;
equation
  when Clock(0.1) then
    // for eqation
    for i in 1:n loop
      x1[i] = if firstTick(x1[i]) then previous(x1[i]) else previous(x1[i]) + u[i];
    end for;
    // function with for loop
    x2 = myfor(u, previous(x2), firstTick());
    // array equation
    x3 = if firstTick(x3) then previous(x3) else previous(x3) + u;
  end when;
  y1 = sum(x1);
  y2 = sum(x2);
  y3 = sum(x3);
end ArrayEquationsTest;

By chance (and a little tweak in BackendEquation.equationSize) the parameter n propagates up to the for loop in the Cpp code and the FMI model description file. The sizes of the arrays are fixed though :-(

[rfranke]

PR2698 (​https://github.com/OpenModelica/OMCompiler/pull/2698) fixes backend errors with BLT analysis. Moreover it adds support for arrays of clocked continuous states.

[rfranke]

PR2721 (​https://github.com/OpenModelica/OMCompiler/pull/2721) evaluates the structural parameter n of the above model. This is needed because a Modelica constant

  constant Integer n=10;

would otherwise stay in the for equation as weil, despite of being unknown during code generation.