next up previous
Next: The Displacement. Up: Basic Concepts Previous: The Partition.

The Orientation.

  The partition determines which array elements and iterations are local to a single processor. The orientation together with the displacement can now specify the processor on which the data and computation are allocated. In particular, the orientation gives the correspondence between the data and computation dimensions and the processor dimensions. In loop nest 1, the columns of array Y are accessed in the reverse order from the columns of X. In loop nest 2, the columns of array Y are accessed in the same order as the rows of array Z. One solution that satisfies all these requirements is to allocate the columns of X in forward order, and the columns of Y and the rows of Z in reverse order. The iterations of the loop in loop nest 2 must now be reversed as well. The orientation is illustrated in Figure 1(b).

Formally, the matrix D from Def. 2.1 defines the data orientation and the matrix C from Def. 2.2 is the computation orientation. The matrices for the example are also shown in Figure 1(b). Note that there exist many different communication-free orientations, all with the same partition. For this example, we could just have easily chosen to allocate the columns of X in reverse order, and the columns of Y and the rows of Z in forward order. This alternative orientation would result in , and , with and .



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