Branch prediction (static and dynamic): Visual walkthrough

Step 1 — What a "pipeline" actually is (a car wash for instructions)

WHAT. A processor does not do one instruction start-to-finish before touching the next. It splits the work into stages, like a car wash: soap → rinse → wax → dry. While car #1 is being waxed, car #2 is already being rinsed, and car #3 is getting soaped. Nobody waits their turn to enter — they overlap.

WHY. If each stage takes one tick of the clock (we call that tick a cycle), then overlapping means a finished instruction pops out every cycle instead of every 5 cycles. That is the whole point of a pipeline: throughput.

PICTURE. In the figure, five instructions (rows) march diagonally through five stages (columns). Read a column top-to-bottom to see "who is where right now."

Figure — Branch prediction (static and dynamic)

Step 2 — Where the branch breaks the car wash

WHAT. A branch is an instruction that asks "should I jump somewhere else, or keep going straight?" — the machine version of an if. The catch: the answer is only known in the Execute stage, but Fetch needs to know the answer right now to know which instruction to grab next.

WHY. Fetch happens in cycle 1. Execute happens in cycle 3. That is a gap of cycles where Fetch is blindfolded: it has already grabbed 2 instructions before the branch even reveals which way it went. Look at the amber gap in the figure — those are instructions fetched on faith.

PICTURE. The branch sits in row 1. Its outcome is unknown until its E box (cycle 3). But rows 2 and 3 have already been fetched (cyan) before that. If the branch actually jumps elsewhere, those cyan boxes were the wrong instructions.

Step 3 — The two ways to react, and why prediction wins

WHAT. When Fetch is blindfolded it has exactly two options:

Stall — freeze Fetch until the branch resolves. Safe, never wrong, but guaranteed to waste those gap cycles every single branch.
Predict — guess a direction, fetch that way, and keep the pipeline full. Free when right; costs the flush only when wrong.

WHY. Guessing is a bet. Let the probability of guessing wrong be $P_{mispredict}$ . Then the expected wasted cycles per branch is a weighted average:

$fraction right (1 - P_{mispredict}) \times cost when right 0 + fraction wrong P_{mispredict} \times cost when wrong Penalty$

The first term vanishes (right guesses cost nothing), leaving $P_{mispredict} \times Penalty$ . That is why prediction beats stalling: as long as you are right often enough, the average cost drops far below the always-stall cost.

PICTURE. Two side-by-side timelines: "always stall" (a fixed grey gap on every branch) vs. "predict" (mostly no gap, an occasional amber flush).

correct guess costs how many cycles?

Zero — the fetched instructions were the right ones, nothing is thrown away.

wrong guess costs how many cycles?

The full branch penalty — every speculatively fetched instruction is flushed.

Step 4 — Turning "wasted cycles" into CPI

WHAT. We need a single number to measure the whole program's speed. That number is CPI = Cycles Per Instruction — on average, how many clock ticks does each instruction cost?

WHY. In a perfect pipeline, one instruction retires every cycle, so $CPI = 1$ . That is our baseline. Every branch misprediction adds extra cycles that no instruction "used productively" — so it inflates CPI above 1. CPI is the right tool (not "total time") because it isolates the per-instruction damage, independent of program length.

PICTURE. A bar starting at height 1 (the ideal), with an amber block stacked on top representing the average penalty cycles bleeding in.

$CPI = ideal: one instr per cycle 1 + the damage we now compute (extra cycles per instruction from branches)$

Step 5 — Only some instructions are branches

WHAT. Not every instruction is a branch — most are adds, loads, stores. Let $P_{branch}$ be the fraction of all instructions that are branches (say 20%, i.e. $0.20$ ).

WHY. The penalty in Step 3 was "per branch." But CPI is averaged over all instructions. So we must scale the per-branch damage down by how often branches even appear. If only 1 in 5 instructions is a branch, the branch damage is diluted across the other 4.

PICTURE. A strip of 10 instruction boxes; 2 are highlighted amber (branches), 8 are cyan (non-branches). Only the amber ones can ever cause a flush.

$extra cycles per instruction = how often an instruction is a branch P_{branch} \times how often a branch is guessed wrong P_{mispredict} \times cost of one wrong guess Penalty$

Step 6 — Assemble the full formula and plug in numbers

WHAT. Substitute Step 5 back into Step 4:

$CPI = 1 + P_{branch} \times P_{mispredict} \times Penalty$

WHY. Each factor answers one question, and multiplying them chains the questions together: how often is it a branch? → of those, how often wrong? → how expensive is a wrong one? Multiply the three probabilities-and-cost and you get the average extra cycles per instruction, sitting on top of the ideal 1.

PICTURE. The three multiplied factors as three shrinking funnels: 100% of instructions → 20% branches → 10% of those mispredict → each costs 10 cycles.

Step 7 — The degenerate cases (never leave a scenario unshown)

WHAT. Push each factor to its extreme to sanity-check the formula.

Case	Values	CPI	Reading
Perfect predictor	$P_{mispredict} = 0$	$1 + 0 = 1.0$	No wrong guesses → no damage. Ideal pipeline.
No branches at all	$P_{branch} = 0$	$1 + 0 = 1.0$	Nothing to mispredict.
Coin-flip predictor, deep pipe	$0.20 \times 0.50 \times 20$	$1 + 2.0 = 3.0$	Half wrong, huge flush → 3× slower!
Always right, any penalty	$P_{mispredict} = 0$ , Penalty $= 100$	$1.0$	Penalty is irrelevant if you never pay it.

WHY. These extremes show the formula behaves: it collapses to the ideal 1.0 exactly when there is nothing to punish, and it blows up when misprediction rate and penalty are both large. This is why modern deep-pipeline CPUs obsess over $P_{mispredict}$ — the Penalty multiplier is unforgiving when pipelines are long.

PICTURE. Three bars for three cases (perfect, moderate, coin-flip-deep) so you see CPI stretch from 1.0 up to 3.0.

The one-picture summary

The single diagram chains the whole story: ideal 1 CPI → branches occur a fraction of the time → some fraction mispredict → each misprediction flushes Penalty cycles → those cycles pile on top of the 1, giving the final CPI. Shrinking the middle funnel ( $P_{mispredict}$ , the job of every predictor in the parent note) is the only lever that a designer fully controls at runtime.

Recall Feynman retelling — say it in plain words

The processor is a factory line where an instruction moves one station per tick, so a finished one pops out every tick — that's why "1 cycle per instruction" is the dream. But a branch is a fork in the road whose signpost is only readable late on the line, while the front of the line has already grabbed the next instructions on a guess. Guess right: no harm, line stays full. Guess wrong: dump everything you grabbed since the fork — that dump is the penalty. Now, only some instructions are forks (that's $P_{branch}$ ), and only some guesses go wrong (that's $P_{mispredict}$ ), and each wrong guess dumps Penalty cycles. Multiply those three, stack them on the dream value of 1, and you have the real cost: CPI. Perfect predictor? Middle factor is zero, cost is 1, dream achieved. Coin-flip predictor on a long line? The cost balloons. The whole art of branch prediction is one thing: make the middle factor as small as you can.

See also: Superscalar Processors (many instructions per cycle multiply the cost of every flush), Cache Performance (another source of extra cycles stacked on the same CPI baseline), Compiler Optimizations (the compiler can reduce $P_{branch}$ and improve static prediction).