Branch prediction — static, dynamic (2-bit predictor, BTB): Worked examples

This page is the drill ground for the parent note. There we built the tools: the misprediction-penalty formula $CPI = 1 + f \cdot p \cdot c$ , the BTFNT static rule, the 1-bit and 2-bit predictors, and the BTB. Here we throw every kind of input at those tools — loops that always run, loops that alternate, nested loops, cold-start tables, degenerate zero-branch code, and an exam twist — and solve each fully.

The scenario matrix

Think of every branch-prediction question as landing in one of these cells. The worked examples below are labelled with the cell(s) they cover, and together they fill every cell.

#	Cell (case class)	What makes it special	Example
A	Static, backward branch	loop bottom, BTFNT predicts taken	Ex 1
B	Static, forward branch	`if`-skip, BTFNT predicts not-taken	Ex 2
C	1-bit vs 2-bit on a long loop	hysteresis pays off (2 misses → 1)	Ex 3
D	*2-bit on an alternating* branch**	T,N,T,N… — worst case for 2-bit	Ex 4
E	Cold start / degenerate table	predictor starts in wrong state	Ex 5
F	Zero-branch / degenerate code	$f = 0$ : prediction is irrelevant	Ex 6
G	Limiting behaviour of CPI	$p \to 0$ , $p \to 1$ , $c$ deep	Ex 7
H	BTB hit vs miss	direction right but target unknown	Ex 8
I	Real-world word problem	full CPI budget of a program	Ex 9
J	Exam twist (nested loops)	inner loop re-entry confuses 1-bit	Ex 10

Example 1 — Cell A: static BTFNT on a backward branch

Worked example A loop runs

$N = 1000$ iterations. Using static BTFNT, how many mispredictions occur per full loop entry, and what accuracy $p_{correct}$ does that give for this branch?

Forecast: Guess now — is it closer to 0, 1, or 500 mispredictions? Write down your gut.

Step 1 — Classify the branch. The blt top at the loop bottom jumps backward (to a lower address). Why this step? BTFNT keys entirely off direction: backward ⇒ predicted Taken. So every iteration we guess Taken (T).

Step 2 — Count the real outcomes. A loop that spins $N = 1000$ times is Taken (T) on iterations $1..999$ (it loops back) and Not-taken (N) exactly once, on iteration $1000$ (it exits). Why this step? The only time control leaves the loop is the final compare.

Step 3 — Compare guesses to reality. We guessed T all $1000$ times. Reality: $999$ T, $1$ N. So we are wrong exactly once (the exit). Why this step? Mispredictions = places where guess ≠ outcome.

Step 4 — Accuracy. $p_{correct} = 999/1000 = 0.999$ , so $p = 0.001$ . Why this step? Accuracy is just (correct guesses)/(total guesses); with $1$ wrong out of $1000$ , $999$ are right, and the misprediction rate $p$ is the complement $1 - 0.999$ .

Verify: Sanity — a 1000-iteration loop must exit once, and BTFNT can never foresee that exit statically, so 1 miss is the irreducible floor. $999/1000 = 99.9%$ ✓. Units: mispredictions are a pure count; accuracy is dimensionless. ✓

The figure below shows the two branch directions BTFNT keys on — this backward branch (Ex 1) and the forward branch of Ex 2 — so you can see why direction alone leaks the likely outcome.

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

Reading the figure (Ex 1 side): the teal backward arrow curves from the loop bottom up to the loop top — that upward jump is what BTFNT reads as "loop, so predict Taken." It is right on all $999$ loop-backs and wrong only at the single downward exit.

Example 2 — Cell B: static BTFNT on a forward `if`

Worked example An error check

if (rare_error) handle(); compiles to a forward branch that skips handle(). The error fires $2%$ of the time. What is BTFNT's misprediction rate on this branch?

Forecast: Higher or lower than $2%$ ? Guess.

Step 1 — Classify. Skipping code forward ⇒ forward branch ⇒ BTFNT predicts Not-taken (N), i.e. fall through to the code after the if. Why this step? Forward = "probably skip the exceptional path."

Step 2 — Map each real outcome to T or N. Here's the subtle part, spelled out. The compiler turns if (rare_error) handle(); into a branch that says "if the error flag is false, jump forward over handle()." So:

