Branch Prediction

A control hazard arises whenever the next instruction to fetch depends on the outcome of an instruction still in flight — most commonly a conditional branch. In a simple 5-stage pipeline (IF, ID, EX, MEM, WB), the branch condition and target may not be known until the EX or MEM stage, forcing the fetch of two or three subsequent instructions to be delayed or guessed. Without any mitigation, a processor must stall until resolution, losing one bubble per branch per stage of resolution delay — a cost that grows linearly with pipeline depth.

Branch prediction replaces "wait and see" with "guess and verify." At fetch time, the processor consults a predictor to guess (a) whether the branch will be taken or not-taken, and (b) if taken, what the target address is (usually cached in a Branch Target Buffer, BTB). Instructions are fetched and executed speculatively along the predicted path. When the branch resolves (in EX or later), the actual outcome is compared to the prediction. On a match, execution continues unaffected. On a mismatch — a misprediction — all speculatively fetched instructions are squashed (flushed) from the pipeline, the predictor state is updated with the correct outcome, and fetch resumes from the correct path, incurring a penalty of several cycles. Predictors are classified as static (fixed at compile time, using no runtime feedback) or dynamic (adapting during execution using hardware that records branch history). Static schemes include predict-not-taken (assume the branch falls through), predict-taken (assume the branch is taken, common for loop back-edges), and backward-taken/forward-not-taken (BTFNT), a compiler-friendly heuristic exploiting the fact that backward branches are usually loop edges (taken) and forward branches are usually error/skip paths (not taken). Dynamic schemes range from single bits of history per branch up to sophisticated two-level adaptive predictors that correlate the current branch's outcome with the recent history of all branches, and tournament predictors that arbitrate between multiple competing sub-predictors. This taxonomy — static vs. dynamic, local vs. global history — organizes essentially every predictor shipped in real hardware, from the 2-bit counters of early RISC chips to the perceptron and TAGE predictors in today's high-end cores.

Static prediction

The cheapest scheme requires zero runtime state: always predict not-taken (fall through sequentially) or always predict taken. A slightly smarter static scheme, BTFNT, uses the branch's direction relative to the program counter, which the compiler or hardware can determine without any history: ``` function static_predict(branch_pc, target_pc): if target_pc < branch_pc: return TAKEN // backward branch: likely a loop edge else: return NOT_TAKEN // forward branch: likely a skip/error path ``` Static schemes need no hardware tables, incur no cold-start cost, and are trivially reasoned about, but they cannot adapt to a branch's actual behavior and are typically 60-85% accurate — good enough for simple, shallow pipelines but far too weak for modern designs.

Dynamic prediction: 1-bit and 2-bit counters

The simplest dynamic predictor keeps one bit per branch (indexed by low-order PC bits into a table called a Pattern History Table, PHT, or Branch History Table, BHT): 1 means "predict taken," 0 means "predict not-taken." After the branch resolves, the bit is overwritten with the actual outcome. The flaw: consider a loop that iterates 10 times, so the loop-closing branch is taken 9 times and not-taken once (on exit), then the loop is entered again later. A 1-bit predictor mispredicts twice per loop invocation — once on the very last iteration (it predicted taken, actual was not-taken) and once again on the next invocation's first iteration (it predicted not-taken, actual is taken). Every loop boundary costs two mispredictions no matter how many times the loop iterates internally. The fix is the 2-bit saturating counter, which adds hysteresis so a single anomalous outcome doesn't flip the prediction: ``` states: 00 = strongly not-taken 01 = weakly not-taken 10 = weakly taken 11 = strongly taken function update(state, outcome): if outcome == TAKEN: state = min(state + 1, 11) // saturate at strongly-taken else: state = max(state - 1, 00) // saturate at strongly-not-taken return state function predict(state): return TAKEN if state >= 10 else NOT_TAKEN ``` Now the loop-exit anomaly moves the counter from "strongly taken" (11) to "weakly taken" (10) — the prediction (taken) does not change, so no misprediction occurs on re-entry. Only two adjacent wrong outcomes in a row can flip the prediction, filtering out one-off exceptions to a branch's dominant behavior.

