Branch prediction (static and dynamic): Worked examples

This is the worked-examples deep dive for Branch Prediction (Static and Dynamic). The parent note taught the machines — the static rules, the 1-bit table, the 2-bit saturating counter, correlating predictors. Here we drive every one of those machines through every situation it can meet and count the hits by hand.

Before we start, one plain-language refresher so no symbol sneaks in unexplained:

Everything below is just filling in tables of these words and dividing at the end. That is the whole game.

The scenario matrix

Every branch-prediction question is one cell of this grid. We will hit all of them.

#	Case class	What makes it special	Worked in
A	Forward branch, rarely taken	Static PNT / BTFNT wins easily	Ex 1
B	Backward branch, loop taken	Static PT / BTFNT wins; sets the ceiling	Ex 1
C	Word problem: CPI cost	Turn accuracy into real slowdown	Ex 2
D	1-bit predictor, short loop	Cold-start and exit both wrong → oscillation	Ex 3
E	2-bit predictor, short loop	Hysteresis; warm vs. cold re-entry	Ex 4
F	2-bit predictor, long loop (limit)	Accuracy → the theoretical ceiling	Ex 5
G	Degenerate: alternating T,NT,T,NT	Worst case — every predictor thrashes	Ex 6
H	Correlating predictor	Outcome depends on another branch	Ex 7
I	Zero / trivial input: loop runs 0 or 1 time	Edge of the pattern; what "cold start" means	Ex 8
J	Exam twist: aliasing (two branches, one BHT slot)	Sharing a counter corrupts both	Ex 9

(PNT = Predict-Not-Taken, PT = Predict-Taken, BTFNT = Backward-Taken-Forward-Not-Taken — all defined in the box above.)

The figures below show the two state machines we lean on repeatedly — keep them open.

Figure — Branch prediction (static and dynamic)

Worked examples

Example 1 — Static BTFNT on a real loop (cells A + B)

Worked example Statement

for (int i = 0; i < 100; i++) {   // branch L: i < 100  (backward jump)
    if (arr[i] < 0) break;        // branch F: negative?  (forward jump)
}

The array arr holds 100 values, all positive. Using BTFNT (Backward → predict Taken, Forward → predict Not-Taken), how many predictions are correct for each branch, and what is the overall accuracy?

Forecast: guess now — will the loop branch or the if branch be the more accurate one?

Step 1 — Classify each branch by direction. Why this step? BTFNT decides purely on "does the target address sit before (backward) or after (forward) the branch?" The loop's back-edge jumps up to the top → backward → predict Taken. The break jumps down/out → forward → predict Not-Taken.

Step 2 — Count the loop branch L. Why this step? The loop body runs for i = 0…99. On each of the first 99 checks the condition i < 100 is true → Taken; on the 100th check i = 100 is false → Not-Taken.

Predicted Taken every time.
Correct on the 99 Taken checks, wrong on the 1 final NT. $L accuracy = \frac{99}{100} = 0.99$

Step 3 — Count the forward branch F. Why this step? All values are positive, so arr[i] < 0 is always false → the break is Not-Taken every time. BTFNT predicted Not-Taken. It runs once per iteration, 100 times. $F accuracy = \frac{100}{100} = 1.00$

Step 4 — Combine. Why this step? Overall accuracy is total-correct over total-branches, not an average of fractions (they have different counts — but here both counts are 100). $Accuracy = \frac{99 + 100}{100 + 100} = \frac{199}{200} = 0.995$

Recall Verify

Directions: back-edge is backward, break is forward → BTFNT matches the natural bias of both. Sanity: accuracy can't exceed 1 and here $199/200 = 0.995 \leq 1$ . ✅

Example 2 — Turning accuracy into a slowdown (cell C, word problem)

Step 1 — Write the CPI penalty model. Why this step? Every instruction takes 1 cycle plus an occasional extra: only branches can misfire, and only the fraction that mispredict pay the penalty. $CPI = 1 + P_{branch} \times P_{mispredict} \times Penalty$

