3 Cost Index and CR simplifications

In this section we examine the major CR simplification rules w.r.t. their effect on the CI of the transformed CR expression.

Table 1 lists the major rules for simplifying multi - dimensional CR expressions. Most of these are generalizations of the rules given in [#!us:issac94!#,#!me:hisc!#,#!zima:issac95!#] from one- or two-dimensional CR expressions to multi - dimensional CR expressions. For a more detailed description and a proofs of these rules, see [#!me:thesis!#].

The left hand sides (LHS) of the simplification rules are given in column 2 and the respective right hand sides (RHS) are given in column 3. For reasons of clarity, the trivial simplification rules for general CR expressions based on the ring axioms are not shown.

In general, the difference CI(LHS) - CI(RHS) is dependent on the complexity of the regular grid, on the weights of the operations involved, and on a chosen variable ordering. Column 4 marks the cases where CI(LHS)-CI(RHS) > 0 independently of all of these factors (the symbol $\wr$ is used to mark the rules where CI(LHS)-CI(RHS) > 0 can not be decided a priori). Column 5 shows CI(LHS) - CI(RHS) of one - dimensional CR expressions for which this difference depends at most on the weights of the operations involved.

For one - dimensional CRs, the application of a simplification rule is always unique in the sense that the same rule can not be applied to the same CR expression and yield different simplification results. However, this is, in general, not the case for multi - dimensional CRs. Let us illustrate this by an example: Let $\Phi = \{\varphi_0 ,\, {\mbox{\texttt{+}}}\, ,\varphi_1\}_{x}$ and $\Psi = \{\psi_0 ,\, {\mbox{\texttt{+}}}\, , \psi_1\}_{y}$ and consider $\Phi \cdot \Psi$. Then by (6), i.e., by

$$\{\varphi_0 ,\, {\mbox{\texttt{+}}}\, ,\ldots ,\, {\mbox{\tex... ...ldots ,\, {\mbox{\texttt{+}}}\, , \varphi_l\cdot\psi \}_{x_k}$$

with $x_k \not\in X(\psi)$, we can simplify $\Phi \cdot \Psi$ to

$$\Lambda = \{\{\varphi_0\psi_0 ,\, {\mbox{\texttt{+}}}\, ,\var... ..._0 ,\, {\mbox{\texttt{+}}}\, , \varphi_1 \psi_1 \}_{y} \}_{x},$$

and alternatively to

$$\Lambda^\prime = \{\{\varphi_0\psi_0 ,\, {\mbox{\texttt{+}}}\... ..._1 ,\, {\mbox{\texttt{+}}}\, ,\varphi_1 \psi_1 \}_{x} \}_{y},$$

where

$$CI(\Lambda) = 1 + \frac{2}{m_x} \qquad CI(\Lambda^\prime) = 1 + \frac{2}{m_y}.$$

Hence, if m_x = 1000 and m_y=10 then an evaluation of $\Lambda$ requires 1980 more additions than an evaluation of $\Lambda^\prime$.

More generally, the freedom of choosing a variable ordering implies an additional degree of freedom in applying certain simplification rules which consequently has an impact on the CI of the simplified CR expression. Column 6 of table 1 marks all simplification rules to which this applies with the symbol $\surd$.

                 

Figure 1: Properties of CR simplification rules