Error false ( $98%$ of the time, the common case): the branch jumps over handle() — that is actually a Taken (T) event. Wait — but BTFNT predicted N... so is the common case a miss?

Not quite: it depends which way the compiler encodes the test. Textbook BTFNT analysis uses the standard encoding where the forward branch is Taken only in the rare case. Concretely, assume the compiler emits "if error is true, branch forward to handle()" (the common handle()-is-far layout). Then:

Error false ( $98%$ ): condition fails ⇒ branch Not-taken (N) ⇒ fall straight through. BTFNT predicted N ⇒ correct.
Error true ( $2%$ ): condition holds ⇒ branch Taken (T) to handle(). BTFNT predicted N ⇒ wrong.

Why this step? We must nail down, outcome by outcome, whether "error happens" corresponds to T or N — that mapping is the whole example, and the figure below draws exactly this fall-through-vs-jump split.

Step 3 — Rate. Mispredict exactly when the error fires: $p = 0.02$ .

Verify: BTFNT is right on the $98%$ common case (falls through, N), wrong on the $2%$ rare case (jumps to handle, T) → $p = 0.02$ , matching the error frequency. This is why forward-not-taken is a good bet: exceptional paths are rare. ✓

Reading the figure (Ex 2 side): the orange forward arrow points down to the handle() block — that jump only happens on the rare $2%$ error. BTFNT predicts Not-taken (N), staying on the straight fall-through path, correct on the $98%$ common case.

Example 3 — Cell C: 1-bit vs 2-bit on a long, repeatedly-entered loop

Worked example A loop of length

$L = 4$ is entered 3 separate times (say inside an outer routine called thrice). Compare total mispredictions of a 1-bit predictor vs a 2-bit saturating counter, both starting in a "predict Taken" state.

Forecast: Which predictor wins, and by how many misses total?

Step 1 — Lay out the outcome stream. Each entry produces T,T,T,N (three loop-backs then one exit). Three entries: TTTN TTTN TTTN (12 outcomes). Why this step? You cannot count mispredictions without the exact taken/not-taken sequence.

Step 2 — Trace the 1-bit predictor. One bit = "predict same as last outcome." It predicts T until surprised. On each entry it mispredicts the exit N (bit was T), then flips to N. The re-entry T is now mispredicted (bit says N), then flips back to T. So each entry after the first costs 2 misses (exit + re-entry); the very first entry costs only 1 (no prior re-entry to fumble). Total $= 1 + 2 + 2 = 5$ . Why this step? The 1-bit predictor's single bit erases its memory after one surprise — see the parent's "loop mispredicts twice" trap.

Step 3 — Trace the 2-bit counter (start $11$ ). Within an entry: T,T,T keep it at $11$ ; the exit N does $11 \to 10$ — top bit still $1$ , still predicts Taken, so it counts as 1 miss but re-entry stays correct. Re-entry T does $10 \to 11$ . So each entry costs exactly 1 miss (the exit only). Total $= 1 + 1 + 1 = 3$ . Why this step? The second bit is inertia: one surprise cannot flip the guess.

Step 4 — Compare. 1-bit: 5 misses. 2-bit: 3 misses. The 2-bit saves 2 misses across 3 entries.

Verify: Per entry, 2-bit hits the theoretical floor of 1 (unavoidable exit). 1-bit costs floor $+ 1$ on every re-entry ( $2$ except the first). $5 > 3$ ✓.

The figure below walks one full entry (T,T,T,N) step by step, plotting both predictors on the same state axis so you can watch the 1-bit line collapse to Not-taken on the exit while the 2-bit line only slips one notch.

Reading the figure: follow the teal line (2-bit state $00..11$ ). It rides along $11$ (top region = "predict Taken", shaded teal), and the exit N only nudges it $11 \to 10$ — still inside the Taken region, so re-entry is safe. The orange dashed line (1-bit, drawn scaled) drops all the way into the Not-taken region on the exit, so its very next re-entry T is a fresh miss. The two purple "outcome" labels along the top mark where each predictor is tested.

Example 4 — Cell D: the 2-bit counter's worst case (alternating branch)

Worked example A branch alternates perfectly: T,N,T,N,T,N,… (e.g. a "process every other element" flag). Starting the 2-bit counter at

$10$ (Weakly Taken), what is its misprediction rate in steady state?

