Initiation Interval and the Recurrence That Caps Throughput

A pipeline’s throughput is usually described in instructions per cycle, which assumes that the instructions are independent enough to keep the stages occupied. A loop carried dependency violates that assumption, and it does so in a way that no amount of hardware parallelism can repair. The correct statement of the limit is the initiation interval: the number of cycles between the start of one iteration and the start of the next, below which the loop cannot be scheduled without changing its meaning. That number is a property of the dependence graph, and it is computable before any scheduling is attempted.

The recurrence bound

Take the simplest recurrence:

for (int i = 1; i < n; i++)
    a[i] = a[i - 1] * k + c;

Every iteration reads the value written by the previous iteration. The multiply has latency L_mul and the add has latency L_add. Iteration i’s store cannot complete until its multiply and add have, and iteration i+1’s multiply cannot start until iteration i’s store has produced its value. The chain around the loop has length L_mul + L_add cycles, and that is the minimum initiation interval: one iteration every L_mul + L_add cycles, regardless of how many execution units the machine has.

Formally, for a dependence edge from operation u to operation v with latency delay(u, v) and a distance of d iterations, the constraint on the initiation interval II is

II · d ≥ delay(u, v)

for every edge. For a cycle in the dependence graph, summing over the edges gives a lower bound:

II ≥ (sum of delays around the cycle) / (sum of distances around the cycle)

That is the recurrence-constrained minimum initiation interval, usually written RecMII. It is a lower bound on any schedule, and it is achievable only if the resource constraints also permit it.

The bound is the reason a chain of dependent floating-point operations runs at the latency of the chain rather than at the throughput of the unit. A machine with four multipliers and a four-cycle multiply latency can start four independent multiplies per cycle, but a recurrence with a four-cycle multiply on its critical path starts one iteration every four cycles, using one multiplier’s worth of capacity. The other three sit idle unless the compiler can find independent work to interleave.

The resource bound

The second constraint is the number of functional units. If a loop body contains U uses of a unit that the machine can start once per cycle, and the schedule must place all of them within II cycles, then

II ≥ U

This is the resource-constrained minimum initiation interval, usually written ResMII, and it is distinct from RecMII, the recurrence bound. The two combine as the maximum, which is the minimum initiation interval the scheduler must target.

The interesting cases are where the two bounds are far apart. A loop with a long recurrence and few operations is recurrence-bound: adding execution units does nothing, and the only fix is to shorten the recurrence by algebraic transformation. A loop with many independent operations and no recurrence is resource-bound: adding units helps linearly until the recurrence bound, if any, becomes the limit.

There is a third bound that matters in practice: the register file. A modulo schedule with initiation interval II overlaps II iterations of the loop, and each overlapping iteration may hold values in registers. The number of live values across the schedule is the register pressure, and if it exceeds the register file the scheduler must either increase II or spill. Spilling adds loads and stores, which add to the resource bound, which may increase II further. This interaction is why aggressive software pipelining can make a loop slower.

/* Minimum initiation interval from a dependence cycle. `edges` lists, for one
   strongly connected component of the dependence graph, the latency and the
   iteration distance of each edge. */
struct edge { int delay; int distance; };

int recurrence_mii(const struct edge *e, int n)
{
    int sum_delay = 0, sum_dist = 0;
    for (int i = 0; i < n; i++) {
        sum_delay += e[i].delay;
        sum_dist  += e[i].distance;
    }
    if (sum_dist == 0) return 0;          /* no cycle: no recurrence bound */
    return (sum_delay + sum_dist - 1) / sum_dist;   /* ceiling division */
}

The ceiling division is the whole arithmetic of the bound: a cycle with total latency 13 and total distance 3 forces II ≥ 5, because 4 cycles would give 12 < 13.

Why the recurrence is a hardware fact and not a compiler failing

It is worth separating two claims that sound similar. The first is that a particular compiler failed to schedule a loop well. The second is that no schedule exists with II below some value. The recurrence bound is the second kind of claim, and it holds for any machine: if the value must travel around the loop through operations with total latency L and the loop’s dependence distance is d, then d iterations cannot start in fewer than L cycles.

Hardware can attack the bound in only two ways. It can reduce L, by making the operations faster or by removing operations from the critical path. Or it can increase d, by restructuring the computation so that iteration i depends on iteration i−2 rather than i−1. The second is an algebraic transformation and belongs to the compiler; the first is a microarchitectural one. Neither can violate the bound.

There is a hardware trick that appears to violate it: forwarding a result from a later pipeline stage back to an earlier one shortens the effective latency of the recurrence. If the multiply’s result is available at the end of its third stage rather than at write-back, the chain shortens by the difference. This is exactly why bypass networks matter for recurrence-bound code, and it is why the latency that appears in the bound is the forwarding latency, not the architectural latency. A multiply with a four-cycle architectural latency but a three-cycle bypass path gives a recurrence bound of three, not four. The bypass network described in forwarding paths and load-use stalls is therefore not only a hazard-avoidance mechanism; it is a device for shortening the critical cycle of a loop.

Modulo scheduling in one paragraph

The schedule that achieves a given II is a modulo schedule: each operation is assigned a cycle within an II-cycle kernel, and iteration i’s copy of an operation executes at kernel position plus i·II. The constraint is that the assignment respects every dependence edge modulo II, and that no resource is used more than its capacity in any kernel slot. The scheduler is typically iterative: pick a candidate II, attempt the assignment, and if it fails, increase II and retry. The search is bounded because the upper bound is the II of a schedule that does not overlap iterations at all.

The output is a kernel that contains the steady-state code plus a prologue and epilogue that handle the first and last iterations, where the overlap is incomplete. The prologue’s length is proportional to the number of stages in the software pipeline, which is II-dependent, and the epilogue mirrors it. For short trip counts the prologue and epilogue can dominate, which is why compilers guard software pipelining with a trip-count test and fall back to the unpipelined loop below a threshold.

Where the model stops describing reality

The bounds above assume that latencies are fixed and that the machine starts an operation every cycle if asked. Both assumptions fail on real hardware in ways that matter for the achievable II.

Memory operations have variable latency. A load that hits in L1 has one latency, one that misses has another two orders of magnitude larger. A modulo schedule built around the hit latency will stall on every miss, and the stall is not accounted for by either bound. Compilers that pipeline loops with loads therefore either assume a conservative latency, which inflates II, or rely on prefetching to make the assumption true.

Branches inside the loop body constrain the schedule further, because a modulo schedule requires the body to be a single basic block or to be if-converted. A loop with an internal branch must be predicated or unrolled before scheduling, and predication consumes issue slots for instructions that do not execute.

Interrupts and exceptions break the assumption that the kernel is a straight line. A modulo schedule with overlapping iterations has several iterations’ worth of state live in registers and, in a software-pipelined loop, the loop counter’s meaning is offset by the stage count. Taking an interrupt in the middle requires the machine to reconstruct which iteration each register belongs to, which is why some architectures define the software-pipelined loop state explicitly and others forbid interrupts in the kernel. The precise-exception machinery described in precise exceptions and pipeline restart is what makes the reconstruction possible at all, and the cost of that reconstruction is part of the reason software pipelining is applied selectively rather than universally.

The final limit is the one the whole cluster has been building toward: a pipeline’s throughput is bounded by the dependencies in the code, and the bounds are computable. Resource limits are removable with area, latency limits are removable with faster logic or better bypassing, but a recurrence with a long critical path and a distance of one is removable only by changing the algorithm.