next up previous
Next: The Orientation. Up: Basic Concepts Previous: Basic Concepts

The Partition.

There is a data dependence of (0,1) in loop nest 2 which serializes the loop. No communication is necessary when all the elements in each column of array Y and each row of array Z are assigned to the same processor. Since the elements in each column of array Y are on the same processor, iterations of in loop nest 1 are also assigned to the same processor and execute sequentially (even though there are no dependences in loop nest 1). In turn, the columns of array X are allocated to the same processor as well. The partitions for this example are shown in Figure 1(a). Informally, the data and computation partitions specify which array elements and iterations, respectively, are assigned to the same processor, but not which processor.

Formally, the subspace of the array space accessed by an array referenced in a loop nest is denoted by S and is the range of the array index matrix F:

 

For an array of dimension m, whenever , then .

Let D be the data decomposition matrix from Def. 2.1. Two array elements are allocated to the same processor if and only if

that is,

Conversely, any two array elements such that may be assigned to different processors and are considered distributed.

Let C be the computation decomposition matrix from Def. 2.2. Two iterations are executed on the same processor if and only if

that is,

Any two iterations such that are said to be distributed and may run on different processors. The mathematical representation of the partitions for the example is also shown in Figure 1(a). The data partitions for X and Y indicate that all array elements along the direction (i.e. each column) are assigned to the same processor. Similarly, the data partition for Z means that all elements along the direction are assigned to the same processor. The computation partitions indicate that all iterations of the loop in the first loop nest, and all iterations of the loop in the second loop nest, are executed on the same processor.



next up previous
Next: The Orientation. Up: Basic Concepts Previous: Basic Concepts



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