The hazard that forwarding cannot fix
In the last guide, forwarding rescued most data hazards by routing a freshly computed result straight to the instruction that needs it, and a single bubble handled the one load-use case forwarding could not. Branches are different in kind. A branch like beq x5, x0, target does not produce a value some later instruction is waiting for — it decides which instruction should be fetched next at all. That is a control hazard, and no amount of wiring results around the pipeline can fix it, because the problem is not a missing value but a missing decision.
Here is the awkward timing. In the classic five-stage pipeline — fetch, decode, execute, memory, write-back — the program counter grabs a new instruction every single cycle. But beq compares two registers in the execute stage and only then computes the branch target. By the time the machine knows whether to jump, fetch has already pulled in the next instruction or two from the fall-through path — instructions that may be completely wrong if the branch is taken. The fetch stage cannot wait politely; the pipeline's whole speed comes from never letting fetch sit idle.
Stall, flush, or guess
The simplest honest fix is to stall: when fetch sees a branch, freeze fetching until the branch resolves, then start again from the correct address. It is always correct, but it inserts a stall of one to three cycles on every branch, taken or not. Since branches are roughly one instruction in five or six in real code, paying a few wasted cycles each time wrecks throughput. The whole point of pipelining was to keep the line full; stalling on every branch empties it again and again.
So real machines do something bolder: they guess and keep fetching. A branch predictor is exactly the bet on which fork in the road you will take from the analogy. The pipeline picks a direction — say, assume not-taken and keep fetching straight ahead — and lets those guessed instructions flow in. This is a small act of speculative execution: the machine runs ahead on a hunch, holding back the commit until it knows the guess was right. If the guess holds, the branch cost nothing — fetch never paused. If the guess was wrong, the machine must undo the damage.
Undoing a wrong guess is a flush. When the branch finally resolves in execute and the guess turns out wrong, the machine throws away the wrongly fetched instructions still sitting in the early pipeline stages — it turns them into bubbles before they can write any register or memory — and restarts fetch from the correct target. That is a pipeline flush. Crucially, those flushed instructions never committed, so the program's visible result is exactly as if they had never run; only time was lost. The cost of one misprediction is the number of useful cycles thrown away, often called the branch (or misprediction) penalty.
How a predictor actually guesses well
A coin-flip predictor would be right half the time — not good enough. The trick is that branches are extremely repetitive: a loop's back-edge branch is taken on every iteration but the last, so 'whatever this branch did last time, it will probably do again' is a startlingly good rule. The cheapest dynamic predictor keeps one bit per branch — taken or not-taken last time — and bets the same way next time. It is right on almost every loop iteration, missing only when the loop exits.
But a one-bit scheme is brittle: a loop that runs 1000 times mispredicts twice per full execution — once on the last iteration (it guesses taken, but the loop exits) and again on re-entry the next time the loop runs (it is still stuck on not-taken). The classic fix is the two-bit predictor: a tiny saturating counter that needs two wrong guesses in a row before it changes its mind. One unusual iteration no longer flips the prediction, so a long loop mispredicts only once, on exit. This one extra bit of hysteresis is one of the best cost-to-benefit trades in all of microarchitecture.
two-bit saturating counter (one per branch)
11 strongly taken --(not taken)--> 10
10 weakly taken --(not taken)--> 00
01 weakly not-tkn --(taken)-----> 11
00 strongly not-tkn --(taken)-----> 01
predict TAKEN if the top bit is 1; one stray
outcome only nudges the counter, it does not flip
the prediction. Two misses in a row are needed
to cross from 'taken' to 'not-taken'.Two more pieces complete the picture. Knowing a branch is taken is useless if you do not know where to — and the target is not computed until late. A branch target buffer caches each branch's recent target address keyed by its instruction address, so fetch can leap to the predicted target the same cycle it fetches the branch, with no stall at all. And to squeeze the last percent, a tournament predictor runs several predictors at once — one tuned for local per-branch history, one for global patterns across recent branches — plus a meta-predictor that learns which one to trust for each branch. Modern cores predict the vast majority of branches correctly, which is precisely why deep pipelines are worth building.
What this does to CPI — a worked count
A perfectly full pipeline retires one instruction per cycle, so its ideal CPI is 1. Every stall and every flush adds wasted cycles, pushing the real number up; the realistic figure is the effective CPI. Let us count it for branches. Suppose 20% of instructions are branches, a misprediction costs a 3-cycle penalty (three instructions flushed), and the predictor is right 90% of the time. The extra CPI from branches is: fraction of branches x misprediction rate x penalty = 0.20 x 0.10 x 3 = 0.06. So effective CPI is about 1.06 — branches cost only 6% over ideal.
Now watch how brutal a bad predictor would be. Keep everything the same but drop accuracy to 50% (a coin flip): 0.20 x 0.50 x 3 = 0.30, an effective CPI of 1.30 — a 30% slowdown from branches alone. That is the gap between a machine with a good predictor and one without, and it explains why so much silicon is spent on prediction. The iron law (run time = instruction count x CPI x cycle time) is unforgiving: a higher CPI multiplies straight into run time, so shaving 0.24 off CPI is a real, measurable speedup with the identical program.
The honest tradeoff of going deeper
It is tempting to think a deeper pipeline is simply better. Cut the work into more, shorter stages and each stage's critical path is shorter, so the clock can tick faster — more stages, higher clock rate. That is real, and it is why pipelines grew from five stages to a dozen or twenty in aggressive designs. But there is a depth tradeoff hiding in plain sight: the misprediction penalty is the number of stages between fetch and where the branch resolves. Deepen the pipeline and you do not just clock faster — you also throw away more instructions on every wrong guess.
Put numbers on it. Our 5-stage example flushed 3 instructions per miss. A 20-stage pipeline might flush 15. Redo the bad-luck count at 90% accuracy: 0.20 x 0.10 x 15 = 0.30 of extra CPI, five times the penalty of the shallow machine for the very same misprediction rate. So a deep pipeline only pays off if its predictor is very accurate — which is exactly why prediction research and deep pipelines grew up together. Push depth too far and the rising misprediction and stall costs eat the clock-speed gain entirely; that is one of the reasons the extreme pipeline depths of the early-2000s clock-rate race were later pulled back.
Step back and see the shape of the whole rung. Pipelining raised throughput without lowering any single instruction's latency — the laundry finishes more loads per hour even though one load still takes the same wash-dry-fold time. The price was three hazards: structural (two stages wanting one resource), data (a value not ready, mostly cured by forwarding), and control (a direction not known, managed by prediction and flushing). The deepest lesson is that none of these are bugs to be eliminated — they are the inherent tension of doing many things at once, and good architecture is the art of paying for that tension as cheaply as the program's behavior allows.