CPU Pipelines: Throughput, Hazards, and Stalls

Two processors at the same clock frequency can differ several-fold in real work done. The reason is that frequency tells you how many cycles per second you get, not how much progress each cycle makes.

The standard accounting is:

time = instructions  x  cycles per instruction  x  seconds per cycle
                          (CPI)                     (1 / frequency)

Compilers attack the first term. Frequency attacks the third, and stopped scaling usefully once power density became the binding constraint. Nearly all of the interesting engineering for the last two decades has gone into the middle term.

CPI below 1 is the goal, and it is achievable because a core works on many instructions at once. Its reciprocal, instructions per cycle or IPC, is the number people usually quote. This cursus is about where IPC comes from and, more often, where it goes.

Executing an instruction involves several distinct jobs. The classic teaching model, from the RISC designs that Patterson and Hennessy use throughout Computer Organization and Design, splits it into five stages:

• IF instruction fetch
• ID instruction decode and register read
• EX execute or compute an address
• MEM access data memory
• WB write back to a register

Run these strictly one after another and each instruction takes five cycles. Pipelining instead keeps all five stages busy on five different instructions at once, the way a laundry keeps the washer and dryer both running.

The critical point, and the one most often stated wrongly: pipelining does not make any single instruction faster. An individual instruction still passes through five stages. What changes is that one instruction can now complete every cycle instead of every fifth cycle. Latency is unchanged, throughput improves fivefold.

At steady state every stage holds a different instruction. In the cycle shown, instruction 1 is retiring while instruction 5 is only just being fetched. Five instructions are in flight simultaneously, and from the outside the machine appears to finish one instruction per cycle. Reaching that steady state takes four cycles of fill, and draining it takes four more, which is why very short instruction sequences never see the full benefit.

Overlap is only safe when the instructions in flight are independent. When they are not, you have a hazard. There are exactly three kinds, and every pipeline complication in this lesson traces back to one of them.

• Structural hazard. Two instructions need the same hardware in the same cycle. Largely designed away in modern cores by duplicating units, which is why it gets the least attention.
• Data hazard. An instruction needs a value that an earlier, still-in-flight instruction has not produced yet.
• Control hazard. The processor does not yet know which instruction comes next, because a branch has not resolved.

Data and control hazards are the interesting two. Data hazards are mostly solved by forwarding, which we will look at next. Control hazards are solved by guessing, which is a much stranger idea and turns out to be the foundation of modern performance.

Consider two dependent instructions:

add  r1, r2, r3    ; r1 = r2 + r3
sub  r4, r1, r5    ; needs r1

The add writes r1 in its WB stage, cycle 5. The sub reads registers in its ID stage, cycle 3. Taken naively the sub would read a stale r1 and produce a wrong answer, so it would have to stall two cycles waiting.

But the value is not actually missing. It exists at the end of the add's EX stage in cycle 3, sitting in a pipeline register. It simply has not been written to the architectural register file yet.

Forwarding, also called bypassing, wires the output of EX directly back to the input of EX for the following instruction. The sub gets its operand from the bypass network rather than the register file, and the stall disappears entirely. This is why back-to-back dependent arithmetic runs at full rate on real hardware despite the textbook dependency.

Forwarding solves the arithmetic case because the value exists early enough. One case defeats it:

ld   r1, 0(r2)     ; load r1 from memory
add  r3, r1, r4    ; needs r1 immediately

A load produces its value in the MEM stage, not EX. The dependent add needs it at the start of its EX stage, which is the same cycle. Forwarding cannot send a value backwards in time, so the pipeline must insert one bubble. This is the load-use hazard, and it is the reason compilers work hard to schedule an independent instruction into the slot immediately after a load.

Note the shape of the problem, because it recurs at every level of this cursus: arithmetic is cheap and predictable, memory is neither. Here the penalty is a single cycle, and only because we assumed the load hit in the fastest cache. Lesson three is about what happens when it does not.

A conditional branch is a genuine problem for a pipeline. The condition is evaluated somewhere in the middle of the pipeline, but the very next instruction must be fetched on the cycle after the branch. The fetch stage needs an answer that does not exist yet.

Three responses are possible. Stall until the branch resolves, which costs the full distance from fetch to resolution on every branch. Execute both paths and discard one, which wastes half the work and does not compose with further branches. Or guess, proceed, and undo if wrong.

Every high-performance processor guesses. This is not a shortcut, it is structural: with branches occurring every handful of instructions in typical code, a pipeline that stalled on each one could never keep its stages full. The correctness requirement is that speculative work must be invisible until confirmed, which is why results are held back and only committed once the branch is known to have gone the predicted way.

When a prediction is wrong, everything fetched after the branch is bogus and must be discarded, and the pipeline refills from the correct address. The cost is roughly the depth of the pipeline, which is why deeper pipelines are not automatically better.

Agner Fog's measured figures, from The Microarchitecture of Intel, AMD and VIA CPUs (last updated May 2026), give the real numbers:

Fog notes for the Intel figure that the penalty "varies a lot". Treat these as the right order of magnitude rather than constants.

Put that in context. A correctly predicted branch is effectively free. A mispredicted one costs roughly what fifteen to twenty-five simple instructions would have. Prediction accuracy, not branch count, is what matters.

Take a loop with an ideal CPI of 1.0, where 20% of instructions are branches, and assume a 17-cycle misprediction penalty.

prediction accuracy 99%:
  mispredict rate = 0.20 x 0.01 = 0.002 per instruction
  added CPI       = 0.002 x 17 = 0.034
  effective CPI   = 1.034          (3.4% slower)

prediction accuracy 95%:
  mispredict rate = 0.20 x 0.05 = 0.010 per instruction
  added CPI       = 0.010 x 17 = 0.170
  effective CPI   = 1.170          (17% slower)

prediction accuracy 80%:
  mispredict rate = 0.20 x 0.20 = 0.040 per instruction
  added CPI       = 0.040 x 17 = 0.680
  effective CPI   = 1.680          (68% slower)

The lesson is how fast this degrades. Dropping from 99% to 95% accuracy sounds minor, but the penalty grows from 0.034 to 0.170 CPI, a factor of five, and at 80% it is twenty times the original. This is why an unpredictable branch on a hot path, a comparison against random data for instance, can be worth restructuring into branchless arithmetic even at the cost of more instructions.

Pipelining is not free, and the tradeoffs explain a lot of processor history.

• Deeper is not better. More stages allow a higher clock but raise the misprediction penalty proportionally. Intel's Pentium 4 pushed this hardest, and Fog records recovery there as "rarely less than 24 clock cycles" and potentially over 100. The industry retreated to moderate depths.
• Forwarding costs wires. The bypass network grows roughly with the square of the number of execution units, and it sits on the critical path.
• Speculation costs energy. Work that is discarded still consumed power. On mobile parts this is a real constraint, not an accounting detail.
• Speculation costs more than energy. Because speculative execution leaves traces in the cache even when discarded, it became a security problem as well. That is a topic in its own right, not a footnote here.

We have assumed one instruction issued per cycle throughout, so CPI bottoms out at 1.0. Real cores do considerably better than that, and the next lesson is how: issuing several instructions per cycle and executing them out of order.