next up previous
Next: Blocked Decompositions Up: Static Decompositions Previous: Calculating Orientations

Calculating Displacements

  As we expect communication at the displacement level to be relatively inexpensive nearest-neighbor communication, we do not consider sacrificing parallelism to avoid communication due to displacements. However, the algorithm minimizes any communication caused by conflicting displacements whenever possible. The displacements are calculated after the partitions and orientations have already been determined. Our compiler uses a simple greedy strategy that takes into account branch predictions and the offset sizes to find displacements that minimize communication along the most frequently executed paths. Eqn. 2 says that given the full data decomposition, , for array x referenced in a loop nest j (with the array index function ) the computation displacement . The data displacement, , for another array y accessed in the same loop nest can be calculated using .

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