Pipelining and hazards

In the fetch–decode–execute chapter, the CPU ran each instruction from start to finish before touching the next one. That wastes most of the hardware: while the ALU computes, the fetch logic sits idle, and while the next instruction is fetched, the ALU sits idle.

Pipelining fixes this the way an assembly line does. Execution is cut into stages, each handled by its own piece of hardware, and a new instruction enters the first stage every cycle while older ones move down the line. The idea is old: IBM's Stretch (1959) already fetched instructions ahead of time into a prefetch buffer, splitting execution in two. A pipeline pushes the same split further.

The five classic stages

The standard textbook pipeline, used by early RISC processors such as MIPS, has five stages:

These are the steps of the fetch–decode–execute chapter, now given separate hardware. Tanenbaum's first pipeline example splits the work slightly differently (fetch, decode, operand fetch, execute, write back), but the principle is the same. The split above is the one most books use for hazards, because memory access has its own stage.

Between every pair of stages sits a pipeline register: a set of latches that holds one instruction's intermediate results at the clock edge. That's what lets each stage work on a different instruction.

The diagram below runs a program on the emulator, then draws each executed instruction's journey through the pipeline, with one column per clock cycle:

Read it diagonally. In cycle 5, five instructions are in flight at once: #1 is writing back, #2 is in MEM, #3 in EX, #4 in ID, and #5 is being fetched.

Latency versus throughput

Pipelining doesn't make any single instruction faster. Each one still takes five cycles from IF to WB: that's its latency. What changes is the throughput: once the pipeline is full, one instruction completes every cycle.

With n stages and a cycle time T:

• latency = n × T per instruction;
• throughput = one instruction per T;
• N instructions take N + n − 1 cycles instead of N × n.

Above, that's 6 + 4 = 10 cycles instead of 30.

Pipelining also lets the clock run faster. The datapath chapter showed that the clock period must cover the slowest path through the datapath. With pipeline registers in between, the clock only has to cover the slowest stage, which is a fraction of the whole path. The gain isn't perfect: every pipeline register adds a little delay, and the stages are never perfectly balanced.

Hazards

The ideal picture — one instruction per cycle, forever — breaks whenever an instruction can't enter the next stage on time. These situations are called hazards, and there are three kinds:

1. Structural hazards: two instructions need the same hardware in the same cycle.
2. Data hazards: an instruction needs a result that an earlier one hasn't produced yet.
3. Control hazards: the pipeline doesn't know which instruction comes next, because a branch hasn't been decided yet.

When a hazard hits, the pipeline stalls: the instruction waits in its stage, and so does everything behind it. The empty slots moving down the pipeline are called bubbles.

Structural hazards

In the diagram above, cycle 4 has instruction #1 in MEM and instruction #4 in IF. If memory had a single port, both would need it at once. This is the von Neumann bottleneck again, and it's one more reason CPUs have separate L1 instruction and data caches: the fetch and the load each get their own port.

Data hazards and forwarding

Here each instruction uses the result of the one before it — a read after write (RAW) dependence. The diagram starts with forwarding off:

Without help, add eax, eax can't read eax in ID until the previous instruction has written it in WB. The register file is written in the first half of a cycle and read in the second half, so the read can happen in the same cycle as the write, but no earlier. Each dependent instruction waits 2 cycles, marked ·.

Now switch Forwarding to on. The stalls disappear. The result of an addition exists at the end of EX, two cycles before WB. Forwarding (or bypassing) adds wires and multiplexers that feed it straight from the pipeline register back into the ALU's input for the next instruction. The register file is still written in WB, but nobody has to wait for it.

The load-use stall

Forwarding can't do everything. A load gets its value from memory at the end of MEM, one stage later than an ALU result:

Even with forwarding on, add eax, 1 has to wait 1 cycle: when it's ready for EX, the load is only just reading memory. This is the load-use hazard.

The fix doesn't need hardware: put an independent instruction between the load and its use. Compilers do this all the time, and it's called instruction scheduling:

Same instructions, same results, one cycle fewer. When optimized code seems to interleave unrelated computations for no reason, this is often why.

RAW is the only true dependence. Two other orderings — write after read (WAR) and write after write (WAW) — matter only once a CPU starts executing instructions out of order, a later chapter's topic.

Control hazards

A conditional jump is decided in EX here. By then, the fetch stage has already fetched the next two instructions in memory order. If the jump is taken, those two are on the wrong path and must be flushed:

Each taken jl leaves a wrong path row of ✕: two fetch slots thrown away. The last jl, not taken, costs nothing, because the fetch stage guessed "not taken" and was right.

Two cycles per taken branch is a lot: in typical code, a branch appears every five to seven instructions. Designers attack control hazards from several sides:

• Decide earlier. Comparing registers and computing the target in ID cuts the penalty to one cycle.
• Delayed branches. Early RISC designs like MIPS and SPARC always executed the instruction right after a branch, the delay slot, taken or not, and left it to the compiler to put something useful there.
• Predict. Guess the outcome and the target before the branch is even decoded, and only pay when the guess is wrong. This is what modern CPUs do, and it's the subject of the branch prediction chapter later in this level.

Deeper and wider

Two ways to push further:

• Deeper pipelines cut the work into more, shorter stages, so the clock can run faster. The Pentium 4 went to 20 stages, then 31. But every stage between fetch and branch resolution adds to the cost of a misprediction, and deep pipelines lost that trade-off. Current x86 cores sit somewhere around 14 to 20 stages.
• Wider pipelines — superscalar processors — start several instructions per cycle. The original Pentium (1993) had two integer pipelines, u and v. The v pipe took only simple instructions, and fixed pairing rules decided when two neighbors could go together. Today's cores can issue four to eight or more µops per cycle.

The 486 (1989) was the first x86 with a classic five-stage pipeline. Every x86 since has been pipelined, and most high-performance ones since the Pentium Pro (1995) have also been out of order.

Measuring it

The number that summarizes a pipeline's health is CPI — cycles per instruction — or its inverse, IPC. An ideal scalar pipeline reaches CPI 1. Stalls and flushes push it above 1, and superscalar cores can push it below 1.

On Linux, perf stat ./prog reports the IPC of a real run on the line insn per cycle. A low value usually means the pipeline is waiting — for memory, which the caches chapter covers, or for branches.

Takeaways

• A pipeline overlaps instructions in stages — IF, ID, EX, MEM, WB — separated by pipeline registers.
• It keeps each instruction's latency but raises throughput to up to one instruction per cycle, and it lets the clock run faster.
• Structural hazards are conflicts over hardware; split instruction and data caches remove the classic one.
• Data hazards (RAW) are mostly hidden by forwarding, except the load-use stall, which compilers hide by scheduling.
• Control hazards flush wrong-path instructions after a taken branch; early resolution, delay slots and prediction reduce the cost.