next up previous
Next: Summary of Algorithm Up: Minimizing Synchronization and Previous: Minimizing Synchronization and


Our algorithm represents loop nests and arrays as multi-dimensional spaces. Computation and data decompositions are represented as a two-step mapping: we first map the loop nests and arrays onto a virtual processor space via affine transformations, and then map the virtual processors onto the physical processors of the target machine via one of the following folding functions: BLOCK, CYCLIC or BLOCK-CYCLIC.

The model used by our compiler represents a superset of the decompositions available to HPF programmers. The affine functions specify the array alignments in HPF. The rank of the linear transformation part of the affine function specifies the dimensionality of the processor space; this corresponds to the dimensions in the DISTRIBUTE statement that are not marked as ``*''. The folding functions map directly to those used in the DISTRIBUTE statement in HPF. As the HPF notation is more familiar, we will use HPF in the examples in the rest of the paper.

Saman Amarasinghe
Fri Apr 7 11:22:17 PDT 1995