Deep Pipelines and Why More Stages Stop Paying

Pipeline depth looks like a free variable: if five stages give five times the throughput, twenty-five should give twenty-five. It does not, and the reason is that two of the costs of a stage grow with the stage count while only one of the benefits does. Latch and clock overhead subtracts a fixed amount from every stage’s useful work, so the benefit per stage shrinks as stages get shorter. The penalty for a wrong-path instruction grows with the number of stages between fetch and resolution, so the cost of every branch, exception, and cache miss grows linearly. Between the shrinking benefit and the growing cost there is a maximum, and finding it is a design calculation rather than a matter of taste.

The overhead term, in cycles and in picoseconds

Split a stage’s logic into useful combinational delay t and the cost of the register that separates it from the next stage, t_r. The register cost includes setup time, clock-to-Q delay, and the skew budget that lets the clock reach every flop in the same cycle. With n stages, the clock period is t + t_r where t is the largest stage’s logic delay, and the throughput relative to an unpipelined machine of delay n·t is the ratio (n·t) / (t + t_r).

As n grows, t falls toward zero and the ratio approaches n·t / t_r, which grows without bound only if t_r stays fixed. It does not. Shorter stages mean more flops per unit of logic, which means more clock load, larger clock distribution networks, and a larger skew budget. The skew term in t_r is roughly proportional to the physical extent of the clock tree, and the tree grows with the number of stages because each stage boundary needs its flops. A design with 30 stages spends a much larger fraction of its cycle in overhead than one with five, and the marginal stage contributes correspondingly less.

A concrete version of the arithmetic: a 500 ps path split into 5 stages of 100 ps with 20 ps of register overhead gives a period of 120 ps and a speedup of 4.2. Split the same 500 ps into 10 stages of 50 ps and the period becomes 70 ps, a speedup of 7.1, not 10. Split into 20 stages of 25 ps and the period is 45 ps, a speedup of 11.1. The returns per doubling are 4.2, 1.7, and 1.6, and each doubling costs roughly double the flops, double the clock power, and double the bypass network.

The bypass network is the term this arithmetic omits and the hardware cannot. A forwarding path from stage i to stage j spans a physical distance that grows with the stage separation, and its delay is part of the EX stage’s logic. In a deep pipeline the number of candidate sources for a bypass multiplexer grows, and the multiplexer sits on the critical path of the stage that needs it. Past some depth, adding a stage forces the bypass network to be redesigned rather than extended, and the redesign costs more than the stage saved. The complementary problem, balancing the stages that already exist, is treated in retiming and stage balancing.

The penalty term that grows with depth

Every event that discards speculative work costs the number of cycles between the fetch of the discarded instruction and the resolution of the event. That number is proportional to the pipeline depth. A branch resolved 3 stages after fetch costs 2 cycles in a five-stage machine; resolved 12 stages after fetch it costs 11.

The frequency of such events does not fall with depth, so the CPI contribution rises linearly. If branches occur once per 8 instructions with a 5 percent misprediction rate, a 3-cycle penalty contributes 0.05 × 3 / 8 ≈ 0.019 to CPI, which is invisible. A 12-cycle penalty on the same stream contributes 0.075, and if the misprediction rate is 10 percent because the deeper machine’s predictor is being asked to look further ahead, the contribution is 0.15. That is a 15 percent throughput tax paid to buy the deeper pipeline’s clock, and it must be subtracted from the speedup before the comparison means anything.

Cache misses behave the same way. A miss detected in MEM squashes everything fetched behind it. In a deep pipeline more instructions are behind it, so the refill cost includes a longer front-end restart. The same holds for exceptions, for interrupts, and for any other event that redirects fetch. Deep pipelines are efficient exactly when such events are rare, which is to say in long straight-line runs with predictable branches and cache-resident data.

Where the crossover lands

