Pipelining from first principles

Doing laundry takes four steps: wash, dry, fold, put away. If each takes 30 minutes and you finish one load completely before starting the next, four loads take 8 hours. If you start the second wash as soon as the first load moves to the dryer, all four steps stay busy and the same four loads finish in 3.5 hours.

No single load finished faster; each still took 2 hours. What improved is throughput: once the pipeline is full, a load finishes every 30 minutes. A processor pipeline works the same way. Instruction execution is split into stages, and a new instruction enters the first stage every clock cycle while older instructions move along behind it.

The classic RISC pipeline, used in MIPS, early Arm cores and most textbook RISC-V designs, has five stages. Pipeline registers between stages (IF/ID, ID/EX, EX/MEM, MEM/WB) hold each instruction's values and control signals as it advances, so every stage can work on a different instruction in the same cycle. Every instruction passes through all five stages, even ones it does not need, which keeps the timing uniform.

The first instruction needs k cycles to fill the pipeline; after that, one instruction finishes per cycle. For long instruction streams the ideal speedup approaches k. Three things keep real pipelines below that:

• Unbalanced stages. The clock must fit the slowest stage, so faster stages sit idle for part of every cycle.
• Register overhead. Each pipeline register adds setup time and clock skew to every cycle.
• Hazards. Stalls add cycles in which no instruction finishes (Part B).

Take stage delays of 200 ps for fetch, 100 ps for register read, 200 ps for the ALU, 200 ps for data memory and 100 ps for write-back. An unpipelined design that runs one load per 800 ps cycle becomes a pipeline with a 200 ps clock, so the speedup is 800 / 200 = 4, not 5, because the two 100 ps stages waste half their cycle.

If instructions and data share one memory port, a load in MEM and a fetch in IF collide every time. Pipelined processors avoid this with separate instruction and data caches. The register file is read in ID and written in WB in the same cycle, so it is designed to write in the first half of the cycle and read in the second, or given separate read and write ports. Long operations such as floating-point division are often not fully pipelined, so two divides in a row still contend for one unit; designers accept this when the operation is rare enough.

In this sequence, sub reads x1 in ID (cycle 3), but add does not write it until WB (cycle 5):

A conditional branch in the five-stage pipeline is not resolved until EX. By then, two more instructions have already been fetched from the path that may be wrong. The simplest fix stalls fetch until the outcome is known, which costs 2 cycles on every branch. Since roughly 15 to 20% of instructions in typical integer code are branches, that alone adds 0.3 to 0.4 cycles to every instruction's average. Control hazards grow with pipeline depth, because the branch resolves further from the front.

The second formula assumes perfectly balanced stages. Suppose a five-stage pipeline with no special hazard hardware runs code in which 30% of instructions use the result of the instruction just before (2 stalls each), 10% use a result from two instructions back (1 stall each), and 15% are branches (2 stalls each):

Stalls per instruction = 0.30 × 2 + 0.10 × 1 + 0.15 × 2 = 1.0, so CPI = 2.0 and the speedup is 5 / 2 = 2.5 instead of 5. Hazards erased half the benefit of pipelining, which is why so much processor design effort goes into removing them.

A dependence is a property of the program: two instructions must keep their order to produce the right result. A hazard is a property of the pipeline: whether that dependence, at that distance, would be violated by overlapping the instructions. The same dependence can cause a hazard on one pipeline and none on another.

A program's dependences form a graph. The longest path through it, the critical path, sets a lower bound on execution time no matter how the instructions are scheduled. Compare the "Dependent chain" and "Two chains interleaved" examples: the second does twice as much work in only a few more cycles, because instructions from one chain fill the gaps left by the other.

How much independent work real programs contain was measured in limit studies. Wall found that typical programs expose only a handful of independent instructions at a time; Austin and Sohi traced dynamic dependence graphs to see where the parallelism lies; and Lam and Wilson showed that control dependences, more than data dependences, limit how much can be found. These results shaped everything from compiler scheduling to how wide processors are built.