Step 2 — Read off the numbers. Why this step? "92% accurate" means the mispredict rate is $1 - 0.92 = 0.08$ . Don't plug 0.92 in — accuracy is the correct fraction, the penalty is paid on the wrong fraction. $P_{branch} = 0.25, P_{mispredict} = 0.08, Penalty = 8$

Step 3 — Compute. Why this step? We now substitute the three numbers into the model from Step 1 — this is where the abstract formula becomes an actual cycle count we can act on. $CPI = 1 + 0.25 \times 0.08 \times 8 = 1 + 0.16 = 1.16$

Step 4 — Convert to a slowdown. Why this step? CPI 1.16 vs ideal 1.00 means each instruction costs 16% more cycles. $Slowdown = \frac{1.16 - 1}{1} = 0.16 = 16%$

Recall Verify

Units: (branches/instr)(mispred/branch)(cycles/mispred) = cycles/instr, added to a CPI in cycles/instr — consistent. Extreme check: if accuracy were 100%, term = 0, CPI = 1 (no loss). ✅ Answer 16%.

Example 3 — 1-bit predictor on a 3-iteration loop (cell D)

Step 1 — List the actual outcomes. Why this step? 3 iterations = branch Taken 3 times (back to top), then Not-Taken once on exit → sequence T, T, T, NT.

Step 2 — Run the state machine. Why this step? Rule (see s01): predict the current bit, then set the bit to the actual outcome.

Iter	Actual	State before	Predict	Correct?	State after
0	T	0	NT	❌	1
1	T	1	T	✅	1
2	T	1	T	✅	1
Exit	NT	1	T	❌	0

Step 3 — Count. Why this step? Accuracy is correct-over-total, so we tally the ✅ rows (2) against all rows (4) — the trace only becomes a number when we do this division. $Accuracy = \frac{2}{4} = 0.50$

Step 4 — Explain the two failures. Why this step? The matrix demands we name every miss. Wrong #1 is the cold start (bit was 0). Wrong #2 is the exit (loop taken 3×, so bit was 1, but exit is NT). A 1-bit predictor pays both on every loop it exits — this is the oscillation flaw.

Recall Verify

Two misses out of four → $2/4 = 0.5$ . Every loop of length $n$ costs the 1-bit predictor exactly 2 misses (start + exit) if entered once, so accuracy $= (n - 1) / (n + 1)$ ; for $n = 3$ that's $2/4$ . ✅

Example 4 — 2-bit predictor, cold vs. warm loop (cell E)

Step 1 — First entry trace. Why this step? Rule: predict Taken iff counter $\geq 10$ (i.e. two or more in binary); increment on T (cap 11), decrement on NT (floor 00).

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	00	NT	❌	01
1	T	01	NT	❌	10
2	T	10	T	✅	11
Exit	NT	11	T	❌	10
$First-entry accuracy = \frac{1}{4} = 0.25$

Step 2 — Why so bad here? Why this step? The counter needs two taken outcomes to climb into the predict-Taken region. The loop is only 3 long, so it barely reaches 11 before exiting — the hysteresis that helps long loops hurts very short ones.

Step 3 — Re-entry trace. Why this step? The exit left the counter at 10 (Weakly Taken), not back at 00. So the counter is warm — it already predicts Taken.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	10	T	✅	11
1	T	11	T	✅	11
2	T	11	T	✅	11
Exit	NT	11	T	❌	10
$Re-entry accuracy = \frac{3}{4} = 0.75$

Recall Verify

First entry 1 correct of 4 → 0.25. Warm re-entry 3 of 4 → 0.75, single miss = the exit only. Warm start is the whole point of the 2-bit hysteresis. ✅

Example 5 — 2-bit predictor, the long-loop limit (cell F)

Step 1 — Count mispredictions. Why this step? Warm start = counter already at 11. So all 100 Taken checks are predicted Taken → 0 misses on the body. Only the exit (NT vs predicted T) misses → 1 miss.

Step 2 — Accuracy. The branch is evaluated 100 (body) + 1 (exit) = 101 times, 1 wrong. $Accuracy = \frac{100}{101} \approx 0.990$

