The role of the constraints due to multiple arrays is to ensure that there exists a single data decomposition matrix D for each array. These constraints are used to initialize the data partitions. Such constraints are necessary if there are two distinct paths in the interference graph from an array x to another array y. For example, consider the following code fragment:
The array index functions for X and Y in
the first loop nest are
.
The array index functions for X and Y in the second
loop nest are 
and 
,
respectively.
A decomposition that is free of reorganization communication will have
decomposition matrices 
and 
(for arrays X and Y, respectively) such that Eqn. 3
holds for some 
and 
(for loop nests 1 and 2, respectively).
For iterations 
in loop nest 1 and 
in
loop nest 2, we have the following:
Since the array index functions are invertible,
these equations produce the following equations for 
:
and 
. Thus,
and 
.
If all the array access functions for each array are
equal then the above equation will yield 
and
, and no additional constraints are placed on
the partitions.
In the example,
Eqn. 4 is
.
Thus,
.
Simplifying the equation gives a constraint on the partition of array X:
.
Similar analysis yields the same constraint on the partition of
array Y: 
.
This partition means that elements along the diagonal are allocated
to the same processor.
In general, when the array index
functions are not invertible, we must introduce auxiliary
variables and use a pseudo-inverse function.
The techniques we use are similar to those presented in other
literature [3,29].
This analysis is run on all pairs of arrays involved in a cycle in the interference graph (including the degenerate case of multiple access functions for one array in a loop nest). If an array is involved in multiple cycles and multiple constraints are found, then the constraints are summed. In general, when computing the data constraints on an array used in multiple loop nests, it is possible that the loop nests access different subsections of the array. If this is the case, each loop nest only contributes to the constraints for the section of the array that it references.
