Branch prediction is the hardware mechanism inside a CPU that guesses the outcome of conditional branches (if/else, loops, function returns) before the branch instruction is actually resolved — allowing the pipeline to continue fetching and executing instructions speculatively rather than stalling for 15–25 cycles while the branch condition is computed. A modern CPU pipeline is 15–25 stages deep; without prediction, every branch would create a bubble (wasted cycles) equal to the pipeline depth. With >95% prediction accuracy, the average branch penalty drops to less than 1 cycle, making deep pipelines and high clock frequencies practical.

Why branches are the enemy of pipelines. A pipelined CPU starts executing the next instruction before the current one finishes. But at a branch, the CPU doesn't know which instruction comes next until the branch condition is evaluated (which happens many stages later). Options: (1) stall and wait (wastes 15–25 cycles per branch, every 5–7 instructions → 50% of cycles wasted), or (2) predict and speculate — guess the direction, start executing, and flush the pipeline if wrong.

Branch predictor types — from simple to state-of-the-art:

The cost of misprediction. When the predictor is wrong, all speculatively-executed instructions must be flushed from the pipeline and re-fetched from the correct path. On a modern 20-stage out-of-order CPU, a misprediction costs ~15–20 cycles. With branches occurring every 5–7 instructions:

$$\text{CPI}_{\text{branch}} = \text{mispredict rate} \times \text{penalty} \times \text{branch frequency}$$

At 4% mispredict rate, 18-cycle penalty, and 1 branch per 6 instructions: CPI penalty = 0.04 × 18 / 6 = 0.12 — adding 12% to effective CPI. This is why even 1% accuracy improvement (97% → 98%) meaningfully impacts IPC.

TAGE — the dominant modern predictor. Tagged Geometric history length (TAGE) uses multiple prediction tables, each indexed by a different length of branch history (geometric series: 4, 8, 16, 32, 64, 128+ bits of history). Longer history captures correlations with distant branches; shorter history adapts faster. A tag check prevents aliasing (different branches colliding in the same table entry). TAGE achieves 96–97% accuracy and is used (in various forms) by Intel, AMD, ARM, and Apple.

Branch target buffer (BTB) — where to go. Predicting taken/not-taken is only half the problem: the CPU also needs the target address (where to jump to) before it can fetch the next instruction. The BTB caches recently-seen branch targets indexed by branch PC. For indirect branches (jump to register, virtual function calls), an indirect target predictor stores per-branch history of target addresses.

Speculative execution and security. Branch prediction enables speculative execution, which was exploited by Spectre (2018): a mispredicted branch executes instructions that load secret data into the cache; even after flush, cache timing reveals the secret. Mitigations (retpolines, IBRS, BHI) add overhead and reduce effective prediction utility — a direct tax on performance caused by the prediction mechanism itself.