Step 3 — Take the limit. Why this step? The matrix wants the limiting behaviour. For a loop of length $n$ with a warm predictor: $Accuracy (n) = \frac{n}{n + 1} ⟹ lim_{n \to \infty} \frac{n}{n + 1} = 1$

Step 4 — Interpret. The single exit miss is amortised over more and more correct body predictions, so accuracy climbs toward 100%. Long loops are exactly where dynamic prediction shines.

Recall Verify

$100/101 = 0.990099 \dots$ . And $n / (n + 1)$ increases monotonically to 1; e.g. $n = 1000 \to 0.999$ . ✅

Example 6 — The degenerate worst case: alternating outcomes (cell G)

Step 1 — Trace until it repeats. Why this step? Alternating data is the pathological input a saturating counter is designed to resist — so it resists learning here too.

Step	Actual	Ctr before	Predict	Correct?	Ctr after
1	T	01	NT	❌	10
2	NT	10	T	❌	01
3	T	01	NT	❌	10
4	NT	10	T	❌	01

Step 2 — Spot the cycle. Why this step? State returns to 01 after 2 steps → the pattern above repeats forever. Every prediction is wrong. $Accuracy = \frac{0}{4} = 0%$

Step 3 — Contrast with a 1-bit predictor. Why this step? A 1-bit predictor on the same stream also mispredicts every time (it always predicts what just happened, which is the opposite of next). So both give 0% — worse than random guessing (50%). This is the theoretical worst case; correlating predictors (Ex 7) are the cure.

Recall Verify

The 01 → 10 → 01 cycle repeats with 0 correct predictions → accuracy 0. Worse than 50% coin flip. ✅

Example 7 — When history matters: correlating predictor (cell H)

Worked example Statement

if (a == 2) x = 0;   // Branch B1
if (b == 2) y = 0;   // Branch B2
if (a == b)  ...      // Branch B3  <- depends on B1 and B2!

The test always uses a = b = 2, and this exact call runs twice. Compare a bimodal predictor (one 2-bit counter for B3, start 00) with a correlating predictor (a 2-bit counter per global-history pattern; the pattern is the last-two-branch outcomes B1,B2, and all its counters start 00). Trace B3 on run 1 and run 2.

Forecast: can either predictor be right on the very first execution of B3?

Step 1 — Fix B3's true outcome. Why this step? With a = b = 2: a==2 is true (B1 Taken), b==2 is true (B2 Taken), and a==b is true → B3 is Taken on both runs. So B3's outcome sequence is T, T, and the global history feeding B3 is always the pattern (B1=T, B2=T).

