next up previous
Next: Tiling with Hyperplanes Up: Statement of the Problem Previous: Statement of the Problem

Definitions

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

We associate with tex2html_wrap_inline1556 and D the dependence graph tex2html_wrap_inline1726 with vertices tex2html_wrap_inline1556 and edges
displaymath1691
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.)


definition277
Note that tex2html_wrap_inline1750 is an open, convex set closed under multiplication by a positive scalar - i.e., tex2html_wrap_inline1750 is in fact a cone. It is polygonal, the intersection of the half spaces tex2html_wrap_inline1754. We call tex2html_wrap_inline1750 the time cone, without mentioning D, whenever there is no ambiguity.

The closure of tex2html_wrap_inline1750 is also important; it is defined by
displaymath1693

Two subsets of tex2html_wrap_inline1766 are important here. First, we must choose, as the normals to the hyperplanes used to partition tex2html_wrap_inline1556, integer vectors in tex2html_wrap_inline1766. The intersection of tex2html_wrap_inline1766 with the surface of the unit sphere in tex2html_wrap_inline1774 (with the euclidean norm) also plays a role.


lemma283
For the proof, observe that the iterations may be performed in order of increasing value of tex2html_wrap_inline1780 where x is any vector in tex2html_wrap_inline1750. Because all dependence displacements tex2html_wrap_inline1786 make an acute angle with such an x, no dependence constraint is violated. We may therefore interpret tex2html_wrap_inline1780 as the time at which iteration i is to be performed, hence the name we have given tex2html_wrap_inline1750. Points of tex2html_wrap_inline1556 with equal value of tex2html_wrap_inline1780 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 [13].

Again, if D results from a loop nest in Fortran or a language like it, we can show that tex2html_wrap_inline1750 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 tex2html_wrap_inline1750 easily follows.

We can now show how to choose hyperplanes for partitioning tex2html_wrap_inline1556 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).
definition288

The atomicity requirement is equivalent to the requirement that the quotient graph be acyclic. A sufficient condition for this is the following.


lemma293
For the proof, observe that, by their definition, the subsets of the partition induced by tex2html_wrap_inline1686 and tex2html_wrap_inline1704 may be ordered according to the values taken by tex2html_wrap_inline1688 on them. It follows from the definition of tex2html_wrap_inline1766 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 tex2html_wrap_inline1686, i.e., tex2html_wrap_inline1844, since by assumption tex2html_wrap_inline1846. But by definition, tex2html_wrap_inline1848 for all columns d of D.

Moldovan and Fortes [15] 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 [11].


next up previous
Next: Tiling with Hyperplanes Up: Statement of the Problem Previous: Statement of the Problem

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