Combining the two terms gives a total time per instruction that has a minimum. Let the base CPI be 1, the branch frequency be b per instruction, the misprediction rate be m, and the resolution depth be proportional to n. Then CPI ≈ 1 + b·m·(αn) plus the fixed overhead of the clock period. Multiplying CPI by the clock period gives time per instruction, and minimizing over n gives the optimum.

The published analyses of this trade find optima in the range of roughly 8 to 20 stages for conventional superscalar designs of their eras, with the exact number depending on the branch frequency, the misprediction rate, and the ratio of latch overhead to logic delay. The point of the calculation is not the specific number but its sensitivity: the optimum moves toward fewer stages as misprediction rates rise, as latch overhead grows, and as the bypass network’s delay grows. It moves toward more stages when the logic is slow relative to the flops, which is the situation in processes where wire delay dominates gate delay.

/* Time per instruction as a function of stage count, using the two terms
   above. `logic` is the total combinational delay of the datapath, `reg`
   the per-boundary register cost, `branch_rate` branches per instruction,
   `miss_rate` mispredictions per branch, `resolve_frac` the fraction of the
   pipeline between fetch and branch resolution. */
double tpi(int n, double logic, double reg,
           double branch_rate, double miss_rate, double resolve_frac)
{
    double period = logic / n + reg;
    double cpi = 1.0 + branch_rate * miss_rate * resolve_frac * n;
    return period * cpi;                /* lower is better */
}

Evaluating this for a 1000 ps datapath, 30 ps of register overhead, one branch per ten instructions, a 5 percent misprediction rate, and branch resolution at 40 percent of the depth gives a minimum somewhere in the low teens of stages. Change the misprediction rate to 15 percent and the minimum moves toward the high single digits. Change the register overhead to 60 ps and it moves further down. The model is crude, but its shape is the reason no production design has gone far past 30 stages and most cluster in the 10-to-20 range.

The costs the model leaves out

Three real costs push the optimum shallower than the arithmetic suggests.

Power. Clocking flops costs energy proportional to the number of flops and the clock frequency. A deep pipeline has more flops and a faster clock, so both terms rise. The clock distribution network is frequently the single largest dynamic power consumer in a high-performance core, and its share grows with depth. Designs that are power-limited, which is most of them, therefore see a shallower optimum than designs that are latency-limited.

Design and verification effort. Each stage boundary is a place where a signal must be timed, a hazard must be checked, and a corner case must be verified. The number of interactions between stages grows faster than the number of stages, because a deep pipeline has more distance over which a dependency can travel and therefore more interlock conditions. A machine with 20 stages needs hazard logic that compares a consumer against many more in-flight producers, and each comparison is a place a bug can hide.

The latency floor. Throughput and latency move in opposite directions. A deeper pipeline raises throughput and raises the latency of a single instruction, because the instruction must traverse more stages. For workloads dominated by dependent chains, such as pointer chasing or a serial recurrence, latency is what matters and depth is pure loss. The recurrence-limited throughput analysis makes this quantitative.

What deep pipelines are actually for

The designs that did go deep did so for a specific reason: to raise the clock frequency when the logic between stages could not be made faster. A 30-stage design is not 30 times faster than a single-cycle one; it is perhaps three to five times faster, and it pays for that with a branch penalty of a dozen or more cycles and a latency of a dozen or more cycles per instruction.

The counter-movement is equally instructive. Designs that emphasize power efficiency and short latency have settled at shallower depths, using wider issue and more parallel execution instead of faster clocks. Both approaches buy throughput; the difference is whether the machine converts clock rate into work or issue width into work. A wide shallow machine has a smaller misprediction penalty and a smaller single-instruction latency, and it needs more execution units and a more complex scheduler. A deep narrow machine has simpler per-stage logic and a harder recovery problem.

The choice is not resolvable in the abstract. It depends on the branch behaviour of the intended workload, the process’s ratio of wire to gate delay, and the power budget. What is resolvable is that the naive argument — more stages, more throughput, proportionally — is wrong, and that the correct argument has a maximum in it.