next up previous
Next: Basic Concepts Up: Problem Overview Previous: A Simple Example

Problem Formulation

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

Jennifer-Ann M. Anderson
Fri Apr 7 14:39:58 PDT 1995