#5110 closed enhancement (fixed)
Inefficient translation of models with arrays
Reported by: | rfranke | Owned by: | rfranke |
---|---|---|---|
Priority: | critical | Milestone: | 1.14.0 |
Component: | Backend | Version: | |
Keywords: | Cc: | wbraun, casella, perost, Karim.Abdelhak |
Description
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.
Change History (22)
comment:1 Changed 6 years ago by casella
- Cc perost added
comment:2 Changed 6 years ago by 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.
comment:3 Changed 6 years ago by 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.
comment:4 Changed 6 years ago by rfranke
-d=newInst improves things, except for Clock and previous. Could those two operators and firstTick be implemented in the new frontend?
comment:5 Changed 6 years ago by 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)).
comment:6 Changed 6 years ago by 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;
comment:7 Changed 6 years ago by 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;
comment:8 follow-up: ↓ 11 Changed 6 years ago by 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?
comment:9 Changed 6 years ago by 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.
comment:10 Changed 6 years ago by 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;
comment:11 in reply to: ↑ 8 Changed 6 years ago by 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
comment:12 Changed 6 years ago by 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.
comment:13 Changed 6 years ago by 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:
comment:14 Changed 6 years ago by rfranke
- Owner changed from lochel to rfranke
- Status changed from new to accepted
comment:15 Changed 6 years ago by 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.
comment:16 Changed 6 years ago by 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.
comment:17 Changed 6 years ago by 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.
comment:18 Changed 6 years ago by rfranke
- Cc kabdelhak added
comment:19 Changed 6 years ago by adrpo
- Cc Karim.Abdelhak added; kabdelhak removed
comment:20 Changed 6 years ago by 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 :-(
comment:21 Changed 6 years ago by rfranke
- Resolution set to fixed
- Status changed from accepted to closed
PR2698 (https://github.com/OpenModelica/OMCompiler/pull/2698) fixes backend errors with BLT analysis. Moreover it adds support for arrays of clocked continuous states.
comment:22 Changed 6 years ago by 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.
@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