## `generate::optimize` -- generate optimized code

#### Introduction

`generate::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.

#### Call(s)

`generate::optimize(r)`

#### Parameters

`r` | - | an expression, array or list of equations

#### Returns

a list of equations.

#### Related Functions

`generate::Macrofort::setOptimizedOption`, `generate::Macrofort::genFor`

#### Details

- The output from `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`).

#### Example 1

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`.

#### Example 2

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.

#### Example 3

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).

#### Background

- A number of FORTRAN compilers provide optimizers. However, they use algorithms of complexity O(n ^2) and O(n ^3) where n is the size of the input expressions. For large amounts of code, these algorithms may ``break''. MuPAD provides a reasonably good scalar (as in non-vectorized and non-parallelized) optimizer which is limited to common subexpression optimization and using binary powering for integer powers. It uses hashing of expressions so that given a sub-expression, it can determine in constant time if this subexpression has already occurred. This results in an overall efficiency which is of lower complexity namely, O(n) i.e. linear in the size of the input expressions to be optimized, Hence overall efficiency is not compromised by very large expressions. This does mean that not all possible optimizations are made but nonetheless a number of reductions including the exploitation of some symmetries are possible.

  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.

- Reference: T.C. Scott, I.P. Grant, M.B. Monagan and V.R. Saunders, MapleTech, 4, no. 2, pp. 15-24, (1997).

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000