Correlating (two-level, global-history) predictors

A single branch's own history is not always the best predictor of its outcome — sometimes a branch's outcome correlates with the outcomes of other, recently executed branches (e.g., `if (x > 0)` followed later by `if (x <= 5)`, where the second depends on information related to the first). Two-level adaptive predictors exploit this by maintaining: 1. A Branch History Register (BHR): a shift register of the last k taken/not-taken outcomes across all (or a hashed set of) branches. 2. A Pattern History Table (PHT): an array of 2-bit counters, indexed by the BHR (globally, per address, or a hashed XOR of both — the popular gshare scheme XORs the BHR with PC bits to reduce table aliasing). ``` function predict_two_level(pc, BHR, PHT): index = hash(pc, BHR) // e.g., gshare: pc XOR BHR counter = PHT[index] return TAKEN if counter >= 10 else NOT_TAKEN function update_two_level(pc, BHR, PHT, outcome): index = hash(pc, BHR) PHT[index] = saturating_update(PHT[index], outcome) BHR = ((BHR << 1) | outcome) mod 2^k // shift in newest outcome ``` With a k-bit history register, the predictor distinguishes up to 2^k distinct recent patterns, letting it learn correlations like "branch B is taken whenever the last three branches were T, T, N." This is strictly more expressive than a per-branch counter alone, at the cost of a larger PHT (2^k entries) and a warm-up period during which the table has not yet learned the program's patterns.

Tournament (hybrid) predictors

No single predictor dominates on all branches — some are best predicted by their own local history (e.g., a branch that alternates T, N, T, N), others by global correlation. A tournament predictor runs two (or more) predictors in parallel and uses a meta-predictor (itself a saturating counter) to learn, per branch, which sub-predictor has been more reliable: ``` function tournament_predict(pc, local_predictor, global_predictor, meta_table): p_local = local_predictor.predict(pc) p_global = global_predictor.predict(pc) meta = meta_table[hash(pc)] chosen = global_predictor if meta >= 10 else local_predictor return chosen.predict(pc), p_local, p_global function tournament_update(pc, outcome, p_local, p_global, meta_table): if p_local != p_global: // only learn when they disagree if p_global == outcome: meta_table[hash(pc)] = min(meta_table[hash(pc)] + 1, 11) else: meta_table[hash(pc)] = max(meta_table[hash(pc)] - 1, 0) local_predictor.update(pc, outcome) global_predictor.update(pc, outcome) ``` This is the architecture used in the DEC Alpha 21264 and conceptually similar to predictors in many commercial cores; modern high-end designs extend the idea further with variable-length history tables (TAGE) and perceptron-based predictors, but the meta-predictor principle — learn which strategy to trust — remains central. ```pseudocode // Full fetch-time pipeline integration function fetch_stage(pc): btb_hit, target = BTB.lookup(pc) direction = predictor.predict(pc) // static or dynamic scheme if direction == TAKEN and btb_hit: next_pc = target else: next_pc = pc + instruction_size speculate(pc, direction) // tag instruction as speculative return next_pc function execute_stage(instr): if instr.is_branch: actual = evaluate_condition(instr) actual_target = compute_target(instr) if actual != instr.predicted_direction or actual_target != instr.predicted_target: flush_pipeline_after(instr) // squash wrong-path instructions redirect_fetch(actual_target if actual == TAKEN else instr.pc + size) predictor.update(instr.pc, actual) BTB.update(instr.pc, actual_target) else: predictor.update(instr.pc, actual) // reinforce correct guess ```