<svg viewBox="0 0 760 470" xmlns="http://www.w3.org/2000/svg" font-family="-apple-system,Segoe UI,Roboto,sans-serif">
  <rect x="0" y="0" width="760" height="470" fill="#0d1117"/>
  <text x="380" y="28" fill="#e6edf3" font-size="21" font-weight="700" text-anchor="middle">Branch Prediction — Speculating the Future</text>
  <text x="380" y="48" fill="#8b98a5" font-size="12" text-anchor="middle">guess which way a branch goes before it resolves — wrong guesses flush the pipeline (15-20 cycles lost)</text>

  <!-- === TOP: Why it matters === -->
  <rect x="25" y="62" width="710" height="95" rx="6" fill="#080d14" stroke="#233043" stroke-width="1.2"/>
  <text x="380" y="80" fill="#e6edf3" font-size="11" text-anchor="middle" font-weight="600">The Branch Problem in Deep Pipelines</text>

  <text x="45" y="100" fill="#8b98a5" font-size="8.5">Every 5-7 instructions is a branch. Pipeline is 15-20 stages deep.</text>
  <text x="45" y="118" fill="#f87171" font-size="8.5" font-weight="600">Misprediction penalty:</text>
  <text x="195" y="118" fill="#8b98a5" font-size="8.5">flush all speculative work (15-20 cycles × 8-wide = 120-160 μops wasted)</text>
  <text x="45" y="136" fill="#34d399" font-size="8.5" font-weight="600">Modern accuracy:</text>
  <text x="165" y="136" fill="#8b98a5" font-size="8.5">~97-99% (TAGE+loop+indirect predictors)</text>
  <text x="45" y="150" fill="#fbbf24" font-size="8.5">Even 1% mispredict rate → ~10-15% IPC loss on deep OoO cores</text>

  <!-- === MIDDLE LEFT: Predictor types === -->
  <rect x="25" y="165" width="350" height="142" rx="6" fill="#0b1220" stroke="#233043" stroke-width="1"/>
  <text x="200" y="183" fill="#e6edf3" font-size="10" text-anchor="middle" font-weight="600">Branch Predictor Evolution</text>

  <text x="45" y="205" fill="#60a5fa" font-size="8.5" font-weight="600">2-bit saturating counter:</text>
  <text x="45" y="221" fill="#8b98a5" font-size="8.5">simple, per-branch history (bimodal, ~90%)</text>
  <text x="45" y="239" fill="#34d399" font-size="8.5" font-weight="600">Correlating (gshare):</text>
  <text x="45" y="255" fill="#8b98a5" font-size="8.5">XOR global history with PC (~93%)</text>
  <text x="45" y="273" fill="#fbbf24" font-size="8.5" font-weight="600">TAGE (TAgged GEometric):</text>
  <text x="45" y="289" fill="#8b98a5" font-size="8.5">multiple history lengths, tagged entries (~97%)</text>
  <text x="45" y="305" fill="#c4b5fd" font-size="8.5" font-weight="600">Neural / perceptron:</text>
  <text x="45" y="321" fill="#8b98a5" font-size="8.5">learned weights on history bits (AMD Zen)</text>

  <!-- === MIDDLE RIGHT: What gets predicted === -->
  <rect x="390" y="165" width="345" height="142" rx="6" fill="#0b1220" stroke="#233043" stroke-width="1"/>
  <text x="562" y="183" fill="#e6edf3" font-size="10" text-anchor="middle" font-weight="600">What Gets Predicted</text>

  <text x="410" y="205" fill="#60a5fa" font-size="8.5" font-weight="600">Direction:</text>
  <text x="480" y="205" fill="#8b98a5" font-size="8.5">taken or not taken (conditional branch)</text>
  <text x="410" y="225" fill="#34d399" font-size="8.5" font-weight="600">Target (BTB):</text>
  <text x="495" y="225" fill="#8b98a5" font-size="8.5">where does it jump to? (branch target buffer)</text>
  <text x="410" y="245" fill="#fbbf24" font-size="8.5" font-weight="600">Indirect target:</text>
  <text x="510" y="245" fill="#8b98a5" font-size="8.5">virtual calls, switch tables (polymorphic)</text>
  <text x="410" y="265" fill="#c4b5fd" font-size="8.5" font-weight="600">Return address (RAS):</text>
  <text x="550" y="265" fill="#8b98a5" font-size="8.5">call/return stack (near-perfect)</text>
  <text x="410" y="285" fill="#f87171" font-size="8.5" font-weight="600">Loop count:</text>
  <text x="490" y="285" fill="#8b98a5" font-size="8.5">how many iterations? (loop predictor)</text>
  <text x="410" y="307" fill="#6b7684" font-size="8">All must be predicted BEFORE decode even knows it's a branch</text>

  <!-- === BOTTOM: Accuracy by workload === -->
  <rect x="25" y="317" width="710" height="85" rx="5" fill="#0b1220" stroke="#233043" stroke-width="1"/>
  <text x="380" y="335" fill="#e6edf3" font-size="10" text-anchor="middle" font-weight="600">Prediction Accuracy by Workload</text>

  <text x="95" y="359" fill="#34d399" font-size="9" text-anchor="middle" font-weight="600">Loops</text>
  <text x="95" y="373" fill="#8b98a5" font-size="8" text-anchor="middle">99.9% (loop predictor)</text>
  <text x="95" y="385" fill="#6b7684" font-size="7.5" text-anchor="middle">nearly perfect</text>

  <text x="235" y="359" fill="#60a5fa" font-size="9" text-anchor="middle" font-weight="600">Server (SPEC)</text>
  <text x="235" y="373" fill="#8b98a5" font-size="8" text-anchor="middle">97-98% (TAGE)</text>
  <text x="235" y="385" fill="#6b7684" font-size="7.5" text-anchor="middle">regular patterns</text>

  <text x="380" y="359" fill="#fbbf24" font-size="9" text-anchor="middle" font-weight="600">Interpreted code</text>
  <text x="380" y="373" fill="#8b98a5" font-size="8" text-anchor="middle">92-95%</text>
  <text x="380" y="385" fill="#6b7684" font-size="7.5" text-anchor="middle">indirect calls (vtables)</text>

  <text x="530" y="359" fill="#f87171" font-size="9" text-anchor="middle" font-weight="600">Data-dependent</text>
  <text x="530" y="373" fill="#8b98a5" font-size="8" text-anchor="middle">85-90%</text>
  <text x="530" y="385" fill="#6b7684" font-size="7.5" text-anchor="middle">binary search, hash lookup</text>

  <text x="670" y="359" fill="#c4b5fd" font-size="9" text-anchor="middle" font-weight="600">Random (crypto)</text>
  <text x="670" y="373" fill="#8b98a5" font-size="8" text-anchor="middle">~50% (unpredictable)</text>
  <text x="670" y="385" fill="#6b7684" font-size="7.5" text-anchor="middle">branchless code wins</text>

  <!-- Key insight -->
  <rect x="25" y="410" width="710" height="22" rx="3" fill="#0b1220" stroke="#233043" stroke-width="0.8"/>
  <text x="380" y="425" fill="#fbbf24" font-size="9" text-anchor="middle">Branch prediction is the most important speculation: without it, a 20-stage pipeline would stall every 5 instructions.</text>

  <text x="380" y="460" fill="#6b7684" font-size="11" text-anchor="middle">Modern CPUs bet on the future and are right 97%+ of the time — speculation makes deep pipelines viable.</text>
</svg>

Branch prediction and the CFS platform. Branch prediction is what makes CPUs fast on irregular, control-heavy code — the orchestration logic that manages AI training (data loading, gradient communication, batch scheduling). The AI accelerator itself (modeled by CFS systolic-array and inference simulators) doesn't need branches because matmul is a perfectly regular loop. But the host CPU that launches kernels and manages the cluster relies heavily on prediction for its own performance — which is why high-IPC ARM (Apple M-series) and x86 (AMD Zen) cores are paired with AI accelerators in every modern system.