Modulo Scheduling and Software Pipelining

A loop body scheduled as a basic block pays the pipeline’s fill and drain cost on every iteration. If the body is a chain of dependent operations whose total latency is, say, twenty cycles, and the machine can issue four instructions per cycle, the body occupies five issue slots but twenty cycles of wall time. The loop’s throughput is one iteration per twenty cycles regardless of how much issue width is available, because the chain is serial and nothing from the next iteration starts until the current one finishes.

Software pipelining attacks exactly this. It reschedules the loop so that iteration i+1 begins before iteration i has completed, with each iteration’s instructions spread across several cycles. The steady state then issues instructions from multiple iterations in the same cycle, and the loop’s throughput is limited by the resource that is scarcest rather than by the length of the chain.

The Overlapped Steady State

The transformation is easiest to see on a loop with a single recurrence. Suppose the body computes s = s + a[i] and increments i. The dependence from s to itself has a latency equal to the add’s latency, and that latency is the minimum time between successive iterations if the recurrence is respected. If the add takes four cycles, the loop cannot go faster than one iteration per four cycles, no matter how wide the machine is. That number — the latency of the recurrence divided by the distance of the dependence — is the recurrence-constrained lower bound on the initiation interval, and it is the loop-level analogue of the block-level bound described in List Scheduling and the Critical Path.

Resource constraints give a second bound. If the body uses three multiply operations and the machine has one multiplier, the initiation interval cannot be less than three cycles. More generally, for each resource, the total demand per iteration divided by the supply per cycle is a lower bound. The initiation interval is the maximum over all resources and all recurrences of these bounds, and it is usually not achievable because the constraints interact.

Given a target initiation interval, the scheduler assigns each operation a cycle modulo the interval. The modulo assignment is what gives the technique its name. An operation scheduled at absolute cycle t runs at cycle t mod II within each iteration’s pattern, and iterations are offset from each other by II cycles. The steady-state loop is the pattern of II cycles, and every iteration executes the same pattern shifted in time.

The output of the transformation is not a loop whose body is the original body. It is a loop whose body contains instructions from several iterations, plus a prologue that fills the pipeline and an epilogue that drains it. For a loop of N iterations with a schedule spanning S stages, the prologue executes the first stages of the first iterations, the steady state executes all stages of the middle iterations, and the epilogue finishes the last iterations. The steady state is where the speedup comes from; the prologue and epilogue are overhead that must be amortized over enough iterations.

Modulo Reservation Tables

The resource model is a table indexed by cycle modulo the initiation interval. Each entry records how much of each resource is in use at that phase. Placing an operation at phase p requires that its resource demands fit in the entry for p and for every phase it occupies given its latency.

A simplified model, with one resource class and unit-latency operations:

/* Try to place op at the earliest phase >= start that fits. */
int place(int op, int start, int ii) {
    for (int p = start; p < start + ii; p++) {
        int ph = p % ii;
        if (used[ph] + demand[op] <= capacity) {
            used[ph] += demand[op];
            sched[op] = p;
            return p;
        }
    }
    return -1;              /* no phase fits: this II is infeasible */
}

For a multi-cycle operation the demand must be recorded in every phase the operation occupies, which is why the table is a matrix of resources by phases rather than a vector. The check on placement is a check of one row of that matrix against the capacity.

The placement order matters because a greedy placement can fail to find a feasible schedule even when one exists. The standard heuristic is to place operations on the most constrained recurrence first, since those operations have the least freedom in their phase assignment. This is the same intuition as list scheduling’s critical-path priority, translated from time to phase.

Finding the Initiation Interval

The search for a feasible schedule proceeds by trying increasing values of the initiation interval, starting from the maximum of the lower bounds. For each candidate, the scheduler attempts to place all operations; if it succeeds, the interval is feasible and the search stops. If it fails, the interval is increased and the attempt repeats.

The naive version of this search can be expensive, because each attempt is a scheduling problem and failures do not always give useful information about how much to increase. Iterative modulo scheduling, as formulated by Rau, adds a backtracking mechanism: when an operation cannot be placed, the scheduler may evict an already-placed operation that conflicts with it and retry, with a bound on the number of evictions to keep the search finite. The eviction heuristic prefers to evict operations whose placement is least constrained, which is the reverse of the placement priority.

