Software Pipelining and Loop-Carried Dependences

A loop body executed once per iteration leaves the machine’s functional units idle for most of each iteration: a load waits for memory, the operation that consumes it waits for the load, and only then does the next iteration’s load start. Software pipelining rewrites the loop so that iteration i’s loads overlap iteration i-1’s arithmetic and iteration i-2’s stores. Nothing about the instructions changes; what changes is the schedule, and the schedule is what the compiler emits.

The gain is bounded by two quantities. One is the machine’s resources: with four issue slots and a loop body of twelve operations, no schedule can do better than three cycles per iteration. The other is the loop’s recurrence: if iteration i depends on iteration i-1 through an operation chain of latency L, then the loop cannot run faster than L cycles per iteration no matter how wide the machine is. Both bounds are computable before a single instruction is scheduled, and both are worth computing because they tell the programmer whether an unroll will help.

The recurrence bound, computed first

Take the loop that computes a prefix-like recurrence:

for (int i = 1; i < n; i++)
    a[i] = a[i - 1] + b[i];

The dependence is on a, distance one iteration. The chain from the load of a[i-1] through the add to the store of a[i] has length: load latency plus add latency. If loads take four cycles to produce a value and adds take one, the chain is five cycles, and the loop can run at best one iteration per five cycles, because iteration i’s add cannot start until iteration i-1’s store has completed and its value is available for the next load.

This is the recurrence-constrained minimum initiation interval, usually written RecMII, and it is computed from the dependence graph by taking, for every cycle in the graph, the sum of the latencies around the cycle divided by the sum of the distances. A self-dependence with distance one and latency five gives five. The resource bound, ResMII, is the total number of operations of each type divided by the number of units of that type. The initiation interval of any schedule is at least the maximum of the two.

The computation is worth doing because it separates two very different problems. If RecMII dominates, unrolling will not help: the loop has a true serial chain and the only fix is to restructure the algorithm, for example by splitting the recurrence into independent partial sums. If ResMII dominates, unrolling and better scheduling will help up to the resource limit.

/* Four independent partial sums: the same addition count,
   but the recurrence distance is now four, so RecMII falls
   from the chain latency to the chain latency divided by four. */
float s0 = 0, s1 = 0, s2 = 0, s3 = 0;
for (int i = 0; i + 3 < n; i += 4) {
    s0 += a[i];
    s1 += a[i + 1];
    s2 += a[i + 2];
    s3 += a[i + 3];
}
float total = (s0 + s1) + (s2 + s3);

The transformation changes the summation order, so it is not valid for floating point under strict IEEE semantics unless the language permits reassociation. That is a real constraint and the reason compilers require a flag to perform it.

Modulo scheduling in outline

Modulo scheduling produces a schedule for one iteration and then rotates it so that iterations overlap. The schedule is described by an initiation interval II and a set of cycle offsets: operation o of iteration i executes at time i * II + offset(o). The prologue executes the first S-1 iterations partially, where S is the number of pipeline stages, filling the pipeline; the steady state executes every iteration with the same pattern of operations at different stages; the epilogue drains the last iterations.

The algorithm is iterative. Start with II equal to the maximum of the two bounds, attempt to schedule every operation within a window of II cycles subject to dependences and resources, and if the attempt fails, increment II and retry. The scheduling step is a list scheduler over a priority order derived from the critical path length; each operation is placed at the earliest cycle that satisfies its dependence constraints and finds a free resource slot in that modulo-II cycle.

The resource model is what makes this different from ordinary list scheduling. A resource that is free at cycle 3 is also free at cycle 3+II, 3+2II, and so on, so the scheduler tracks occupancy modulo II. A functional unit that can accept one operation per cycle has, for a given II, II slots in the modulo table, and the schedule must fit every operation into one of them.

Convergence is not guaranteed. For some loops no schedule exists at the computed lower bound, and the search increments II until it finds one or gives up. Compilers cap the attempts and fall back to unrolling without pipelining, which is a common outcome for loops with irregular bodies.

The prologue and epilogue cost

The steady state is efficient, but the prologue and epilogue are not: they contain partial iterations, and their length is proportional to the pipeline depth, which is roughly the number of stages times II. For a loop with II of four and five stages, the prologue is sixteen cycles of partially filled work.

For a loop that runs a thousand iterations, sixteen cycles of overhead is noise. For a loop that runs eight iterations, the pipelined version can be slower than the simple one, because the overhead exceeds the work saved. Compilers therefore guard the transformation with a trip-count check when the count is known at compile time, and skip the pipelined version for short loops.

The epilogue also has to handle the final iterations’ stores, which cannot be moved past the loop exit without knowing they are safe. Some implementations emit the steady-state kernel and a separate drain loop; others rely on predication to keep the last iterations’ operations in the same code with guards, which is where Mask Registers, Tail Handling, and the Cost of the Last Iteration becomes relevant.

Register pressure as the binding constraint

A modulo schedule keeps several iterations’ values live at once. With II cycles and a loop body of L cycles of work, the number of overlapping iterations in the steady state is about L/II, and each contributes its live values. Unrolling the loop by a factor U multiplies the live values again.

Register pressure is therefore the practical limit on how aggressively a loop can be pipelined. When the allocator runs out of registers, it inserts spills, and a spill inside the steady-state kernel adds a store and a load to every iteration, which may push the schedule past its II and force a larger one. Compilers often pipeline with a modest II and accept a longer schedule rather than spill.

The interaction with vectorisation is direct: a vector register holds many elements, so the same loop pipelined with vector operations has fewer operations but wider values, and the register count per value is unchanged. What changes is that a single vector operation covers the work of several scalar ones, so the II bound is reached at a coarser granularity. This is why loop-level parallelism and data-level parallelism are complementary rather than alternative: vectorising reduces the operation count, and software pipelining hides the latency of the remaining operations.

When the schedule cannot help

Three situations defeat software pipelining.

A loop with a true recurrence whose chain latency is long relative to the body: the schedule cannot beat RecMII, and the only remedy is algorithmic. Prefix sums, running maxima, and recurrence relations in numerical methods all fall here.

A loop with unpredictable control flow inside the body: an if inside the loop prevents operations from moving across it unless they are predicated, and predication costs slots. The scheduler’s freedom is limited to the straight-line portions.

A loop with memory dependences the compiler cannot disambiguate: if it cannot prove that the store to a[i] does not alias the load from b[j], it must keep them ordered, which serialises the iterations. Alias analysis quality therefore directly determines how much pipelining is possible, and languages with pointer arithmetic and type punning give the analyser less to work with than languages that restrict aliasing.

The hardware counterpart of this scheduling effort is dynamic out-of-order issue, which discovers independence at run time at the cost of the structures described in Register File Ports and Operand Delivery. The compiler’s advantage is that it can look arbitrarily far ahead and can restructure the loop; the hardware’s advantage is that it adapts to the actual latencies and to branches the compiler could not resolve. Neither subsumes the other, and current designs use both.