Space. A table-based dynamic predictor with n-bit index (2^n entries) and w-bit counters per entry costs O(2^n · w) bits — e.g., a 12-bit gshare table with 2-bit counters is 4096 × 2 bits = 1 KB, negligible next to caches. A BTB storing full target addresses for m entries costs O(m · address_width) bits. Both are constant with respect to program size; accuracy is a function of table size relative to the program's working set of distinct branch/history patterns, so bigger tables reduce aliasing (destructive interference where two different branches map to the same PHT entry) at higher hardware cost.

Time. Prediction and update are both O(1): a table index computation (hash/XOR), an array lookup, and a counter increment/decrement, all performed within a single fetch-stage cycle. This is essential — a predictor that took multiple cycles to consult would itself reintroduce the stall it is meant to eliminate.

Why 2-bit counters strictly dominate 1-bit counters (informal proof). Model a branch's true behavior as mostly-taken with rare isolated exceptions (the loop-exit case is the canonical instance). A 1-bit predictor changes its prediction after exactly one contrary outcome, so an isolated exception both (a) causes a misprediction when it occurs, and (b) causes a second misprediction on the next normal outcome, since the predictor flipped incorrectly. A 2-bit saturating counter requires two consecutive contrary outcomes to change its prediction (moving from state 11 → 10 keeps the prediction at TAKEN; only 10 → 00 or 11 → 00-in-two-steps flips it). Hence an isolated exception costs the 2-bit predictor exactly one misprediction (when the exception occurs) and zero extra mispredictions afterward, because the prediction did not change. Formally, for a Bernoulli-like sequence where contrary outcomes are rare and non-adjacent, the 2-bit scheme's misprediction count is a subset of the 1-bit scheme's, with strict inequality whenever an isolated exception occurs — proving 2-bit counters are never worse and are strictly better on any trace containing at least one isolated anomaly.

