Branch prediction and out-of-order execution

You know the classic five-stage pipeline, its hazards and CPI; if not, start with Instructions and pipelines. Its two remaining limits are control flow and latency. A modern core may have more than ten stages between choosing the next fetch address and resolving a branch, so without prediction each branch costs roughly that depth times the fetch width in lost slots.¹ And a load that misses stalls every younger instruction in an in-order machine, even the independent ones.

The out-of-order superscalar answers both with five mechanisms, which this chapter takes in turn:

1. Prediction of branch direction and target, so fetch runs ahead of execution.
2. Register renaming, so only true dataflow dependences remain.¹⁰
3. Dynamic scheduling from reservation stations or issue queues in dataflow order.²
4. In-order commit from a reorder buffer, which provides precise exceptions and mispredict recovery.¹¹
5. Memory disambiguation with load and store queues, so loads can pass stores speculatively.¹³

We use open material throughout: MIT’s graduate architecture lectures, the open-source RISC-V BOOM core and its documentation, and the Hot Chips disclosures of x86, Arm and RISC-V cores as case studies. Caches appear here only as a latency to hide; how they work is the next chapter, Caches and coherence.

Prediction has three parts: is this fetch block holding a branch, which way does it go (direction), and where does it go (target). Direction is the hard part for conditional branches; target is the hard part for indirect jumps and returns.²⁰

The cost model is simple. A mispredicted branch wastes the issue slots from its fetch to its resolution plus the refill: at least the front-end depth, and more if the branch itself waited on a cache miss, since everything fetched after it is squashed. Measured penalties: 15–20 cycles on Intel’s Haswell-through-Lake cores; about 18 on AMD Zen 1–3, 15–18 on Zen 4 and 15–25 on Zen 5.¹⁵ The open-source SonicBOOM pegs a mispredict at about a 10-cycle bubble, the same as an instruction-cache miss.¹⁴

• Static (BTFN or ISA hint bits): about 80%.¹
• 1-bit last-outcome: two mispredictions per loop execution.¹
• Bimodal 2-bit counters indexed by PC (Smith 1981; used in the Alpha 21164): one miss per loop; McFarling’s SPEC’89 data saturates at 93.5%.¹⁵

Two refinements matter in hardware. The predictor is updated at commit so wrong-path branches don’t pollute it, but any speculative history it uses must be updated at fetch, because dozens of branches are in flight by the time the first one commits; the history is snapshotted per fetch block and repaired on a mispredict.¹² And counters reset after a context switch or a flush cost a warm-up period, which is why the sim’s accuracies include the first few branches.

From two-level to TAGE

In Emer’s predictor algebra, a global-history predictor is $\mathrm{MSB}(\mathrm{Counter}(\mathrm{History}(0;T);T))$, gselect concatenates history with PC bits, and gshare indexes with $\mathrm{History} \oplus \mathrm{PC}$.¹ McFarling’s point was index efficiency: with 8 index bits, gshare 8/8 distinguishes cases that gselect 4/4 aliases; below about 256 bytes, though, adding history to an already-contended table hurts.⁵ The perceptron predictor (one weight vector per branch, dot product with the history as ±1) cut mispredictions 10.1% versus gshare at 4 KB on SPEC 2000, because its storage grows linearly rather than exponentially with history length.⁷

TAGE’s structure: a PC-indexed bimodal base table $T_0$ and tagged tables $T_1 \ldots T_M$ indexed by hashes of PC and history lengths $L(i) = \lfloor \alpha^{i-1} L(1) + 0.5 \rfloor$. An entry holds a 3-bit signed counter, a partial tag and a useful counter. The longest-history hit provides the prediction; on a misprediction a new entry is allocated in a longer-history table whose useful bits are clear.⁶ TAGE-SC-L adds a statistical corrector that can overturn low-confidence predictions and a loop predictor; the championship versions scored 3.986 mispredictions per thousand instructions at 64 KB and 4.991 at 8 KB on the CBP-5 traces.⁶ Under the hood sketches the algorithm.

Targets and front-end organization

Modern front ends are decoupled: the predictor runs ahead of fetch, writing predicted fetch blocks into a queue, and acts as an instruction prefetcher.¹⁸ Target structures are layered: a small zero- or one-cycle BTB (a next-line predictor), a large main BTB, an indirect-target predictor and a return stack. Published sizes include a 16K-entry first-level BTB and a 52-entry return stack (AMD Zen 5), and a 1K-entry next-line predictor, 2.5K-entry indirect predictor and 64-entry return stack (SiFive P870); Arm’s Neoverse V2 split its main BTB into two levels and enlarged its nano-BTB tenfold.¹⁶¹⁹¹⁸ Zen 5 and Neoverse V2 both predict two taken branches per cycle, because a 6- to 8-wide back end runs dry if fetch stops at every taken branch.¹⁶¹⁸ The BTB is indexed before decode, so it can be trained by one context and consulted by another, which is what Spectre’s variant 2 abused.²⁰

