Lecture 16: Advanced Branch Prediction

What this lecture covers

This lecture continues the course's treatment of guessing the next fetch address, focusing specifically on predicting whether a conditional branch is taken. It picks up from an earlier lecture that showed even 90% prediction accuracy badly underutilizes a deep, wide pipeline, and asks how real processors get closer to 100%.

The lecture works through static (compile-time) prediction methods, then dynamic (runtime, hardware-based) predictors of increasing sophistication: last-time prediction, two-bit saturating counters, two-level global and local history prediction, G-share, hybrid predictors as used in the Alpha 21264, and modern perceptron and TAGE predictors used in commercial chips. After watching, you should be able to explain why history-based prediction outperforms static heuristics and describe the mechanism behind each major predictor family.

Key ideas

• Static prediction methods: always-not-taken, always-taken, backward-taken, profile-based, program-analysis-based, and programmer-supplied pragma hints, none of which adapt to a branch's changing behavior at runtime.
• Last-time predictor: predicts a branch will do what it did the previous time; accurate for long loops but always mispredicts the first and last iteration.
• Two-bit saturating counter: adds hysteresis so a single unexpected outcome doesn't immediately flip the prediction, improving accuracy over a single bit.
• Global history correlation: a branch's outcome is often correlated with the recent outcomes of other branches, captured in a global history register that indexes a pattern history table.
• G-share: indexes the pattern history table with the branch address XORed with global history, improving table utilization and accuracy.
• Local history correlation: a branch's outcome can correlate with its own past outcomes beyond just the last execution, useful for identifying loop iterations.
• Hybrid predictors: combine multiple predictor types (for example local and global) with a meta-predictor that chooses which one to trust, as in the Alpha 21264.
• Perceptron and TAGE predictors: perceptron predictors learn per-bit correlation weights with simple machine learning; TAGE combines multiple history lengths in tagged tables, and both are used in modern commercial processors.

Walkthrough

Static branch prediction techniques (10:21)

The lecture reviews compile-time methods that require no history hardware: always-not-taken (30-40% accurate, since loop branches are usually taken), always-taken, and backward-taken (better, since backward branches often close loops). It then covers profile-based prediction, where a compiler encodes a single hint bit per branch based on running the program on sample inputs, and shows with examples that this only reaches 50% accuracy on branches that alternate or split evenly, and can fail badly if the profiling input isn't representative. Program-analysis heuristics (such as predicting error-checking branches as not taken) and programmer-supplied pragmas are also covered as ways to set that hint bit without profiling, each with its own limitations. All static methods share the same weakness: they cannot adapt when a branch's behavior changes while the program runs.

The last-time and two-bit saturating counter predictors (26:30)

The simplest dynamic predictor stores one bit per branch recording its outcome last time and predicts the same outcome again. For a loop of n iterations this gets (n-2)/n accuracy, good for long loops but poor for short or alternating ones, since it always mispredicts on loop entry and exit. The lecture then introduces the two-bit saturating counter (from a 1981 paper), using an air-conditioner analogy for hysteresis: a single unexpected outcome moves the counter to a "weakly" predicted state rather than flipping the prediction outright, so two consecutive opposite outcomes are needed to change the prediction. This recovers much of the accuracy lost on short loops and was adopted quickly by industry, though even 85-90% accuracy is shown to be insufficient for deep, wide modern pipelines.

Two-level global history prediction (40:40)

To go further, the lecture introduces two-level prediction based on a 1991 paper: the idea that a branch's outcome correlates with the recent outcomes of other branches (global correlation) or with its own history beyond the last execution (local correlation). A global history register, a shift register of recent taken/not-taken outcomes, indexes a pattern history table of saturating counters recording what happened the last time that same history pattern was seen. Code examples show how testing related conditions in sequence makes later branches highly predictable once earlier outcomes are known. The Pentium Pro's implementation, a 4-bit global history register with multiple pattern history tables, is presented as the first commercially successful use of this idea.

G-share and local history prediction (1:06:22)

The G-share predictor improves on plain global history by indexing the pattern history table with the branch's program counter XORed with the global history register, adding context about which branch is being predicted and spreading table usage more evenly, at the cost of an extra XOR on the critical path. The lecture then covers local history prediction, where each branch gets its own history register tracking its own past outcomes, useful for distinguishing which iteration of a loop is executing since the ending iteration produces a distinct history pattern.

Hybrid predictors and the Alpha 21264 (1:19:32)

Since different branches predict better with different techniques, no single predictor is best for all branches. The lecture presents hybrid predictors that combine multiple predictor types with a meta-predictor (or choice predictor) that learns which one to trust for a given branch, illustrated with the Alpha 21264's design: a 12-bit global predictor, a 1,024-entry local history table feeding a local predictor, and a choice predictor that selects between them based on global history.

Perceptron and TAGE predictors (1:26:36)

The lecture introduces the perceptron predictor, a single-layer neural network that learns a weight per global history bit representing how strongly that bit correlates with the branch's outcome, computing a prediction as the sign of the dot product between history bits (encoded as +1/-1) and weights. This allows longer history lengths without table sizes exploding, at the cost of needing multiplier hardware, and is used in AMD processors. The lecture closes with TAGE, which combines multiple pattern history tables indexed by different, geometrically increasing history lengths with tag matching, letting the predictor choose the history length that works best for each branch; TAGE and perceptron variants are both used in modern commercial designs, alongside confidence estimation techniques that decide how much to trust a given prediction.

Before you watch

• Review the previous lecture's introduction of the branch target buffer and the basic fetch-stage prediction flow, which this lecture builds on directly.
• Be familiar with saturating counters and cache-style indexed table structures, referenced throughout.

Check your understanding

1. Why does profile-based static prediction fail on a branch that alternates taken and not-taken every execution?
2. How does the two-bit saturating counter avoid the last-time predictor's worst-case mistakes on short loops?
3. What problem does G-share's XOR of program counter and global history solve compared to using either alone?
4. Why might a hybrid predictor need a separate meta-predictor, and what tradeoff does that introduce?
5. What advantage does a perceptron predictor have over a fixed-length global history table when using very long histories?