## Controlling the Order of Execution

**Introduction:** The linear inequalities extracted from the lower and upper bounds of a loop body define a set of iterations over a convex polyhedron. As such, the representation assumes no execution ordering between iterations within the iteration space. The original program imposes one sequential order on the iterations, which is the lexicographic order with respect to the loop index variables ordered from the outermost to the innermost. However, the iterations in the space can be executed in any order as long as their data dependences are honored (i.e., the order in which writes and reads of any array element are performed by the various assignment statements inside the loop nest do not change).

The problem of how we choose an ordering that honors the data dependences and optimizes for data locality and parallelism is hard and is dealt with later starting from Synchronization-Free Parallelism. Here we assume that a legal and desirable ordering is given, and show how to generate code that enforces the ordering.

**Projection: **Geometrically speaking, we can find the loop bounds of the outer loop indexin a two-deep loop nest by projecting the convex polyhedron representing theiteration space onto the outer dimension of the space. The projection of apolyhedron on a lower-dimensional space is intuitively the shadow cast by theobject onto that space. The projection of the two-dimensional iteration space inFig. 11.11 opto the i axis is the vertical line from 0 to 5; and the projection onto the j axis is the horizontal line from 0 to 7. When we project a 3-dimensional object along the z axis onto a 2-dimensional x and y plane, we eliminate variable z, losing the height of the individual points and simply record the 2-dimensional footprint of the object in the x-y plane.

Loop bound generation is only one of the many uses of projection. Projection can be defined formally as follows. Let S be an n-dimensional polyhedron. The projection of S onto the first m of its dimensions is the set of points (xi,x2,... ,xm) such that for some x m 1 , x m 2 , . . . ,xn, vector [xi,x2,... ,xn] is in S. We can compute projection using Fourier-Motzkin elimination, as follows:

**Algorithm**: Fourier-Motzkin elimination.

**INPUT:**A polyhedron S with variables That is, 5 is a set of linear constraints involving the variables X{. One given variable xm is specified to be the variable to be eliminated.

**OUTPUT:**A polyhedron 5" with variables x\,... ,xm-\,xm i,... ,xn (i.e., all the variables of S except for xm) that is the projection of S onto dimensions other than the mth.

**METHOD:**Let C be all the constraints in S involving xm. Do the following:

1. For every pair of a lower bound and an upper bound on xm in C, such as

create the new constraint

c_{2}L < c\U

Note that c\ and c2 are integers, but L and U may be expressions with variables other than xm.

2. If integers c\ and c2 have a common factor, divide both sides by that factor.

3. If the new constraint is not satisfiable, then there is no solution to S; i.e., the polyhedra 5 and S' are both empty spaces.

4. S' is the set of constraints S - C, plus all the constraints generated in step 2.

Note, incidentally, that if *xm *has *u *lower bounds and *v *upper bounds, eliminating *xm *produces up to *uv *inequalities, but no more.

The constraints added in step (1) of Algorithm 11.11 correspond to the implications of constraints *C *on the remaining variables in the system. Therefore, there is a solution in *S' *if and only if there exists at least one corresponding solution in S. Given a solution in S' the range of the corresponding xm can be found by replacing all variables but xm in the constraints C by their actual values.

**Loop-Bounds Generation: **Now that we have defined Fourier-Motzkin elimination, the algorithm to generatethe loop bounds to iterate over a convex polyhedron (Algorithm 11.13) isstraightforward. We compute the loop bounds in order, from the innermost tothe outer loops. All the inequalities involving the innermost loop index variablesare written as the variable's lower or upper bounds. We then project away the dimension representing the innermost loop and obtain a polyhedronwith one fewer dimension. We repeat until the bounds for all the loop indexvariables are found.

**Algorithm:**Computing bounds for a given order of variables.

**INPUT**: A convex polyhedron S over variables v\,... ,vn.

**OUTPUT**: A set of lower bounds L{ and upper bounds Ui for each vi, expressed only in terms of the fj's, for j < i.

**METHOD:**The algorithm is described in Fig. 11.15.