next up previous
Next: Time-Step Calculations and Iteration Up: Machine Balance, Compute Balance, Previous: Loop Skewing and Tiling

Describing Transformations

The transformations used here can be described concisely in the framework of Kelly and Pugh [22]. In this framework, each execution of each statement is identified with a unique tuple of integers. For example, we can refer to the iteration of Figure 4 in which $t=3$ and $i=7$ as $[3,7]$. We can describe the set of all iterations with a set of constraints derived from the loop bounds and conditional expressions [23,24], for this example,

\begin{displaymath}
\{ \ [ \ t, i \ ] \mid 0 \leq t < T \land 0 \leq i < N \ \}.
\end{displaymath}

The integers in these tuples may correspond to the loop index values of surrounding loops (as above), or they may indicate which of several statements is being performed. For example, if there were two statements in this loop, we could refer to the executions of individual statements as $[t,i,1]$ and $[t,i,2]$; statements in two consecutive nests would be $[1,t,i]$ and $[2,t,i]$.

The lexicographical ordering of these tuples defines the execution ordering of the statements and iterations, so we can describe a reordering transformation as a remapping of the tuples assigned to the iterations. The transformation used by Wolf and Lam to produce Figure 5 is

\begin{displaymath}
\{ \ [ \ t, i \ ] \rightarrow
[ \ (t+i) \ div \ s, t, (t+i) \ mod \ s \ ] \ \}
\end{displaymath}

and the transformation for Figure 7 is

\begin{displaymath}
\{ \ [ \ t, i \ ] \rightarrow
[ \ t \ div \ s, i+t, t \ mod \ s \ ] \ \}.
\end{displaymath}

In this framework, loop skewing shows up in as sums of index variables ($t+i$), and tiling as $div$ (for the tile number) and $mod$ (for the offset within the tile). In the first transformation, the tiles are skewed; in the second, the tiles are not skewed, but the execution of iterations within each tile is.

We can use the constraint manipulation techniques discussed by Pugh and Wonnacott [23] to check that the transformation does not violate any data dependences, and to apply the transformation to the set describing the iteration space. This transformed set can then be used as input to the code generation algorithms of Kelly, Pugh, and Rosser [25].

The constraint manipulation and code generation algorithms require that all constraints be affine, which requires that $s$ must be a known constant in the transformation above. More details about the use of this system can be found in the Omega Library documentation [26]; algorithmic details can be found in the papers cited above.


next up previous
Next: Time-Step Calculations and Iteration Up: Machine Balance, Compute Balance, Previous: Loop Skewing and Tiling

2002-04-22