Forecast: Better or worse than a coin flip ( $50%$ )?

Step 1 — Trace it. Start $10$ (predict T). Outcome N (wrong) → decrement $10 \to 01$ . Now $01$ predicts N. Outcome T (wrong) → increment $01 \to 10$ . Now $10$ predicts T. Outcome N (wrong) → $10 \to 01$ … Why this step? We must watch whether the counter ever "locks on."

Step 2 — Spot the cycle. It oscillates $10 \leftrightarrow 01$ , and on the alternating stream T,N,T,N it is wrong every single time. Why this step? The stream flips faster than the counter's 2-step inertia can adapt; the middle two states never saturate.

Step 3 — Rate. $p = 1.0$ (100% wrong) in this pathological case. A pure 1-bit predictor would also be $100%$ wrong here.

Verify: This is the textbook worst case for local counters and is exactly why real CPUs add history/correlating predictors (tracking recent patterns) — see Speculative Execution. Even a coin flip would beat this at $50%$ . The lesson: 2-bit inertia helps steady branches and hurts on perfect alternation. ✓

The figure shows the counter trapped in the two middle states, never reaching either "Strongly" corner — the visual signature of "wrong every step."

Reading the figure: the four states are drawn as boxes left-to-right ( $00, 01, 10, 11$ ). The plum arrows show the actual trajectory: it ping-pongs only between the two middle boxes $01$ and $10$ , never touching the shaded "Strongly" ends. Because the prediction (top bit) flips exactly out of phase with the outcomes, every test is a red ✗.

Example 5 — Cell E: cold start, table in the wrong state

Worked example A loop of length

$L = 5$ runs once. The 2-bit counter for its branch happens to boot at $00$ (Strongly Not-taken) because another branch aliased that table entry. How many mispredictions?

Forecast: Will the counter recover before the loop ends?

Step 1 — Outcome stream. One run of a length-5 loop = T,T,T,T,N (four loop-backs, one exit).

Step 2 — Trace from $00$ .

Outcome T: predict N (top bit 0) → wrong; $00 \to 01$ .
T: predict N → wrong; $01 \to 10$ .
T: predict T (top bit 1) → correct; $10 \to 11$ .
T: predict T → correct; stays $11$ .
N (exit): predict T → wrong; $11 \to 10$ .

Why this step? Cold/aliased entries force the predictor to "warm up" — it must climb two steps before its guess even points the right way.

Step 3 — Count. Mispredicts on outcomes 1, 2, and 5 → 3 misses out of 5.

Verify: If instead it had booted at $11$ (correct warm state) it would miss only the exit → 1 miss. The extra 2 misses are pure cold-start / aliasing tax. This is why bigger BTBs and tagged tables (fewer aliases) matter — connects to Caches and Locality. ✓

The figure plots the counter climbing out of $00$ : two wrong guesses while it warms up, then correct, then the unavoidable exit miss.

Reading the figure: the teal staircase starts in the bottom (Not-taken) region and climbs one step per Taken outcome. The first two markers sit in the orange "predict Not-taken" band → both are ✗ (wrong direction). Only once the line crosses into the teal "predict Taken" band do guesses turn ✓; the final drop is the exit miss.

Example 6 — Cell F: degenerate code with no branches ( $f = 0$ )

Worked example A tight numeric kernel is fully

loop-unrolled so it contains straight-line code with zero conditional branches ( $f = 0$ ). It has predictor accuracy $90%$ on paper. What is its branch-CPI overhead?

Forecast: Does the $90%$ accuracy matter at all?

Step 1 — Apply the formula. $extra CPI = f \cdot p \cdot c$ . Here $f = 0$ . Why this step? We test the degenerate input directly.

Step 2 — Evaluate. $0 \cdot p \cdot c = 0$ for any $p$ and $c$ . The $90%$ accuracy is multiplied away.

Step 3 — Interpret. With no branches there is nothing to mispredict; $CPI = 1 + 0 = 1$ . Why this step? Confirms the formula degrades gracefully at the boundary.

Verify: This is the mechanism behind Loop Unrolling — you delete branches so $f$ drops, making prediction irrelevant. But beware: unrolling costs instruction-cache space, so it trades a branch problem for a Caches and Locality problem. Overhead $= 0$ ✓.

Example 7 — Cell G: limiting behaviour of $CPI = 1 + f p c$