Modern cores split Tomasulo’s station into stages: rename (operand naming), dispatch into an issue queue and the ROB, and issue (wakeup and select). Wakeup broadcasts each completing destination tag to every waiting entry, which compares it with its source tags; select picks among the ready entries, usually oldest first, up to the number of free ports. For a dependent instruction to issue in the cycle right after its producer, wakeup and select must complete in one cycle; Palacharla, Jouppi and Smith called them an atomic operation and found them, with the bypass network, likely to be the critical timing paths of wide machines.⁹

Values move either through the queue (data-capture, like the 360/91) or are read from a physical register file after issue (non-data-capture). Most current designs read operands after issue: Arm describes Neoverse V2’s physical register files as “read after issue”, and BOOM uses a unified physical register file.¹⁸¹⁰ Issue queues are typically distributed by unit type; Zen 5, for example, shows separate schedulers feeding its six integer ALUs.¹⁶

Issue width and commit width are separate design choices. Intel’s Lion Cove allocates and renames 8 per cycle but retires 12 and has 18 execution ports; AMD’s Zen 5 dispatches and retires 8.¹⁷¹⁶ Ports exceed rename width because instruction mixes are uneven: the scheduler needs a free unit of the right type far more often than it needs many at once.

Two organizations exist. In data-in-ROB (implicit) renaming, as in Intel’s P6, speculative results live in ROB entries and are copied to an architectural register file at commit. In explicitrenaming, as in the MIPS R10000, Alpha 21264 and BOOM, one unified physical register file holds both committed and speculative values, and only pointers move.¹⁰³ Explicit renaming avoids the commit copy and decouples ROB size from register count, at the cost of a free list and freeing rules: the physical register a new writer replaces is released when that new writer commits, since no older instruction can need it after that.

Rename sits on the critical path of the front end. Each cycle a W-wide renamer reads 2W sources and W old destination mappings and writes W new ones, and must also check dependences within the group being renamed that cycle. Recovery after a mispredict needs the map table as it was at the branch: BOOM keeps a copy per in-flight branch for single-cycle recovery, and Arm’s Neoverse V2 lists six rename checkpoints; the alternative is to walk the ROB backward, undoing mappings.¹⁰¹⁸³

Renaming also enables cheap tricks at the map table: a register-to-register move or a zeroing idiom can be “executed” by pointing two names at one physical register. The Meltdown paper notes that Intel’s cores handle move elimination and zeroing idioms this way.²¹

The ROB is a circular buffer of W banks for a W-wide machine, allocated at dispatch and freed at commit. Per entry it tracks completion, exception status, branch mask and rename state (the stale physical register to free), and BOOM stores one PC per row of W instructions to save area.¹¹ Commit retires up to W completed instructions from the head per cycle and stops at the first that isn’t complete or that faulted.

Mispredict recovery doesn’t have to wait for the branch to reach the head. With per-branch map-table snapshots and branch masks on every younger instruction, a branch that resolves wrong can kill exactly its dependents in the queues and restore rename state in a cycle, while older instructions keep executing.¹⁰³ Exceptions, by contrast, are usually handled only at commit.¹¹ That deferral is what Meltdown exploited: on affected cores the faulting load’s data reached dependent transient instructions before the permission fault was raised at retirement.²¹

Memory ordering

BOOM’s load/store unit illustrates the common scheme. Stores enter the store queue at decode, wait for commit, and are then sent to memory in order. Loads issue speculatively as soon as their address is ready; each searches older uncommitted stores for a match, killing the memory request and forwarding store data when one hits. When a store’s address is resolved, it searches younger loads; one that already got its data from memory or from an even older store is a memory-ordering failure, which flushes and resets the rename maps.¹³ Store-set predictors start with naive speculation and record each violation, so that a load later waits only for the stores in its set.⁴ The ISA’s memory model sets what the queues must preserve between cores; RISC-V’s RVWMO, which BOOM implements, still requires ordering between same-address loads.¹³ Consistency across cores is part of Caches and coherence.

The Expert view adds a register-renaming toggle (off adds WAR and WAW interlocks), a front-end refill delay after a mispredict, and in the predictor bench a history-length slider and a penalty for a cycles-lost readout. Try:

