Next: Definitions Up: Automatic Blocking of Nested Previous: Notation

# Statement of the Problem

We are given a convex set of lattice points . This is the set of all values of the k dimensional natural index in the loop nest. We call the index space of the loop nest, which is the standard term, even though is a finite subset of . We are also given a set of dependence displacements where each integer vector 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 and for each , if , then iteration 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

where the subsets of index points are disjoint. The tile is the task of executing the loop body for all values of the loop index in .

Some restrictions are in order if this partition of 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 achieved by cutting 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 along hyperplanes normal to the integer vector , we first apply loop index transformation to one of the original loops, replacing its index with . We then strip mine this loop and bring the strip loop to the outermost position.

Next: Definitions Up: Automatic Blocking of Nested Previous: Notation

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