Worked example Fix

$f = 0.2$ , $c = 20$ (a deep modern pipeline, 20 flush slots). Compute CPI at the limits $p = 0$ , $p = 0.05$ , and $p = 1$ . What does each limit mean?

Forecast: How much does a deep pipeline punish a bad predictor?

Step 1 — Perfect predictor $p = 0$ . $CPI = 1 + (0.2) (0) (20) = 1$ . Why: zero misses ⇒ pipeline never flushes ⇒ ideal. This is the floor.

Step 2 — Realistic $p = 0.05$ . $CPI = 1 + (0.2) (0.05) (20) = 1 + 0.2 = 1.2$ . Why: even a good $95%$ predictor costs $20%$ when $c$ is large — deep pipelines amplify every miss.

Step 3 — Worst case $p = 1$ . $CPI = 1 + (0.2) (1) (20) = 1 + 4 = 5$ . Why: always wrong ⇒ every branch pays the full 20-cycle flush ⇒ the CPU crawls at 5× the ideal cycle count. This is the ceiling for these fixed $f, c$ .

Verify: The three values $1, 1.2, 5$ are monotonically increasing in $p$ , as they must be (CPI is linear in $p$ with positive slope $f c = 4$ ). Slope check: from $p = 0$ to $p = 1$ , CPI rises by $4$ , i.e. $5 - 1 = 4$ ✓. This is why Pipeline Depth and CPI and prediction quality are inseparable — see also Out-of-Order Execution which hides some of this cost. ✓

The figure draws CPI as a straight line against $p$ for the deep ( $c = 20$ ) and a shallow ( $c = 2$ ) pipeline, so the steeper slope of the deep pipeline visually equals "misses hurt more."

Reading the figure: two straight lines both start at CPI $= 1$ when $p = 0$ (perfect predictor, left edge). The orange deep-pipeline line ( $c = 20$ ) climbs steeply to $5$ at $p = 1$ ; the teal shallow line ( $c = 2$ ) barely rises to $1.4$ . The three plum dots mark our computed points $p = 0, 0.05, 1$ . Steeper line = deeper pipeline = prediction matters more.

Example 8 — Cell H: correct direction, but BTB miss

Worked example A branch is correctly predicted

Taken by the 2-bit counter, but its target is not in the BTB (first time seen, so a BTB miss). Penalty $c = 2$ . What does this taken branch cost, and why isn't a right direction enough?

Forecast: Zero cost (we guessed right) or nonzero?

Step 1 — Separate the two questions. Prediction answers whether to jump (T or N); the BTB answers where to jump (the target address). Why this step? The parent stressed prediction needs two answers, and the IF stage needs the target now.

Step 2 — BTB miss consequence. On a BTB miss the target address isn't known until decode/EX computes it. So even though the direction was right (T), fetch stalled/fetched wrong-path instructions for the slots before the target was known → cost $= c = 2$ cycles. Why this step? Direction without an address can't steer the fetch unit.

Step 3 — After this pass. The BTB now records (PC, target); on the next visit it's a hit + correct direction ⇒ 0 bubble. Why this step? Shows the one-time warm-up nature of the miss.

Verify: Cost this pass $= 2$ ; cost next pass $= 0$ . Matches the parent's piecewise cost: BTB miss ⇒ $c$ , BTB hit + correct ⇒ $0$ ✓.

The figure contrasts the two fetch timelines: a BTB miss (bubble of $c$ cycles before the target is known) versus a BTB hit (target ready in IF, zero bubble).

Reading the figure: the top timeline (orange, BTB miss) shows two hatched "bubble" slots where fetch has no target yet — that is the $c = 2$ penalty. The bottom timeline (teal, BTB hit) jumps straight from the branch's IF to the target's IF with no gap. Same correct direction, wildly different cost — the BTB is what closes the gap.

Example 9 — Cell I: real-world CPI budget (word problem)

Worked example A program runs

$1 0^{9}$ instructions. Measurements: $f = 0.18$ of instructions are branches, the predictor's accuracy is $96%$ (so $p = 0.04$ ), and the misprediction penalty is $c = 3$ cycles. The base clock does 1 instruction/cycle when nothing flushes. (a) What is the effective CPI? (b) How many extra cycles (beyond ideal) does branch misprediction cost the whole run? (c) If a better predictor lifts accuracy to $99%$ , how many cycles are saved?