Why correlating predictors add value. Consider two branches B1: `if (x % 2 == 0)` and B2 that depends on the same `x` a few instructions later. If B1's outcome is statistically dependent on B2's (e.g., correlated through shared program state), a predictor conditioning only on B2's own past history cannot capture this dependency — its prediction is a function of B2's outcome sequence alone, ignoring information in B1. A two-level predictor whose PHT is indexed by the global history register (which includes B1's outcome) can, in principle, learn a distinct counter for each (B1-outcome, B2-context) combination, capturing correlations invisible to any local-history-only scheme. This is a strict increase in the information available to the predictor (conditioning on a strictly larger observation set), so with enough table capacity and training, correlating predictors can only match or beat local schemes — the practical cost is a larger table and a longer warm-up (more executions needed before counters converge), which is the central accuracy/hardware/warm-up tradeoff of predictor design.

Performance model. Let branch frequency be the fraction f of instructions that are branches, misprediction rate be p, and misprediction penalty be P cycles (pipeline flush cost). Then the average CPI overhead from branches is: ``` CPI_branch_overhead = f × p × P ``` For example, with f = 0.20 (1 in 5 instructions is a branch), p = 0.08 (92% prediction accuracy), and P = 15 cycles (a 15-stage pipeline flush), the overhead is 0.20 × 0.08 × 15 = 0.24 CPI added to the base pipeline CPI of roughly 1 — a 24% slowdown from branches alone. Dropping p to 0.03 (97% accuracy, a realistic gshare/tournament result) cuts the overhead to 0.20 × 0.03 × 15 = 0.09 CPI, nearly a 3x reduction in branch-induced stall cost. This linear relationship is exactly why predictor accuracy is treated as a first-class performance metric in processor design: each percentage point of accuracy is worth a proportional, and at deep pipeline depths substantial, fraction of total CPI.

Tradeoffs. Better prediction never comes free: larger tables cost silicon area and power (leakage scales with SRAM cells), longer history registers need more warm-up time (costly for short-running code or frequent context switches), and misprediction recovery logic (checkpoint/restore of register renaming state, reorder buffer entries) adds design complexity independent of the predictor itself. Predictors must also be speculation-safe: they must never be updated with unresolved or squashed outcomes in a way that corrupts state permanently, since a mispredicted branch itself produces a "fake" outcome for instructions along the wrong path that must not pollute the predictor tables.

Trace a 2-bit saturating counter through a loop executed twice, with 3 iterations each time (T, T, N pattern), starting the counter at state 01 (weakly not-taken, an arbitrary cold-start value):

Total: 6 branch executions, 3 mispredictions (steps 1, 3, 6) — steps 1 is unavoidable cold-start, and steps 3 and 6 are the loop-exit anomaly, each costing exactly one miss with no follow-on miss (compare to a 1-bit predictor, which would additionally mispredict step 4, the first iteration of run 2, because it would have flipped to NOT_TAKEN after step 3). This confirms the earlier proof sketch: the 1-bit scheme would score 4 mispredictions out of 6 on this exact trace (steps 1, 3, 4, and — tracing the 1-bit version explicitly — step 6 as well, since it flips again after each exit), a clear empirical demonstration that hysteresis saves one full misprediction per loop invocation. Now trace the pipeline-level cost. Suppose this loop sits in a 10-stage pipeline with a misprediction penalty of P = 8 cycles, and the loop body (excluding the branch) is 4 instructions long. Per run of 3 iterations: 12 body instructions + 3 branch instructions = 15 instructions, with 1 misprediction (using the 2-bit predictor, steady state after cold start). Ideal CPI (no stalls) is 1, so ideal cycles = 15. Actual cycles = 15 + (1 × 8) = 23. Effective CPI for this loop invocation = 23 / 15 ≈ 1.53 — versus the 1-bit predictor's 2 mispredictions per run (steps 3 and the re-entry flip), giving 15 + 16 = 31 cycles, CPI ≈ 2.07. The 2-bit counter delivers roughly 26% fewer cycles on this small but realistic loop-heavy trace.

Branch prediction moved from an academic curiosity to a load-bearing pillar of processor design as pipelines deepened through the 1980s and 1990s. James E. Smith's 1981 paper formalized the 2-bit saturating counter and analyzed dynamic branch prediction rigorously, becoming the reference design point for a generation of RISC and CISC implementations alike. Later work by Yeh and Patt introduced two-level adaptive predictors correlating branch history across multiple branches, and Scott McFarling's gshare scheme (global history XORed with PC) became a standard baseline still taught and benchmarked today. Tournament predictors, popularized in the DEC Alpha 21264, and later TAGE and perceptron-based predictors, pushed accuracy from the 80-90% range of early dynamic schemes toward the high-90s achieved in contemporary out-of-order cores.

Every modern general-purpose processor — x86 desktop and server chips, ARM cores in phones and laptops, RISC-V implementations, and GPU control processors — relies on branch prediction to sustain deep, wide, out-of-order pipelines. Branch mispredictions are also the entry point for a major class of security vulnerabilities: Spectre-style attacks exploit speculative execution triggered by branch prediction to leak data through microarchitectural side channels, making predictor design a topic of active security research as well as performance engineering. Compilers exploit predictor behavior indirectly through branch layout and profile-guided optimization, arranging hot paths to align with predictor-friendly patterns (e.g., favoring BTFNT-friendly loop structures). Just-in-time compilers in language runtimes (JVM, V8) similarly reorder code to help hardware predictors, and performance-critical systems code (kernels, database engines, high-frequency trading systems) is routinely profiled specifically for branch-misprediction hotspots using hardware performance counters. The recovery machinery triggered by a misprediction — squashing in-flight instructions and restoring precise architectural state — is the same machinery that underlies exception and interrupt handling, which is why understanding branch prediction is a direct stepping stone toward Exceptions and Interrupts.

Ask the tutor: How does a mispredicted branch's pipeline flush relate to how the processor handles a precise exception?