next up previous
Next: Definitions Up: Automatic Blocking of Nested Previous: Notation

Statement of the Problem

We are given a convex set of lattice points tex2html_wrap_inline1640. This is the set of all values of the k dimensional natural index tex2html_wrap_inline1644 in the loop nest. We call tex2html_wrap_inline1556 the index space of the loop nest, which is the standard term, even though tex2html_wrap_inline1556 is a finite subset of tex2html_wrap_inline1650. We are also given a set of dependence displacements tex2html_wrap_inline1652 where each integer vector tex2html_wrap_inline1654 is the displacement in the index space from iterations that produce values to iterations that use them. The integer m is the number of such dependences. Hence, for all points tex2html_wrap_inline1658 and for each tex2html_wrap_inline1660, if tex2html_wrap_inline1662, then iteration tex2html_wrap_inline1664 must have been performed before we perform iteration i. We may also consider anti-dependences and output dependences and treat them in the same manner. (See [8] for the definition of the various kinds of dependences.)

We now consider the blocking problem. The problem is to partition tex2html_wrap_inline1668
where the subsets of index points tex2html_wrap_inline1672 are disjoint. The tex2html_wrap_inline1674 tile is the task of executing the loop body for all values of the loop index in tex2html_wrap_inline1676.

Some restrictions are in order if this partition of tex2html_wrap_inline1668 is to be of any use. The key restriction was stated by Wolfe [19]:

``Each tile is a unit of computation to be scheduled on a processor. Once a tile is scheduled ... it runs to completion without preemption. A tile will not be initiated until all dependence constraints for that tile are satisfied, so there will never be a reason that a tile, once started, should have to relinquish the processor.''
We call this the atomicity requirement.

The second, less fundamental but nevertheless important restriction is that the tiling should be expressible as a transformation of the original program. For this reason, we restrict our attention to partitions of tex2html_wrap_inline1668 achieved by cutting tex2html_wrap_inline1668 along hyperplanes. Wolfe's original tilings used planes normal to the natural coordinate axes. Here, we allow arbitrary planes with integer normals. If we want to cut up tex2html_wrap_inline1556 along hyperplanes normal to the integer vector tex2html_wrap_inline1686, we first apply loop index transformation to one of the original loops, replacing its index with tex2html_wrap_inline1688. We then strip mine this loop and bring the strip loop to the outermost position.

next up previous
Next: Definitions Up: Automatic Blocking of Nested Previous: Notation

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