   Next: Tiling with Hyperplanes Up: Statement of the Problem Previous: Statement of the Problem

## Definitions

First, we define the type of partition of that we are considering. Let an integer vector and an integer block size parameter be given. The partition induced by and is given by (1) where (Imagine a knife aligned so that is normal to its flat side, cutting into slices of equal thickness .)

We associate with and D the dependence graph with vertices and edges We assume that G is acyclic. (If the dependence graph comes from a loop nest in an imperative language like Fortran, then G has to be acyclic.) Note that is an open, convex set closed under multiplication by a positive scalar - i.e., is in fact a cone. It is polygonal, the intersection of the half spaces . We call the time cone, without mentioning D, whenever there is no ambiguity.

The closure of is also important; it is defined by Two subsets of are important here. First, we must choose, as the normals to the hyperplanes used to partition , integer vectors in . The intersection of with the surface of the unit sphere in (with the euclidean norm) also plays a role. For the proof, observe that the iterations may be performed in order of increasing value of where x is any vector in . Because all dependence displacements make an acute angle with such an x, no dependence constraint is violated. We may therefore interpret as the time at which iteration i is to be performed, hence the name we have given . Points of with equal value of are independent of one another and can be executed in any order - or in parallel, for that matter. This is the essence of Lamport's hyperplane method for the parallel execution of do-loops .

Again, if D results from a loop nest in Fortran or a language like it, we can show that is not empty. In fact, it is easy to see that D has the property that the first nonzero element of every column is positive (i.e. it is lexicographically positive.) From this, the nonemptyness of easily follows.

We can now show how to choose hyperplanes for partitioning in such a manner that Wolfe's atomicity requirement is satisfied. First, we restate the requirement in terms of the quotient of the dependence graph under the partition (1). The atomicity requirement is equivalent to the requirement that the quotient graph be acyclic. A sufficient condition for this is the following. For the proof, observe that, by their definition, the subsets of the partition induced by and may be ordered according to the values taken by on them. It follows from the definition of that no point in a lower numbered subset can depend on any point in a higher numbered subset; if there were such a pair, say a point x that depends on a point y such that x - y = d for some column d of D, then d makes an obtuse angle with , i.e., , since by assumption . But by definition, for all columns d of D.

Moldovan and Fortes  have used this technique for the synthesis of systolic arrays without cyclic data flow, which allows the array to be used to solve problems larger than the array. They gave no method for choosing the hyperplanes. The material of this section was also presented by Irigoin and Triolet .   Next: Tiling with Hyperplanes Up: Statement of the Problem Previous: Statement of the Problem

Jack Dongarra
Tue Feb 18 15:39:11 EST 1997