Pipelining Principles

The SEQ processor is correct and almost embarrassingly wasteful. It computes one instruction through all six stages — fetch, decode, execute, memory, write-back, PC update — and only then fetches the next. While the ALU works, the instruction memory, the register file write port, and the data memory all sit idle; while the write-back happens, the ALU sits idle. At any instant five-sixths of the datapath is doing nothing. Pipelining reclaims that wasted hardware: keep every stage busy by letting it work on a different instruction than its neighbors. This lesson develops the principle in the abstract, with real delay numbers and the ceilings on the gain, before the next applies it to Y86-64.

Throughput is not latency

Two different numbers measure how fast a system runs work, and pipelining trades one for the other, so we must keep them apart.

In SEQ the two are locked together: an instruction takes one clock period, and a new one finishes every clock period, so latency $=1/\text{throughput}$. The catch is that the clock period must be long enough for the slowest instruction to crawl through all six stages in series. Pipelining breaks the lock. It does nothing to shorten any single instruction's path — latency stays the same or even grows slightly — but it lets a new instruction finish every short clock period, multiplying throughput. For a processor running a long stream of instructions, throughput is what we feel, and throughput is what pipelining buys.

The laundry analogy

Picture doing four loads of laundry, each needing wash (30 min), dry (30 min), and fold (30 min). Done strictly in series — wash, dry, fold, then start the next load — each load takes 90 minutes and four loads take six hours. But the washer, dryer, and table are three separate machines. The moment load 1 leaves the washer for the dryer, load 2 can start washing. Stagger them and after the pipeline fills, a finished load comes out every 30 minutes.

Series takes $4\times 90=360$ minutes; pipelined takes $90+3\times 30=180$ minutes: the first load's full 90, then one new load every 30-minute slot. The latency of any single load is unchanged at 90 minutes. What improved is the rate, a load every 30 minutes instead of every 90. A processor is the same story with the loads renamed instructions and the machines renamed stages.

Splitting a computation into stages

The mechanism is to take one block of combinational logic that computes the whole instruction and cut it into stages separated by registers. Each pipeline register snapshots the partial result at a clock edge and hands it to the next stage, exactly the clocked register from digital logic. Because a register isolates each stage, stage $s$ can work on instruction $i$ while stage $s+1$ works on the instruction ahead of it.

Bryant and O'Hallaron work this with concrete delays, and the numbers are worth following exactly. Take a computation that needs 300 ps of combinational logic, followed by a register that takes 20 ps to load. Unpipelined, the clock period must cover both: $300+20=320$ ps. One instruction finishes per period, so

about 3.12 billion instructions per second (GIPS), with a latency of 320 ps. Now cut the logic into three equal 100 ps stages, a register after each:

Each clock period now needs to push one instruction through one stage plus its register: $100+20=120$ ps. After the pipeline fills, an instruction completes every 120 ps, a throughput of $1/120\approx 8.33$ GIPS. But a single instruction now takes three periods to get through: latency $3\times 120=360$ ps, worse than the 320 ps we started with. The same arithmetic for a two-stage split (150 ps stages) gives a 170 ps clock. Tabulating all three:

Two lessons sit in this table. Throughput scales with stage count but never reaches the ideal: three stages give $8.33/3.12=2.67\times$, not $3\times$, because every stage pays the 20 ps register overhead. And latency creeps up with depth ($360/320=1.12\times$ for three stages), because that same overhead is paid three times per instruction. Pipelining is purely a throughput optimization.

The non-pipelined vs pipelined timing diagram

The signature picture of this whole module plots instructions down the side and clock cycles across the top, filling each cell with the stage that instruction occupies that cycle. Successive instructions form a diagonal staircase: in cycle $c$, instruction $i$ is in stage $c-i$, so the stages slide one step right per instruction.

