## Solving Space-Partition Constraints

**Introduction**: Once the space-partition constraints have been extracted, standard linear algebra techniques can be used to find the affine partitions satisfying the constraints.

**Algorithm:** Finding a highest-ranked synchronization-free affine partition for a program.

**INPUT:** A program with affine array accesses.

**OUTPUT**: A partition.

**METHOD**: Do the following:

**1.** Find all data-dependent pairs of accesses in a program for each pair of data-dependent accesses, T\ — ( F i , f i , B i , b i ) in statement s\ nested in di loops and T2 = ( F 2 , f 2 , B 2 , b 2 ) in statement s2 nested in d2 loops. Let ( C i , c i ) and ( C 2 , c 2 ) represent the (currently unknown) partitions of statements s\ and s2, respectively. The space-partition constraints state that if

F i i i fi — F 2 i 2 f2

then

C i i i ci = C 2 i 2 c2

for all ii and i2, within their respective loop bounds. We shall generalize the domain of iterations to include all ii in Zdl and i2 in Zd2; that is, the bounds are all assumed to be minus infinity to infinity. This assumption makes sense, since an affine partition cannot make use of the fact that an index variable can take on only a limited set of integer values.

**2**. For each pair of dependent accesses, we reduce the number of unknowns in the index vectors.

a) Note that Fi f is the same vector as F f

That is, by adding an extra component 1 at the bottom of column vector i, we can make the column-vector f be an additional, last column of the matrix F. We may thus rewrite the equality of the access functions F i i i f\ = F 2 i 2 f2 as

[ Fi -f2 (fi - f 2 ) ; = 0.

b) The above equations will in general have more than one solution. However, we may still use Gaussian elimination to solve the equations for the components of ix and i2 as best we can. That is, eliminate as many variables as possible until we are left with only variables that cannot be eliminated. The resulting solution for i2 and i2 will have the form

where U is an upper-triangular matrix and t is a vector of free variables

ranging over all integers.

c) We may use the same trick as in Step (2a) to rewrite the equality of the partitions. Substituting the vector (ii, i 2 ,1) with the result from Step (2b), we can write the constraints on the partitions as

; Ci - C 2 (ci - c2) ] U = 0.

**3**. Drop the nonpartition variables. The equations above hold for all combinations of t if

[ Ci - C 2 (ci - c2 ) ] U = 0.

Rewrite these equations in the form Ax = 0, where x is a vector of all the unknown coefficients of the affine partitions.

**4**. Find the rank of the affine partition and solve for the coefficient matrices. Since the rank of an affine partition is independent of the value of the constant terms in the partition, we eliminate all the unknowns that come from the constant vectors like ci or c 2 , thus replacing Ax = 0 by simplified constraints A'x' = 0. Find the solutions to A'x' = 0, expressing them as B, a set of basis vectors spanning the null space of A'.

**5.** Find the constant terms. Derive one row of the desired affine partition from each basis vector in B, and derive the constant terms using Ax = 0. Note that Step 3 ignores the constraints imposed by the loop bounds on variables t. The constraints are only stricter as a result, and the algorithm must therefore be safe. That is, we place constraints on the C's and c's assuming t is arbitrary. Conceivably, there would be other solutions for the C's and c's that are valid only because some values of t are impossible. Not searching for these other solutions may cause us to miss an optimization, but cannot cause the program to be changed to a program that does something different from what the original program does.