Lesson 5: Branch Prediction & the Spectre Vulnerability

Opening: when the pipeline does not know which instruction comes next

Lesson 4 solved DATA conflicts between overlapping instructions in the pipeline — but there is another kind of conflict, more dangerous for THROUGHPUT: a conditional branch (BEQ, BNE) leaves the CPU not knowing WHICH instruction runs next until that branch has actually been computed (at the EX stage, i.e. 2–3 cycles AFTER IF has already fetched the following instruction). This is a control hazard — and the way modern CPUs solve it (guess first, then run speculatively) accidentally opened the most serious hardware security hole in history: Spectre.

1. Control hazards & why prediction is necessary

With a BEQ, the CPU only knows the next instruction's address FOR CERTAIN once it has computed the comparison at the EX stage (in Lesson 4's model, EX is the 3rd of the 5 stages IF-ID-EX-MEM-WB). But the pipeline has already had to FETCH (IF) the next 2 instructions in the 2 cycles immediately after — so without guessing ahead, the CPU has to STOP fetching (stall) until it knows the outcome, losing 1–3 cycles per branch (depending on which stage a given CPU resolves branches at). For a program dense with branches — every if/else, every loop — that cost adds up enormously if left unhandled.

2. Static & dynamic branch predictors: 1-bit and 2-bit saturating FSMs

Two abbreviations run through this whole section. FSM stands for finite state machine: a mechanism with only a few defined states, plus a fixed rule saying which state to move to when a given event happens in a given state. A traffic light is a three-state FSM. The branch predictors below are FSMs with 2 or 4 states, and their "event" is the actual outcome of the branch that just resolved.

BHT stands for Branch History Table: instead of using ONE predictor for the whole program, the CPU keeps a table indexed by instruction address, so every branch instruction gets its OWN predictor. That is necessary because different branches have different habits: a loop-exit branch is almost always "taken", while an error-check branch is almost always "not taken" — mixing them into one counter makes both predict worse.

The simplest approach — static prediction (always guess Not-taken, or always guess Taken) — is only about 50% right on a random branch. Dynamic prediction remembers the HISTORY of that particular branch to guess more intelligently, exploiting how strongly repetitive real loop branches are.

// 1-bit predictor: remembers ONLY the MOST RECENT outcome, and predicts the same.
function makeBranchPredictor1Bit() {
  let state = 0; // 0 = predict Not-taken (N), 1 = predict Taken (T)
  return {
    predict: () => (state === 1 ? 'T' : 'N'),
    update: (actual) => { state = actual === 'T' ? 1 : 0; },
  };
}
// Verified on the nested-loop sequence (TTTTN repeated 3 times, 15 branches):
// the 1-bit predictor gets only 9/15 = 60% right.

The 2-bit saturating predictor (a saturating counter) uses 4 states instead of 2 — a SINGLE wrong guess only nudges the state one notch along rather than flipping the prediction immediately, so it tolerates small amounts of noise far better:

// States: 0=Strongly-not-taken 1=Weakly-not-taken 2=Weakly-taken 3=Strongly-taken.
// Predict T once state >= 2. One wrong guess only nudges the state one notch, so a
// single blip does NOT flip the prediction.
function makeBranchPredictor2Bit() {
  let state = 0;
  return {
    predict: () => (state >= 2 ? 'T' : 'N'),
    update: (actual) => {
      state = actual === 'T' ? Math.min(3, state + 1) : Math.max(0, state - 1);
    },
  };
}

// BHT (Branch History Table): every branch ADDRESS gets its OWN 2-bit predictor,
// indexed by pc - different branches have different habits.
function makeBranchHistoryTable() {
  const table = new Map();
  const entryFor = (pc) => {
    if (!table.has(pc)) table.set(pc, makeBranchPredictor2Bit());
    return table.get(pc);
  };
  return {
    predict: (pc) => entryFor(pc).predict(),
    update: (pc, actual) => entryFor(pc).update(actual),
    size: () => table.size,
  };
}
// Verified on the SAME 15-branch sequence: the 2-bit predictor gets 10/15 = 66.7%
// right - better than the 1-bit one.

3. Effective CPI & the cost of a misprediction