Read the staircase: in the pipelined run, cycle 3 has I1 in stage C, I2 in stage B, I3 in stage A — three instructions in flight, every stage busy. The non-pipelined version finishes I2 at cycle 6; the pipelined version has already finished I1 (cycle 3), I2 (cycle 4), I3 (cycle 5), I4 (cycle 6). Same latency per instruction, triple the completions.

A finite stream, counted exactly

The staircase makes the steady state look like a clean $k\times$ win, but a real program is finite, and the first few and last few cycles never run full. Count a concrete run: $N$ instructions through the three 120 ps stages. The first instruction needs 3 cycles to reach stage C, and after that one instruction finishes every cycle, so the last of the $N$ finishes at cycle $N+2$. Total time $=(N+2)\times 120$ ps. The unpipelined machine takes $N\times 320$ ps.

Plug in numbers to see the fill and drain cost fade as the stream grows:

Three instructions barely break even because two of the five cycles are spent filling the pipe; a hundred instructions get within $2\%$ of the steady-state ceiling. This is why pipeline speedup is quoted for long instruction streams: the fill-and-drain overhead is a fixed $k-1$ cycles amortized over the whole run, negligible once $N\gg k$. A processor executing billions of instructions lives entirely in the flat part of that curve.

Nothing about the clock has to be clever for this to work. The registers only load on the rising edge, so signals racing through a stage's logic at different speeds cannot interfere: whatever reaches a pipeline register's input before the edge is captured, and nothing changes downstream until the edge. Running the clock slower than 120 ps would still compute correctly, just more slowly. Running it faster would capture garbage — inputs that had not finished propagating. The clocked register discipline from sequential logic is the entire control mechanism.

Limit 1: the slowest stage sets the clock

The three-stage example split 300 ps into three perfectly equal parts. Real hardware rarely cooperates. Suppose the logic divides only into chunks of 50, 150, and 100 ps — still 300 ps total. The clock period must be long enough for the slowest stage plus its register: $150+20=170$ ps. Stage A then works 50 ps and idles 120; stage C works 100 ps and idles 70. Only stage B stays busy.

Throughput drops to $1/170\approx 5.88$ GIPS — the same as an even two-stage split, even though we built three stages — and latency rises to $3\times 170=510$ ps. Unbalanced stages waste exactly what pipelining was meant to reclaim, which is why so much of real pipeline design is timing optimization: shuffling work across stage boundaries to equalize delays.

The payoff from rebalancing is worth working through, because it shows the clock is set by a single stage. Suppose 20 ps of the middle stage's logic can be moved into the first stage, turning the 50/150/100 split into 70/130/100. The clock now tracks the new slowest stage, $130+20=150$ ps:

Shaving 20 ps off the bottleneck bought $13\%$ throughput for zero extra hardware; the other two stages did not change at all. Only when every stage is equal does the clock reach its floor. The whole 300 ps of logic is unchanged in each row — the same total work — yet throughput swings by $40\%$ purely on how evenly the boundaries fall. A designer stares at exactly this table and moves logic across register boundaries until the column of stage delays is as flat as the circuit allows. The problem is stubborn because some units are indivisible. An ALU or a memory read is a single tightly coupled block; you cannot cheaply cut it into two half-delay pieces. Whichever stage inherits the biggest indivisible unit sets the clock for everyone.

Limit 2: register overhead and diminishing returns

If unbalanced stages are the first cost, the pipeline registers themselves are the second. Each register adds its 20 ps to every period, no matter how short the stage logic gets. Cut the 300 ps into six 50 ps stages and the period is $50+20=70$ ps, a throughput of 14.29 GIPS. We doubled the number of stages and gained only $14.29/8.33=1.71\times$, because the register delay is now $20/70\approx 29\%$ of every cycle. Push to $k$ stages and the period is $300/k+20$ ps: the logic term shrinks toward zero, the overhead term never budges, and throughput approaches a hard ceiling of $1/20$ ps $=50$ GIPS that no depth can pass. Meanwhile latency, $k\cdot (300/k+20)=300+20k$ ps, grows without bound.