Forecast: Guess the extra-cycle count to the nearest ten million.

Step 1 — CPI (a). $CPI = 1 + f p c = 1 + (0.18) (0.04) (3) = 1 + 0.0216 = 1.0216$ . Why: plug the three measured quantities into the boxed formula.

Step 2 — Extra cycles (b). Extra CPI $= 0.0216$ . Over $1 0^{9}$ instructions: $0.0216 \times 1 0^{9} = 2.16 \times 1 0^{7} = 21, 600, 000$ extra cycles. Why: multiply per-instruction overhead by instruction count.

Step 3 — Improved predictor (c). New $p = 0.01$ . New extra CPI $= (0.18) (0.01) (3) = 0.0054$ ; extra cycles $= 5.4 \times 1 0^{6}$ . Savings $= 2.16 \times 1 0^{7} - 5.4 \times 1 0^{6} = 1.62 \times 1 0^{7} = 16, 200, 000$ cycles. Why: difference of the two overhead totals.

Verify: Savings should equal $f \cdot c \cdot (Δ p) \cdot 1 0^{9} = 0.18 \cdot 3 \cdot (0.04 - 0.01) \cdot 1 0^{9} = 0.54 \cdot 0.03 \cdot 1 0^{9} = 1.62 \times 1 0^{7}$ ✓. Units: (instructions)·(cycles/instruction) = cycles ✓.

Example 10 — Cell J: exam twist — nested loops fool the 1-bit predictor

Worked example Inner loop of length

$M = 3$ sits inside an outer loop that runs $K = 4$ times, so the inner branch is entered 4 separate times. Its outcome stream is TTN TTN TTN TTN. Compare 1-bit and 2-bit total mispredictions on the inner branch.

Forecast: Nested loops re-enter often — does that hurt the 1-bit predictor 4× as much?

Step 1 — Stream and structure. Each inner activation = T,T,N (two loop-backs, one exit). Four activations: 12 outcomes. Why: nesting means the inner loop is repeatedly re-entered, the exact situation that punished 1-bit in Ex 3.

Step 2 — 1-bit trace. First activation: predict T, hit, hit, then N exit misprediction (bit flips to N) → 1 miss. Every later activation: re-entry T mispredicted (bit says N) and exit N mispredicted (bit flips back to N) → 2 misses each. Total $= 1 + 2 + 2 + 2 = 7$ . Why: the single bit is wiped by each exit, so every re-entry stumbles.

Step 3 — 2-bit trace (start $11$ ). Each activation: T,T keep $11$ ; exit N does $11 \to 10$ (still predicts T) = 1 miss; next re-entry T restores $11$ . So 1 miss per activation → total $= 4$ . Why: inertia survives the single exit surprise, so re-entry is always correct.

Step 4 — Compare. 1-bit: 7 misses; 2-bit: 4 misses. The 2-bit predictor saves 3 across the nest.

Verify: 2-bit hits the floor of 1 miss/activation (4 exits are unavoidable). 1-bit adds one extra re-entry miss for each activation after the first: $4 + 3 = 7$ ✓. This is the classic reason real CPUs prefer ≥2-bit schemes for loop-heavy code — related to Pipelining and Hazards. ✓

The figure stacks the two predictors' miss patterns across all four activations, so the extra orange (1-bit re-entry) misses stand out against the steady single teal (2-bit exit) miss per activation.

Reading the figure: each of the four activation blocks shows the T,T,N outcomes as ticks. On the 1-bit row, misses (✗) land on both the exit N and the following re-entry T (except the very first block). On the 2-bit row, only the single exit N of each block is a miss. Count the ✗ marks: $7$ vs $4$ .

Recall Quick self-test — which cell is this?

"A branch alternates T,N,T,N forever; the 2-bit counter guesses wrong every time." Which matrix cell, and what's the fix? ::: Cell D (alternating worst case); fix = correlating/history predictor, not more local bits. "A fully unrolled kernel has no conditional branches; predictor accuracy is irrelevant." Which cell? ::: Cell F ( $f = 0$ , degenerate). "First visit to a taken branch: direction right, but fetch still stalls." Which cell and why? ::: Cell H — BTB miss; the target wasn't cached yet.