Branch prediction — static, dynamic (2-bit predictor, BTB): Visual walkthrough

Step 1 — What "pipeline" even means (the assembly line)

WHAT. A CPU does not finish one instruction before starting the next. It splits every instruction into stages and works on several instructions at once, like a car assembly line where one car is being painted while the next is being welded.

WHY. If each instruction took the whole machine to itself, most of the silicon would sit idle. Overlapping stages means (once the line is full) one instruction finishes every cycle — that is the dream we are protecting.

PICTURE. Five stages, five instructions in flight, each shifted one cycle to the right. The five stages are:

IF = Instruction Fetch — grab the next instruction from memory.
ID = Instruction Decode — figure out what it is.
EX = Execute — do the arithmetic / comparison.
MEM = Memory — read or write data memory.
WB = Write Back — store the result in a register.

Figure — Branch prediction — static, dynamic (2-bit predictor, BTB)

Step 2 — The trap: fetch must guess before execute knows

WHAT. A conditional branch (if, loop test) decides where to go next. But that decision is made in the EX stage (the comparison happens there), while IF — the stage that must pick the next address — runs two stages earlier.

WHY. IF cannot wait. Every cycle it must fetch something, or the line starves. So it fetches a guess — usually "the next instruction in memory" — and hopes.

PICTURE. Follow the branch (lavender) down the line. When it reaches EX and resolves, two younger instructions (coral) have already been fetched behind it. If the guess was wrong, those two are on the wrong path.

Step 3 — Counting the damage: the penalty $c$

WHAT. When the guess is wrong, every instruction fetched after the branch and before it resolved is on the wrong path. We flush (delete) them and restart fetch from the correct address.

WHY. Those wrong-path instructions haven't changed any registers or memory yet (they haven't reached WB), so deleting them is safe — but the cycles spent fetching them are gone.

PICTURE. Count the flushed slots. Between IF (where the branch was fetched) and EX (where it resolved) there are exactly 2 instructions to squash. That count is the penalty.

Step 4 — Not every instruction is a branch: the fraction $f$

WHAT. Only some instructions are branches. Call the fraction of all instructions that are branches $f$ (a number between $0$ and $1$ ).

WHY. The penalty $c$ only threatens us at branches. If branches are rare, even a costly penalty is diluted across all the harmless instructions between them.

PICTURE. A strip of 10 instructions; 2 of them are branches (lavender). Here $f = 2/10 = 0.2$ — one instruction in five is a branch.

Step 5 — We don't fail every branch: the probability $p$

WHAT. A predictor is usually right. Let $p$ be the probability that a branch is mispredicted (guessed wrong).

WHY. Being wrong is the only thing that costs $c$ . A correct guess costs nothing — fetch was already on the right path. So the penalty is scaled down by how often we're wrong.

PICTURE. Ten branches; the predictor got 8 right (mint) and 2 wrong (coral). Only the coral two pay the $c$ penalty. Here $p = 2/10 = 0.2$ .

Step 6 — Multiply the three: expected extra cost per instruction

WHAT. We combine $f$ , $p$ , and $c$ into the average extra cycles per instruction.

WHY multiply, not add? Because they are three independent filters stacked in sequence, and to pay the cost you must pass all three:

the instruction must be a branch → happens a fraction $f$ of the time,
and the branch must be mispredicted → a fraction $p$ of those,
and each such event costs $c$ cycles.

"AND" of independent fractions = product. That is the deep reason for the $\times$ signs.

PICTURE. A funnel: all instructions enter the top; the $f$ gate keeps only branches; the $p$ gate keeps only the wrong ones; each survivor carries a bill of $c$ cycles.

Step 7 — Add the ideal baseline: the full CPI formula

WHAT. In a perfectly-flowing pipeline, one instruction completes each cycle, so the baseline CPI (Cycles Per Instruction) is exactly $1$ . Add the branch tax on top.

WHY. CPI measures average cycles spent per finished instruction. The ideal $1$ is the assembly line at full speed; the extra term is the price of every wrong guess, smeared across all instructions.

PICTURE. A bar starting at height $1$ (the baseline, slate) with a thin slice $f p c$ stacked on top (coral). The whole bar is the real CPI.

Step 8 — Two edge cases that make the formula honest

WHAT. Plug in the extreme inputs and confirm the formula behaves sanely.

WHY. A formula you trust is one you've tested at its corners — the boring cases reveal hidden bugs in your understanding.

PICTURE. Two CPI bars side by side: the perfect predictor ( $p = 0$ ) sits flat at $1$ ; the naïve one ( $p$ large) towers above it.

The one-picture summary

Everything above compressed into a single flow: instructions stream in, three gates ( $f$ , then $p$ , each survivor multiplied by $c$ ) skim off the penalty, and it stacks on the immovable baseline of $1$ .

Recall Feynman retelling — the whole walkthrough in plain words

Picture a factory line making one gadget per second. But some gadgets are forks in the road: the line has to start building the next gadget before it knows which way this fork goes. If it guesses the wrong way, it has to scrap the two gadgets it started on the wrong path — that scrapping is the penalty $c$ , and it's exactly how many gadgets were already on the line behind the fork. Now, forks are only some of the gadgets — that share is $f$ . And a smart foreman with a notebook (the predictor) guesses right most of the time, so he's only wrong a small share $p$ . To find the average wasted time per gadget you must pass all three filters at once — it's a fork and guessed wrong and each costs $c$ — so you multiply them: $f \times p \times c$ . Stack that little waste on top of the perfect line's speed of "one per second" ( $1$ ), and you get the real speed: $CPI = 1 + f p c$ . Shrink $p$ with a good notebook and the waste almost disappears; make the line longer (bigger $c$ ) and a bad notebook becomes a disaster.