The curve climbs fast for small $k$, then flattens; the widening gap to the dashed line is precisely the accumulated register overhead. There is a sweet spot — a handful to a couple dozen stages — past which adding stages buys almost nothing while costing area, power, and single-instruction latency. Modern processors do run deep, fifteen or more stages, but their designers fight for every picosecond of register delay and pay a further price this module has not yet named.

Limit 3: the instructions are not independent

Laundry loads are independent. Instructions are not. Everything so far assumed the items flowing through the pipeline are independent, and for a processor that assumption is false in two specific ways:

irmovq $50, %rax        # writes rax
addq   %rax, %rbx       # reads rax, writes rbx
mrmovq 100(%rbx), %rdx  # reads rbx

Each instruction here consumes a value the previous one produces: a data dependency. And control flow creates the second kind:

subq %rdx, %rbx
jne  target             # which instruction is next?

Until the jne decides, the very identity of the next instruction is unknown: a control dependency.

In SEQ, dependencies cost nothing: each instruction fully completes — its register writes land, its next-PC is computed — before the next begins, so every value is always ready. That safety came from the feedback paths that carry results from late in the datapath back to the register file and the PC at the start. Pipelining breaks exactly those paths. When the addq needs %rax, the irmovq that produces it is still two stages from writing it back; when fetch needs the next PC, the jne that determines it has not yet executed. Naively inserting pipeline registers into a system with feedback changes what it computes, which is unacceptable: the pipelined machine must honor the ISA's one-at-a-time semantics while overlapping everything it can. Making that true is the work of the next three lessons, and the penalties it forces — stalls and squashed instructions — are the third and final limit on pipeline speedup.

Two ways past the single-issue ceiling

Limit 2 fixed a ceiling: a single pipeline finishing one instruction per cycle tops out at $1/t_{\text{reg}}$, no matter the depth. Real processors blew past that ceiling with two ideas the CS:APP pipeline does not use, both worth knowing because they frame everything the rest of this module builds toward.

The first is superpipelining — cutting the pipeline far deeper than five stages so the clock period shrinks toward the register overhead. The MIPS R4000 (1991) ran an 8-stage integer pipeline; Intel's Pentium 4 Prescott (2004) reached 31 stages chasing clock frequency, splitting even a single ALU add across cycles. Prescott is also the cautionary tale: the same depth that let the clock hit nearly 4 GHz turned every branch misprediction into a 30-plus-cycle drain and made the chip infamous for heat, and Intel abandoned the deep-pipeline strategy for the wider, shallower Core architecture (Hennessy and Patterson, Computer Architecture: A Quantitative Approach, on the power wall). Depth trades latency and misprediction cost for clock rate, and past a point the trade stops paying — exactly the diminishing-returns curve above, now with power as the third axis.

The second, and the one that actually broke the one-per-cycle ceiling, is superscalar execution: replicate the stages so the processor fetches, decodes, and completes several instructions per cycle. A 4-wide superscalar has an ideal CPI of $0.25$ — impossible for any single-issue pipeline however deep. The idea entered the mainstream with the Intel Pentium (1993, two integer pipelines) and the DEC Alpha 21064, and every performance core since is superscalar. Issuing multiple instructions per cycle sharpens the dependency problem this lesson named as Limit 3: now instructions that could run together must be found and checked against each other within a single cycle. Resolving that led to out-of-order execution (Tomasulo's algorithm, IBM System/360 Model 91, 1967), which the final lesson of this module returns to. For now the takeaway is that pipelining is the first and simplest form of instruction-level parallelism, and the ceilings derived here are precisely what superpipelining and superscalar issue were invented to climb over.

The next lesson stops drawing abstract A/B/C stages and pipelines the real thing: inserting registers between the SEQ stages to build PIPE.