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.