This section presents a mathematical model of the decomposition problem.
We represent data and computation decompositions as affine transformations.
In this discussion, all loops are normalized to have a unit step size,
and all arrays subscripts are adjusted to start at 0.
A loop nest of depth **l**, with loop bounds that are affine
functions of the loop indices, defines an iteration
space , a polytope in **l**-dimensional space.
Each iteration of the loop nest corresponds to an integer point
in the polytope
and is identified by its index vector .
An array of dimension **m** defines an array space ,
an **m**-dimensional rectangle.
Each element in the
array is accessed by an integer vector .
Similarly, an **n**-dimensional processor array defines a processor
space , an **n**-dimensional rectangle.
We write an affine array index function
as
, where
**F** is a linear transformation and is a constant vector.

The problem can now be stated formally as follows. We want to find the computation decomposition for each loop nest, and the data decomposition for each array in each loop nest, such that parallelism is maximized and communication is minimized. The formal decompositions for the simple example from the previous section are shown in Figure 1(c).

Fri Apr 7 14:39:58 PDT 1995