Before you can read the parent note Branch prediction with real understanding, you need to earn every word it uses. This page builds them one at a time, from nothing. Follow top to bottom; each block leans on the one above it.
Why the topic needs it: a branch is exactly the instruction that can set the PC to something other than "the next line". Prediction is entirely about guessing the next value of the PC. If you don't know what the PC is, nothing else makes sense.
Figure s01 — A vertical list of instructions at their addresses. Orange arrows show the normal PC→next-instruction step; a magenta curved arrow shows a taken branch bending the PC backward to a loop top; a violet arrow shows the not-taken fall-through. Question at fetch time: which arrow will we follow?
The parent note writes IF → ID → EX → MEM → WB as if you already know them. Here they are from zero. A CPU splits the work of one instruction into 5 short steps, like 5 stations on a factory line:
Figure s02 — Three instructions marching diagonally through the five stages, one cycle apart, so that at any single cycle all five stages are busy on different instructions. An orange arrow marks where instruction 1 is fetched (IF), a violet arrow where it is resolved (EX); the horizontal gap between them is the source of the whole prediction problem.
Why two separate ideas — direction and target? Because knowing a branch is taken (direction) is useless if you don't know where to (target). The parent note's BTB exists purely to supply the target; the 2-bit counter supplies only the direction. Keep these two words apart in your head.
Figure s03 — A branch followed by two greyed-out "wrong-path" instructions crossed out in magenta (the flush), leaving two bubbles, and finally the correct next instruction in orange. The annotation shows the penalty c equals the number of flushed instructions (here 2).
Why the topic needs these: the whole cost of a wrong guess is measured in flushed instructions = bubbles = wasted cycles. When the parent says "misprediction penalty c", it literally means how many instructions get flushed — which equals how many stages sit between IF and EX. See Pipelining and Hazards for the family of hazards this belongs to.
The 2-bit predictor is a "state machine." Both words, from zero:
Figure s04 — The four states 00,01,10,11 drawn as circles left to right. Orange arrows (labelled "Taken → increment") push rightward and self-loop at 11; violet arrows (labelled "Not-taken → decrement") push leftward and self-loop at 00. The two right circles predict Taken (top bit 1), the two left predict Not-taken (top bit 0).
The parent calls the BTB "a small cache". From zero:
Why the topic needs it: the BTB (Branch Target Buffer) is a cache indexed by a branch's PC. Its tag confirms the entry is for this branch; its payload is the predicted target address so fetch can jump instantly in the IF stage. If caches feel new, see Caches and Locality.
Read it top-down: an instruction needs a PC; the PC feeds the pipeline; the pipeline plus branches create the hazard; the hazard plus cycle-counting give CPI; CPI plus the three fractions give the cost formula; state machines and caches then give the two fixes. All arrows converge on the topic.
Cover the right side and answer each; reveal to check.
What the PC holds
the address of the next instruction to fetch
Why we write PC ← PC+1 not PC+4
"+1" is an abstraction meaning "next instruction"; real PCs are byte addresses and step by the instruction's size
The five pipeline stages in order
IF, ID, EX, MEM, WB
Where a branch is fetched vs where it is resolved
fetched at IF, resolved at EX — that gap is the whole problem
"Taken" vs "target"
taken = the direction (did it jump?); target = the address it jumps to
What a flush / bubble costs
wasted cycles = the misprediction penalty c
Ideal CPI of a perfect pipeline
1 (one instruction finished per cycle)
Meaning of f, p, c
fraction of branches, probability of misprediction, cycles lost per miss
Why we multiply f⋅p⋅c
chained "how often × how often × how much" = average waste per instruction
Which outcome increments the 2-bit counter
a Taken outcome increments (up), a Not-taken decrements (down), both saturating at the ends
What "saturating" gives the 2-bit counter
inertia — it takes two surprises to flip the prediction
What a BTB stores that a counter does not
the target address (plus a tag), so a taken branch costs 0
What happens on a BTB miss
no stored target, so fetch falls through sequentially (predict not-taken); if it was really taken, pay c and install the entry for next time
Recall Quick self-test before moving on
If you can explain each checklist item out loud without peeking, you're ready for the parent note.
Which idea would you revisit if the formula CPI=1+f⋅p⋅c felt mysterious? ::: the "why multiply" intuition in section 6