Every WRONG guess forces the pipeline to flush the instructions it fetched down the wrong path and refetch along the right one — costing PenaltyCycles entirely wasted cycles. The effective CPI adds exactly that cost on top of the ideal CPI:

$$CPI_{eff} = CPI_{ideal} + \text{BranchFrequency} \times \text{MispredictionRate} \times \text{PenaltyCycles}$$

A realistic case: a program where 20% of instructions are branches, the predictor achieves a 10% misprediction rate, each misprediction costs 3 cycles, and the ideal CPI is $1$ — verified for real: $CPI_{eff} = 1 + 0.2 \times 0.1 \times 3 = \mathbf{1.06}$. In other words, branch mispredictions alone make the CPU 6% slower than ideal, even though only 10% of guesses are wrong — because effective CPI multiplies ALL THREE factors together (branch frequency × miss rate × penalty cycles).

function effectiveCPI(cpiIdeal, branchFrequency, mispredictionRate, penaltyCycles) {
  return cpiIdeal + branchFrequency * mispredictionRate * penaltyCycles;
}
// Verified: effectiveCPI(1, 0.2, 0.1, 3) === 1.06
// Verified: effectiveCPI(1, 0, 0.1, 3) === 1 (no branches at all -> the ideal CPI)

4. Speculative execution & the Spectre vulnerability

Having GUESSED a branch direction, a modern CPU does not merely fetch instructions — it runs them ahead of time (speculative execution) along the predicted path, including LOAD instructions that pull data from memory into the cache. If the guess was RIGHT, the results are committed normally. If it was WRONG, the CPU restores architectural state (registers, memory) exactly as if those instructions had never run — but ONE trace is NOT erased: the cache state. Data fetched speculatively REMAINS IN the cache even though the architectural result was discarded.

Spectre (disclosed in 2018) exploits exactly that trace: the attacker trains the branch predictor to force the victim CPU to SPECULATIVELY EXECUTE code that reads secret data (out of an array's bounds, say, past a bounds-check the CPU has not yet confirmed), then uses cache access timing (a cache-timing side-channel attack — measuring read latency to tell whether an address is cached) to INFER that secret value, even though the architectural result of the speculative computation was fully discarded. This is NOT an isolated software bug — it exploits the very speculation MECHANISM that every modern high-performance CPU needs in order to be fast.

// 1. Train the predictor: call the function many times with a VALID index
//    -> the predictor comes to "trust" that the bounds-check branch is TRUE
// 2. Call it again with an OUT-OF-BOUNDS index (past the real array)
//    -> the CPU PREDICTS the check is still TRUE and SPECULATIVELY reads the
//       out-of-bounds data into a register, using it to index a second array
//    -> the secret value is now part of an ADDRESS that entered the cache
// 3. When the CPU notices the misprediction it RESTORES architectural state
//    (registers and memory)
//    -> BUT the cache still holds the trace (that address is now cached)
// 4. The attacker TIMES a read of each candidate address
//    -> whichever address is fast (i.e. cached) reveals part of the secret

5. Hands-on: simulating a 2-bit branch predictor

Pick a control structure below to run BOTH the 1-bit and the 2-bit predictor at once (using the same verified engine) — a green cell is a correct guess, a red one is a misprediction, so you can compare the two predictors' real hit rates on the SAME branch sequence:

Summary

• ✅ Control hazard: the CPU only knows a branch direction for certain after EX, yet has already had to fetch the next instruction — costing 1–3 cycles per branch without prediction.
• ✅ Verified: the 1-bit predictor is 60% right on nested loops (oscillating at each loop boundary); the 2-bit saturating one reaches 66.7% (absorbing a single blip).
• ✅ A BHT keeps SEPARATE history per branch address — different branches have different habits and cannot share one predictor.
• ✅ Verified: $CPI_{eff} = CPI_{ideal} + \text{BranchFreq} \times \text{MispredictRate} \times \text{Penalty}$ — 20% branches, 10% mispredicted, a 3-cycle penalty gives 1.06, i.e. 6% slower than ideal.
• ✅ Spectre exploits the CACHE trace left behind after speculative execution is discarded — no software patch removes it completely without a performance cost.

Review quiz