next up previous
Next: (3) Data-Computation Relation. Up: Partition Constraints Previous: (1) Single Loop

(2) Multiple Arrays.

The role of the constraints due to multiple arrays is to ensure that there exists a single data decomposition matrix D for each array. These constraints are used to initialize the data partitions. Such constraints are necessary if there are two distinct paths in the interference graph from an array x to another array y. For example, consider the following code fragment:

The array index functions for X and Y in the first loop nest are . The array index functions for X and Y in the second loop nest are and , respectively.

A decomposition that is free of reorganization communication will have decomposition matrices and (for arrays X and Y, respectively) such that Eqn. 3 holds for some and (for loop nests 1 and 2, respectively). For iterations in loop nest 1 and in loop nest 2, we have the following:

Since the array index functions are invertible, these equations produce the following equations for : and . Thus,

 

and .

If all the array access functions for each array are equal then the above equation will yield and , and no additional constraints are placed on the partitions. In the example, Eqn. 4 is . Thus, . Simplifying the equation gives a constraint on the partition of array X: . Similar analysis yields the same constraint on the partition of array Y: . This partition means that elements along the diagonal are allocated to the same processor. In general, when the array index functions are not invertible, we must introduce auxiliary variables and use a pseudo-inverse function. The techniques we use are similar to those presented in other literature [3,29].

This analysis is run on all pairs of arrays involved in a cycle in the interference graph (including the degenerate case of multiple access functions for one array in a loop nest). If an array is involved in multiple cycles and multiple constraints are found, then the constraints are summed. In general, when computing the data constraints on an array used in multiple loop nests, it is possible that the loop nests access different subsections of the array. If this is the case, each loop nest only contributes to the constraints for the section of the array that it references.



next up previous
Next: (3) Data-Computation Relation. Up: Partition Constraints Previous: (1) Single Loop



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