• Width 4, window 32: then turn renaming off. How many fewer instructions finish under the miss, and which register reuse is responsible?
• Raise the miss latency to 100 cycles. The out-of-order advantage stays about 23 cycles. Why doesn’t it grow with the miss?
• On the loop pattern, lower the history to 2 bits and then 3. What is the shortest history that sees the loop exit coming?

The model is deliberately small: fixed latencies, no structural hazards beyond width, no cache or memory bandwidth, and one branch. It isolates window size, width, renaming and speculation.

By Little’s law (in-flight = throughput × latency), sustaining W instructions per cycle across a stall of L cycles needs

window entries, and proportionally many physical registers, load-queue and store-queue entries. With $W = 4$ and an L3 latency of about 50 cycles that is 200, the SonicBOOM figure.¹⁴ In practice the window fills with instructions dependent on the miss, so the useful fraction is lower, and a branch that depends on the missing load is the worst case: if it mispredicts, the whole run-ahead is squashed. The sim’s “branch guess: wrong” setting shows that interaction.

Wall’s numbers bound what a window can find. With perfect everything, median parallelism was 30.6; without branch prediction 2.2, without alias analysis 3.4, without renaming 4.8. With realistic but ambitious assumptions it stayed at 4–10, and speculating down both sides of branches added only modestly (to 7–13).⁸ The study assumed unlimited functional units and no cache misses, which makes those optimistic ceilings for ILP, not predictions of IPC.⁸

Growing the window has diminishing returns because the instructions that matter are often dependent on the stall, because mispredictions cap useful run-ahead (at one mispredict per few hundred instructions, a 600-entry window is often partly wrong-path), and because the structures get slower. Latency beyond the window is the job of prefetchers and of the cache hierarchy, and of other threads on the same core: see Multicore and vector units.

The general model is a covert channel from transient to architectural execution. Something steers the machine onto a path it would not architecturally take: a mistrained conditional predictor (Spectre variant 1), a poisoned BTB entry (variant 2), or a fault that is only acted on at commit (Meltdown). Transient instructions on that path read a secret and encode it in microarchitectural state, typically by making the address of a dependent load depend on it. After the squash, a receiver measures that state, typically with a cache timing probe.²⁰²¹

Each ingredient is a performance feature described earlier in this chapter: predictor state shared across security domains, a BTB indexed before decode, exceptions deferred to commit, a window several hundred instructions deep, and caches that are never rolled back.²⁰ Mcilroy et al. argue the leaks “lie at the foundation of optimization”: for most languages with a timer, today’s CPUs let a program build a procedure that reads arbitrary memory in its own process, so isolation must come from hardware and OS process boundaries.²²

Mitigations sit at every layer, each with a cost. OS: separate kernel page tables (KAISER/KPTI) for Meltdown.²¹ Software: speculation barriers and index masking at sensitive bounds checks, and process isolation for untrusted code.²² Hardware: flushing or partitioning predictor state across privilege and context changes, blocking forwarding of faulting loads, and research designs that hide or undo transient cache fills. Each gives back some of the performance speculation bought, which is why this remains, in Mcilroy et al.’s words, an open design problem.²²

A rough budget for a modern core: at 20% branches, 97% accuracy and a 17-cycle penalty (illustrative midpoints), mispredicts add about $0.2 \times 0.03 \times 17 \approx 0.1$ CPI, which at a base CPI of 0.25 (4 IPC) is a 40% slowdown. TAGE-SC-L’s championship results, about 4 mispredictions per thousand instructions at 64 KB, show how far the state of the art has pushed that term.⁶ Zen 5’s 448-entry ROB at 8-wide dispatch covers about 56 cycles of a stalled head, and Lion Cove’s 576 at 8-wide about 72, which matches the SonicBOOM rule of thumb that windows are sized for last-level-cache hits, not DRAM.¹⁶¹⁷¹⁴

• Wakeup and select scale badly. Palacharla, Jouppi and Smith’s SPICE models showed wakeup delay rising about 34% from 2- to 4-wide and 46% from 4- to 8-wide at a 64-entry window, with tag-drive delay quadratic in window size and a growing share of wire delay at smaller feature sizes. They proposed dependence-based clustering (FIFOs of dependent chains) to keep issue logic simple.⁹ Modern cores answer with distributed schedulers and clustered execution.¹⁶
• Bypass networks. Every result must reach every consumer in the next cycle. A fully bypassed design needs $2 \cdot W^2 \cdot S$ paths for $S$ result-producing stages, and because the result wires get longer too, bypass delay grows quadratically with issue width.⁹
• Register-file ports. A W-wide machine reads 2W and writes W registers per cycle. More ports make every cell larger and slower; Palacharla et al.’s clustered design kept a copy of the register file per cluster partly to cut the ports on each copy.⁹
• Prediction versus pipeline depth. A deeper front end raises clock rate and the penalty together; the architecture stage works out the optimum. Arm’s V2 keeps its pipelines short to recover quickly from mispredicts.¹⁸
• Security against speed. Partitioning or flushing predictor state at domain switches, fencing sensitive branches and isolating processes all cost performance.²²
• Single thread against throughput. The same area could hold several smaller cores, or wider vector units; a core can also share its window among two threads, as Zen 5 does by splitting its ROB.¹⁶ Those choices are the subject of Multicore and vector units.