Two structural facts make the search tractable. The first is that the initiation interval is bounded above by the length of the original schedule, since scheduling each iteration sequentially is always feasible. The second is that the lower bound is usually close to the achievable value for loops with few recurrences, so the search examines a small number of candidates. Loops with many recurrences and irregular resource demands are where the search becomes expensive, and those are also the loops where the payoff is largest.

Register Pressure and Stage Count

Every additional stage in the pipeline keeps more values live simultaneously. A schedule with S stages holds the partial results of S iterations at once, and each of those results needs a register. The register demand therefore grows roughly linearly with the stage count, and the stage count grows as the initiation interval shrinks.

This is the central trade of software pipelining: throughput against registers. A tight initiation interval hides more latency and needs more registers; a loose one needs fewer and hides less. On a machine with a small register file, the tight schedule spills, and the spill loads and stores consume the issue slots the pipelining was supposed to free. The transformation then makes the loop slower, which is a well-known failure mode and the reason production compilers cap the stage count and check the register demand before committing.

The standard countermeasures are to reduce the stage count by lengthening the initiation interval, to apply the transformation only to loops whose trip count is large enough to amortize the prologue, and to use a technique called register pipelining or modulo variable expansion, which renames the values that cross iterations so that each stage has its own copy. Renaming does not reduce the number of live values; it only makes the allocation problem expressible, since without distinct names the same virtual register would appear to be defined and used in conflicting phases.

The trip-count condition is worth stating as a number. If the schedule has S stages, the steady state needs at least S-1 iterations before the last stage of the first iteration has executed, and the code outside the steady state amounts to (S-1) partial iterations at the start and (S-1) at the end. The transformation pays off only when N is substantially larger than S, and compilers therefore guard the pipelined loop with a runtime check that the trip count exceeds a threshold, falling back to the unpipelined version otherwise. The threshold is a heuristic, and it is one of the places where a compiler’s estimate of the loop’s cost directly determines whether the optimization fires.

Correctness at the Edges

The prologue and epilogue are not optional bookkeeping; they are where most of the bugs in a software pipeliner live. Three issues recur.

The first is the loop-carried dependence that the schedule assumes but the code does not express. If the recurrence’s distance is one iteration, the modulo schedule places the dependent operation exactly one initiation interval later, and the value must be forwarded across the stage boundary. If the distance is greater than one, the schedule must place the operation that many intervals later, and the register that carries the value must persist across those intervals. A pipeliner that gets the distance wrong produces a loop that computes the right answer for the first few iterations and then diverges.

The second is memory dependence. A loop that writes a[i] and reads a[i-1] has a dependence with distance one, and the schedule must respect it. A loop that reads a[i+4] and writes a[i] has a recurrence of the opposite sign: iteration i’s read consumes the value that iteration i+4 writes, so the dependence runs from the read forward to the later write, and the operand read in an early iteration must come from a write the schedule places four iterations later. In the modulo formulation the distance is positive but the operand is produced after it is consumed, and the constraint it places on the relative phases of the read and the write is what makes such loops hard to schedule; they are frequently rejected rather than risk a stage ordering that cannot be satisfied.

The third is the epilogue’s partial iterations. The last S-1 iterations execute only the later stages, and the code for those stages must be duplicated with the earlier stages removed. The duplication multiplies code size by the stage count in the worst case, which is why pipelining is applied to small loop bodies and why code-size-conscious compilers restrict it.

Where It Fits

Modulo scheduling is most valuable where the hardware cannot reorder: VLIW machines, in-order cores with narrow issue, and DSPs with exposed pipelines. On such a target the steady state fills slots that a plain block schedule would leave empty, which is the packing problem Bundling Instructions for VLIW Issue Slots describes from the encoding side. On an out-of-order core with a large reorder buffer, the hardware already overlaps iterations, and the compiler’s pipelined schedule mostly duplicates what the hardware does while consuming registers the hardware would rather have used for its own window.

The technique also requires a loop with enough iterations and enough parallelism to fill the stages. A loop with a trip count of four and a body of three instructions gains nothing and loses code size. Recognizing which loops qualify is a profitability question, and it depends on the same profile information that every other scheduling decision needs. Without it, the compiler applies the transformation to loops it can prove are countable and large, and leaves the rest alone.