next up previous
Next: The Partition. Up: Global Optimizations for Parallelism Previous: Problem Formulation

Basic Concepts

  The problem of finding data decompositions and computation decompositions can be broken down into three distinct components using the affine model. The partition determines the computation and data that are allocated to the same processor. Mathematically, data and computation partitions are described by the nullspace of the matrices D and C from Definitions 2.1 and 2.2. The orientation, represented by the matrices D and C, describes the mapping between the axes of the array elements and loop iterations, and the processors. Lastly, the displacement gives the offset of the starting position of the data and computation, and corresponds to the constant vectors and . We illustrate the partition, orientation and displacement by developing a communication-free decomposition for the sample program in Figure 1.

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