1. Bimodal and gshare

Both predictors are a table of 2-bit saturating counters; they differ only in the index. Predict with the counter’s top bit at fetch; update at commit; keep the global history register speculative and repair it on a mispredict.⁵¹²

table ctr[2^n] = 2          # 2-bit counters, start weakly taken
ghr = 0                     # global history, speculative

predict(pc):
  i = (pc >> 2) ^ (ghr & (2^h - 1))   # gshare; bimodal: i = pc >> 2
  taken = ctr[i % 2^n] >= 2
  ghr = (ghr << 1) | taken            # speculative update at fetch
  return taken, snapshot(ghr), i

resolve(branch):                      # at execute
  if branch.taken != branch.predicted:
    ghr = (branch.snapshot without its guess << 1) | branch.taken

commit(branch):
  c = ctr[branch.i]
  ctr[branch.i] = min(3, c + 1) if branch.taken else max(0, c - 1)

2. TAGE

The base table $T_0$ is bimodal. Tagged tables $T_1 \ldots T_M$ use history lengths in a geometric series; each entry holds a 3-bit signed counter, a partial tag and a useful counter.⁶

L(i) = round(alpha^(i-1) * L(1))      # e.g. 4, 8, 16, 32, 64 ...

predict(pc, h):
  hits = [i for i in 1..M if T[i][idx(pc, h, L(i))].tag == tag(pc, h, L(i))]
  provider = max(hits) or 0             # longest matching history
  alt      = next-longest hit or T0
  p = T[provider].ctr
  if provider is newly allocated and |2*ctr+1| == 1:  use alt   # weak, untrained
  return sign(p)

update(pc, h, taken):
  train T[provider].ctr toward taken
  if prediction != alt: adjust T[provider].u toward (prediction == taken)
  if mispredicted and provider < M:
    allocate in some j > provider with u == 0 (else age the u counters)
  periodically decay all u                # so stale entries can be replaced

TAGE-SC-L wraps this with a statistical corrector, which reverts predictions that were statistically wrong in similar circumstances, and a loop predictor for long regular loops.⁶

3. Rename, issue and commit: the sim’s loop

The simulation above runs this loop each cycle over a 24-instruction trace with ALU latency 1, multiply 3, load hit 4 and one load that misses.

each cycle t:
  # 1. commit, in order
  while ROB.head.done and retired < W: retire(ROB.head)
  # 2. branch resolution
  if branch.done and branch.mispredicted:
    squash every entry younger than branch; fetch resumes at t + refill
  # 3. issue (wakeup + select), oldest first
  for e in ROB from head, while issued < W:
    if e.dispatched_before(t) and all producers(e) done by t:
      if renaming or (older readers of e.dst issued and older writer done):
        e.done = t + latency(e); issued += 1
    elif in_order: break          # nothing may pass a stalled instruction
  # 4. dispatch (rename + allocate)
  while fetched < W and ROB.size < N: ROB.push(next instruction)

4. Two first-order models

Mispredictions add CPI in proportion to their rate and penalty:

where $f_{\text{br}}$ is branches per instruction, $a$ the accuracy and $P$ the penalty in cycles. Because the penalty is roughly the front-end depth plus the branch’s own wait for its operands, a branch that depends on a cache miss can cost far more than $P$. The window needed to keep issuing at width $W$ through a stall of $L$ cycles follows Little’s law:

That is the SonicBOOM sizing argument.¹⁴ Combining the two: useful run-ahead ends at the first mispredicted branch, so the expected useful window is about $\min\!\left(N,\ 1 / \bigl(f_{\text{br}}(1 - a)\bigr)\right)$ instructions; at $f_{\text{br}} = 0.2$ and $a = 0.97$ that is about 167, which is why window size and predictor accuracy have grown together.

The window-sizing and side-channel arguments both lead into the memory system. Next, Caches and coherence covers locality, cache organization, miss types and average memory access time, prefetching (the answer to latency beyond the window), and the coherence and consistency rules the load/store queues must respect. Then Multicore and vector units covers sharing a window between threads and the turn from single-thread speed to many cores.