4.1.21 · D5Computer Architecture (Deep)
Question bank — Branch prediction — static, dynamic (2-bit predictor, BTB)
The three letters, defined before you use them
Every formula on this page rests on three quantities. Meet them first so no symbol is a stranger.
A quick shared vocabulary so nothing else below is a symbol you haven't met:
- Taken (T) = the branch jumps to its target. Not-taken (N) = execution falls through to the next sequential instruction.
- Flush / squash = throw away instructions already fetched down the wrong path.
- BTB = Branch Target Buffer, the little cache that remembers where a branch went.
- 2-bit counter states: Strongly-Taken, Weakly-Taken, Weakly-Not-taken, Strongly-Not-taken. Top bit = the prediction. The state machine looks like this:
And the BTB is just a small PC-indexed cache holding where each branch went:
True or false — justify
True or false: A perfect branch predictor would make CPI exactly 1 with no other changes.
Only if branches were the sole source of stalls — data and structural hazards and cache misses still add cycles, so CPI stays above 1 even with .
True or false: A deeper pipeline always makes prediction accuracy higher.
False — depth changes the penalty (bigger, since more stages flush), not the accuracy . Accuracy comes from the predictor's cleverness, not the pipeline length.
True or false: Static "predict not-taken" is right about half the time on average.
False — real code is loop-heavy and backward branches are taken almost always, so blanket not-taken is badly wrong on loops. That's exactly why BTFNT beats it.
True or false: The 2-bit counter needs two consecutive correct predictions to change its mind.
False — it needs two consecutive surprises (wrong-direction outcomes). One anomaly only slides Strongly→Weakly without flipping the top bit.
True or false: A BTB is needed even for correctly-predicted not-taken branches.
False — a not-taken branch's target is just the next sequential address, which fetch already has. The BTB earns its keep only for taken branches, whose target is elsewhere.
True or false: If the direction prediction is correct but the BTB missed, there is no penalty.
False for a taken branch — a BTB miss means the target isn't known in IF, so you stall/flush anyway even though the direction bit was right. Direction and target are two separate answers.
True or false: The 2-bit predictor stores whether the branch is taken; the BTB stores nothing about direction.
Roughly true in the simple model — the counter holds direction, the BTB holds the target address (plus a PC tag). In real designs the prediction bits often live inside the BTB entry, but conceptually they're distinct roles.
True or false: With a good predictor, branches become "almost free."
True — with tiny , the term shrinks to well under 1% of CPI, so branches stop hurting throughput. That's the payoff the whole mechanism exists for.
Spot the error
Spot the error: "The 1-bit predictor mispredicts a loop once — on the final exit."
It mispredicts twice per loop execution: once on the exit (bit flips to N) and again on the first iteration of the next entry (predicted N because the bit is stale). The exit poisons the next entry.
Spot the error: "10 (Weakly Taken) predicts Not-taken because its low bit is 0."
The top bit decides, and has top bit → predicts Taken. Only the high bit is the prediction; the low bit is just confidence.
Spot the error: "Deeper pipelines make prediction less important because there's more work to hide the flush."
Backwards — deeper pipelines make larger, so each miss flushes more instructions. Prediction matters more, not less, as depth grows.
Spot the error: "BTFNT predicts forward branches taken because forward means jumping ahead."
BTFNT predicts forward branches Not-taken. Forward branches are usually
if/error skips that fall through; only backward branches (loop bottoms) are predicted taken.Spot the error: "CPI = 1 + f·p·c, so raising accuracy from 90% to 98% cuts the branch penalty by 8%."
It cuts it by the ratio of values: from to is a 5× reduction of the penalty term, not 8%. The lever is directly, and it enters multiplicatively.
Spot the error: "A BTB hit guarantees the fetch continues correctly."
A hit gives the stored target, but the direction could still be mispredicted, or the target may have changed (e.g., an indirect/return branch). A hit removes the target-lookup cost, not the risk of being wrong.
Spot the error: "Since the 2-bit counter starts at Strongly-Taken, the first time it ever sees a branch it must be right."
Initial state is a guess; a branch that's actually not-taken on its first encounter is mispredicted. Cold entries cost misses until the counter warms up.
Why questions
Why does the misprediction penalty equal the number of stages between fetch and branch resolution, not the total pipeline depth?
Only instructions fetched after the branch but before it resolves are on the wrong path and must die. Stages after resolution hold correct, already-committed work.
Why does adding a second bit (hysteresis) specifically help loops rather than random branches?
Loops produce a long run of T with one N (the exit) — a predictable anomaly. The second bit ignores that single N, so the pattern's one blip no longer flips the guess. Truly random branches have no pattern for either predictor to exploit.
Why do we index the predictor and BTB by the branch's PC rather than by anything about the branch's data?
The PC is known in the IF stage — before decode reveals it's even a branch. Data (the compared values) isn't available until much later, too late to steer fetch.
Why is a taken branch potentially more expensive than a not-taken branch even when both are predicted correctly?
A correct not-taken branch just keeps fetching sequentially (free). A correct taken branch needs its target address early; without a BTB you don't have it in IF, so you'd bubble — the BTB is what makes taken cost 0.
Why does BTFNT cost exactly one misprediction per loop entry and not zero?
The loop exit is a backward branch that this one time is not-taken, but BTFNT always bets taken on backward branches. That final wrong guess is statically invisible and irreducible.
Why can two different branches "collide" in a simple predictor table, and why does that hurt?
The table is indexed by low PC bits, so two branches with the same index share an entry (aliasing). Their conflicting outcomes overwrite each other's history, dropping accuracy — the same collision idea you meet in direct-mapped caches.
Why does correct prediction matter for speculative execution and out-of-order machines even more than for a simple 5-stage pipe?
They run many instructions speculatively past a branch; a wrong guess discards a huge window of work, so the effective penalty (and the value of accuracy) is far larger than a 2-slot flush.
Edge cases
Edge case: a branch that alternates T, N, T, N, … forever — how does a 2-bit counter do?
It does badly — the counter oscillates near the middle and the top bit lags the true value, mispredicting on most flips. Alternating patterns are the 2-bit predictor's worst case; correlated/history predictors handle these.
Edge case: a loop that runs exactly once (body executes, branch immediately exits).
The single backward branch is not-taken, so BTFNT and a Strongly-Taken counter both mispredict. There's no repetition to learn from — degenerate loops defeat loop-friendly heuristics.
Edge case: the very first execution of a branch (cold start).
No history exists, so the predictor uses its initial/default state — effectively a static guess. Cold branches always risk a miss until the table warms; this is analogous to a compulsory cache miss.
Edge case: an indirect branch (target computed at runtime, e.g. a switch or virtual call).
Direction may be trivially "taken," but the target changes, so a BTB storing one target mispredicts whenever the destination differs. This needs an indirect-target predictor, not just direction bits.
Edge case: a function return — same PC, different caller each time.
The return target depends on who called, so a plain BTB entry is stale for a different caller. Real CPUs use a dedicated Return Address Stack instead of the BTB for returns.
Edge case: (a genuinely perfect predictor) in CPI .
The whole penalty term vanishes (), giving CPI from branches — branches become truly free, though other hazards may still push CPI up.
Edge case: (a straight-line kernel with no branches, e.g. after aggressive loop unrolling).
The penalty term is regardless of — no branches, nothing to mispredict. This is exactly why unrolling helps: it deletes branches, sidestepping the predictor entirely.
Edge case: a BTB with far fewer entries than the program has branches.
Entries get evicted before reuse, so many branches suffer BTB misses and pay the full taken-branch penalty. A too-small BTB reintroduces the very bubble it was built to remove.
Recall Meta-check: did you
reason, or just match yes/no? For each item above, the grade isn't the true/false — it's whether your justification matched. If you said "true" for the right pattern but the wrong reason, treat it as wrong and reread the parent section it points to.