Step 2 — Bimodal trace (B3's own counter only). Why this step? A bimodal predictor indexes purely by B3's address, so it starts cold at 00 and can only learn B3 in isolation.

Run	Actual	Ctr before	Predict	Correct?	Ctr after
1	T	00	NT	❌	01
2	T	01	NT	❌	10

Bimodal: 0/2 correct so far — it needs two Takens just to reach the predict-Taken region, so both early runs miss.

Step 3 — Correlating trace (counter selected by history B1,B2). Why this step? The correlating predictor picks the counter tagged with the current global pattern. Both runs arrive with pattern (T,T), so both use the same (T,T) counter — its history accumulates run to run.

Run	Pattern	Actual	(T,T) Ctr before	Predict	Correct?	Ctr after
1	(T,T)	T	00	NT	❌	01
2	(T,T)	T	01	NT	❌	10

Step 4 — Answer the forecast + name the payoff. Why this step? On the very first execution of B3 both predictors miss — no predictor can know an outcome it has never seen (cold start is unavoidable). The difference appears once mixed contexts occur: if some runs had a≠b (pattern not (T,T)), the correlating predictor keeps a separate counter for that pattern, so the (T,T)-context stays cleanly trained toward Taken. The bimodal predictor blends every context into one counter, so mixed histories drag its B3 accuracy down. With a pure repeating (T,T) context, once the shared counter saturates at 11 both reach 100% — but only the correlating design survives interleaved contexts.

Recall Verify

Logic: a=b=2 ⇒ (a==2) ∧ (b==2) ∧ (a==b) all true ⇒ B1=B2=B3=Taken. First-run prediction cold at 00 = NT ≠ T ⇒ both miss run 1 (forecast answered: no). ✅

Example 8 — Trivial inputs: loop runs 0 or 1 time (cell I, degenerate)

Step 1 — Case (a), zero iterations. Why this step? The loop test is checked once, is false → NT. Cold counter 00 predicts NT, so it matches.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
test	NT	00	NT	✅	00
$Accuracy = \frac{1}{1} = 1.00$
The cold predictor matches by luck: SNT expects fall-through, and a zero-trip loop is fall-through.

Step 2 — Case (b), one iteration. Why this step? Body runs once → back-edge Taken once, then exit NT. Sequence T, NT.

Iter	Actual	Ctr before	Predict	Correct?	Ctr after
0	T	00	NT	❌	01
Exit	NT	01	NT	✅	00
$Accuracy = \frac{1}{2} = 0.50$

Step 3 — Interpret the edge. Why this step? These are the boundaries of the loop pattern. A 0-trip loop rewards the pessimistic cold state; a 1-trip loop is essentially a single unpredictable event. Neither has enough repetition for the counter to "learn" — dynamic prediction only pays off with repetition.

Recall Verify

(a) 1/1 = 1.0; (b) 1/2 = 0.5. General warm-limit formula $n / (n + 1)$ does not apply cold — these are cold-start boundary cases. ✅

Example 9 — Exam twist: BHT aliasing (cell J)

Step 1 — Show they collide. Why this step? BHT index uses low PC bits above the byte offset. Here $0 x 1000$ and $0 x 1010$ differ only in a bit outside the 2-bit index window, so both index the same counter — this is aliasing (a.k.a. destructive interference).

Step 2 — Trace the shared 1-bit state. Why this step? Each branch overwrites the bit with its own outcome, then the other branch reads that stale bit.

Step	Branch	Actual	Bit before	Predict	Correct?	Bit after
1	X	T	0	NT	❌	1
2	Y	NT	1	T	❌	0
3	X	T	0	NT	❌	1
4	Y	NT	1	T	❌	0

Step 3 — Count. Why this step? The bit is always set by the previous, opposite branch, so every prediction is inverted. $Accuracy = \frac{0}{4} = 0%$

Step 4 — The fix. Why this step? Alone, X would be 100% (always T) and Y would be 100% (always NT). Aliasing destroys both. Cures: more BHT entries (fewer collisions), or tagging entries with part of the PC to detect collisions — a real design trade-off between table size and accuracy.

Recall Verify

Isolated X: predict-then-update on a constant stream converges to 100%. Same for Y. Shared: the alternation forces the stored bit to always be the other branch's outcome → 0%. Sharing turned 100%+100% into 0%. ✅

Recall

Recall Full coverage check

Which single flaw makes a 1-bit predictor miss twice per loop? ::: cold start (first iter) and loop exit — it can't hold the "mostly taken" pattern. Why does a 2-bit predictor beat it on long loops? ::: hysteresis: one exit NT only drops it from 11 to 10, still predicting Taken, so re-entry needs no relearning. What is the warm 2-bit accuracy for an $n$ -iteration loop? ::: $n / (n + 1)$ , approaching 1 as $n \to \infty$ . What input class defeats all single-counter predictors? ::: alternating T, NT, T, NT — accuracy 0%; needs a correlating predictor. What is aliasing and why is it bad? ::: two branches mapping to one BHT slot overwrite each other's history, potentially crashing both to 0% accuracy.

Connections

Speculation only pays off because prediction is usually right — see Speculative Execution.
Fewer mispredicts = deeper usable pipelines = more Instruction-Level Parallelism (ILP) and wider Superscalar Processors.
Mispredict flushes also thrash the cache with wrong-path fetches.
Compiler Optimizations like loop unrolling and BTFNT hint placement change the branch mix a predictor sees.