generate::optimize
-- generate
optimized codegenerate::optimize
(..)
returns a sequence
of equations representing an ``optimized computation sequence'' for the
input expression. Each equation in the sequence corresponds to an
assignment of a subexpression of the input expression to a ``temporary
variable''. Common subexpressions are computed only once, thus reducing
the total operation count.
generate::optimize(r)
r |
- | an expression, array or list of equations |
a list of equations.
generate::Macrofort::setOptimizedOption
,
generate::Macrofort::genFor
generate::optimize
represents a
``computation sequence'', i.e., a list of equations representing an
optimized version of the input. Common intermediates are identified by
the optimizer and ``stored'' in temporary variables t1
,
t2
etc. Each equation in the sequence corresponds to an
assignment to such a variable.
The number of operations, namely additions (or subtractions),
multiplications (or divisions) and in particular functions calls of the
output is usually lower than the number of such operations of the
input. This facility is useful for code generation (see
generate::Macrofort::setOptimizedOption
).
In this first example, we show the effects of optimization for a simple expression:
>> generate::optimize(cos(x^2) + x^2*sin(x^2) + x^4)
2 2 [t2 = x , t1 = cos(t2) + t2 sin(t2) + t2 ]
The ``blind'' computation of the input expression
requires 7 multiplications, 2 additions and 2 function calls. The
optimized version introduces a ``temporary variable'' t2
storing the subexpression x^2
that is used to compute the
final result t1
. This reduces the total cost to 3
multiplications, 2 additions and 2 function calls, albeit using 1 extra
assignment to the temporary variable t2
.
Here we repeat the exercise of the first example but with an array of expressions:
>> generate::optimize(array(1..2, 1..2, [[x^3, x^2],[x^2, x^4]]))
-- +- -+ -- | | x t4, t4 | | | 2 | | | | t4 = x , t3 = | 2 | | | | t4, t4 | | -- +- -+ --
The original input requires 6 multiplications. The optimized version needs only 3 multiplications and 1 extra assignment.
We optimize a list of equations representing a
computation sequence for 3 variables t
, C[1]
,
C[2]
:
>> generate::optimize([t = u, C[1] = t*(u - w)^2, C[2] = 2*(u - w)^3])
2 [t = u, t5 = u - w, t6 = t5 , C[1] = t t6, C[2] = 2 t5 t6]
The original computation requires 5 multiplications and 2 subtractions. The optimized version needs 4 multiplications and 1 subtraction.
Note that since these examples involve small expressions, the
computational savings are slight. In the case of very large
expressions, optimization can yield a considerable dividend (c.f. the
last example in the help-pages of generate::Macrofort::genFor
for a real application of this implementation).
It should be understood that ``optimization'' is meant in the sense
of compiler optimization. The end-result rarely corresponds to the
absolute irreducible minimum number of operations - or as in the case
of FORTRAN code generation, the absolute minimum of floating-point
operations (FLOPS). Achieving this limit can be extremely difficult if
not impossible especially for large computational sequences.
Nonetheless, in a number of real-life instances, MuPAD's
optimizer can yield a very useful result. Additionally, MuPAD
provides symbolic manipulation tools such as factor
which
can yield additional reduction in operation costs.
In many cases of optimization, it is most often a matter of how best to pose the problem so as to fully exploit every possible symmetry or useful natural property of the given problem.