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.

Fri Apr 7 14:39:58 PDT 1995