LOOP SCHEDULING WITHOUT RESOURCE BOUNDS

Choosing an optimal schedule subject to data-dependence constraints and resource hazards is difficult - it is NP-complete, for example. Although NP-completeness should never scare the compiler writer (graph coloring is NP-complete, but the approximation algorithm for graph coloring described in is very successful), it remains the case that resource-bounded loop scheduling is hard to do in practice. We will first describe an algorithm that ignores the resource constraints and finds an optimal schedule subject only to the data-dependence constraints. This algorithm is not useful in practice, but it illustrates the kind of opportunities there are in instruction-level parallelism. The Aiken-Nicolau loop pipelining algorithm has several steps:

1. Unroll the loop;
2. Schedule each instruction from each iteration at the earliest possible time;
3. Plot the instructions in a tableau of iteration-number versus time;
4. Find separated groups of instructions at given slopes;
5. Coalesce the slopes;
6. Reroll the loop.

We use Program 20.4a as an example to explain the notions of tableau, slope, and coalesce. Let us assume that every instruction can be completed in one cycle, and that arbitrarily many instructions can be issued in the same cycle, subject only to data-dependence constraints.(a) A for-loop to be software-pipelined. (b) After a scalar-replacement optimization (in the deFlnition of a); and scalar variables labeled with their iteration-number.

Data dependence through memory For optimal scheduling of stores and fetches, we need to trace data dependence as each value is stored into memory and then fetched back. As discussed on page 424, dependence analysis of memory references is not trivial! In order to illustrate loop scheduling for Program 20.4a without full-fledged dependence analysis, we can use scalar replacement to replace the reference to V[i − 1] with the (equivalent) b; now we can see that in the resulting Program 20.4b all memory references are independent of each other, assuming that the arrays U, V, W, X do not overlap. Next we mark each variable in the loop body to indicate whether this iteration's value is used, or the previous iteration's value, as shown in Program 20.4b. We can construct a data-dependence graph as a visual aid in scheduling; solid edges are data dependences within an iteration, and dotted edges are loop-carried dependences, as shown in Graph 20.5a.GRAPH 20.5: Data-dependence graph for Program 20.4b: (a) original graph, in which solid edges are same-iteration dependences and dotted edges are loop-carried dependences; (b) acyclic dependences of the unrolled loop.

Now suppose we unroll the loop; the data-dependence graph is a DAG, as shown in Graph 20.5b. Scheduling DAGs is easy if there are no resource constraints; starting from operations with no predecessors, each operation goes as soon as its predecessors have all completed:

It is convenient to write this schedule in a tableau where the rows are successive cycles and the columns are successive iterations of the original loop, as shown in Table 20.6a. After a few iterations are scheduled, we notice a pattern in the tableau: There is a group of instructions cdeh racing down to the lower-right corner with a slope of three cycles per iteration, another group abg with a more moderate slope of two cycles per iteration, and a third group fj with zero slope. The key observation is that there are gaps in the schedule, separating identical groups, that grow larger at a constant rate. In this case the groups of instructions at iteration i ≥ 4 are identical to the groups at iteration i + 1. In general the groups at iteration i will be identical to the groups at i + c,where sometimes c > 1; see Exercise 20.1. Theorems:

• If there are K instructions in the loop, the pattern of identical groups separated by gaps will always appear within K² iterations (and usually much sooner).
• We can increase the slopes of the less steeply sloped groups, thereby either closing the gaps or at least making them small and nonincreasing, without violating data-dependence constraints.
• The resulting tableau has a repeating set of m identical cycles, which can constitute the body of a pipelined loop.
• The resulting loop is optimally scheduled (it runs in the least possible time).

See the Further Reading section for reference to proofs. But to see why the loop is optimal, consider that the data-dependence DAG of the unrolled loop has some path of length P to the last instruction to execute, and the scheduled loop executes that instruction at time P. The result, for our example, is shown in Table 20.6b. Now we can find a repeating pattern of three cycles (since three is the slope of the steepest group). In this case, the pattern does not begin until cycle 8; it is shown in a box. This will constitute the body of the scheduled loop. Irregularly scheduled instructions before the loop body constitute a prologue, and instructions after it constitute the epilogue. Now we can generate the multiple-instruction-issue program for this loop, as shown in Image 20.7. However, the variables still have subscripts in this "program": The variable j_i+1 is live at the same time as j_i. To encode this program in instructions, we need to put in MOVE instructions between the different variables, as shown in Image 20.8.

This loop is optimally scheduled - assuming the machine can execute eight instructions at a time, including four simultaneous loads and stores. Multicycle instructions Although we have illustrated an example where each instruction takes exactly one cycle, the algorithm is easily extensible to the situation where some instructions take multiple cycles.