next up previous
Next: Calculating Partitions Up: Partition Constraints Previous: (2) Multiple Arrays.

(3) Data-Computation Relation.

This constraint ensures that the relationship between data and computation from Eqn. 3 holds. If two iterations and in loop nest j are mapped to the same processor, then the data of array x they access must also be mapped to the same processor. For , then from section 3, . Using Eqn. 3: and thus . Formally,

 

Similarly, two iterations and in loop nest j must be mapped to the same processor if the data of array x they access are mapped to the same processor. Again, let . If then . Since , if then the two iterations reference the same array location and must be mapped to the same processor. Let . In general,

 

The sequential loops in each loop nest cause elements of the array referenced in that loop nest to be allocated local to the same processor. The local array elements cause iterations of the loop nests that access those elements to be executed sequentially.



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