Modern Branch Predictors

The gshare predictor of Chapter 55 reached roughly 95 percent accuracy on the SPEC benchmarks of its era. Modern predictors push that number to 97 or 98 percent on the same workloads, and the gap is consequential. At 95 percent accuracy and a 20-cycle recovery, a 4-IPC core loses about $0.20 \times 0.05 \times 20 \times 4 = 0.8$ slots per instruction to mispredictions, a 20 percent IPC hit. At 98 percent the loss falls to $0.20 \times 0.02 \times 20 \times 4 = 0.32$ slots, an 8 percent hit. Cutting the misprediction rate by 60 percent recovers 12 percent of the IPC, which is more than most other front-end optimizations deliver.

The accuracy improvements since gshare have come from two ideas. The first is variable-length history matching. gshare uses one fixed history length for every branch. Some branches need only a short history (last 4 outcomes); some need a long history (last 100 outcomes). TAGE, the dominant modern predictor, runs several tables in parallel with geometrically increasing history lengths and picks the longest-history table whose tag matches the current PC and history. The second idea is replacing the saturating counter’s discrete update rule with a continuous one. Perceptron predictors, and later BATAGE, treat the prediction as a weighted sum or a Bayesian posterior, which captures finer correlations than two-bit counters can express.

This chapter develops the modern predictors from first principles. It starts with the limits of fixed-length history (the motivation for tagging), develops the TAGE structure and its update rule, extends to indirect targets via ITTAGE, treats the perceptron predictor and its path-based hashed variant, and closes with BATAGE and the CBP competition results that frame the current state of the art.

01.The Limits of Fixed-Length History

A gshare predictor with a 14-bit GHR captures correlation with the last 14 branches. Two patterns reveal its limits. The first is the short-history pattern: a branch whose outcome correlates only with the immediately previous branch. For this branch, the gshare’s 14 bits of history act as noise. The single bit that matters is diluted by 13 irrelevant bits, and the index lands in a different PHT entry every time even when the relevant history is unchanged.

The second is the long-history pattern: a branch whose outcome correlates with a branch executed 30 branches ago. The gshare’s 14-bit GHR has already shifted that branch out of history. The correlation is invisible to the predictor.

A concrete numerical example clarifies. Consider a loop that iterates 100 times with a single branch inside. The loop-exit condition correlates with the loop counter, which is updated 100 branches before the exit branch executes for the last time. A gshare with a 14-bit GHR cannot see the counter update. A predictor with a 100-bit GHR could see it, but indexing a PHT with 100 bits requires either an enormous table or aggressive hashing that destroys most of the information.

The TAGE design resolves both extremes by indexing several tables with different history lengths and choosing the right one dynamically per branch.

02.TAGE: The Tagged Geometric Predictor

The TAGE predictor was introduced by Seznec and Michaud in 2006 [1] and has since gone through several revisions, with the 2011 version [2] as the canonical reference. The predictor has dominated every CBP competition since CBP-2 in 2006.

The structure has two levels. A base bimodal predictor is the fallback, indexed only by branch PC, with no history. Several tagged components sit on top. Each tagged component is a small table indexed by a hash of branch PC and a fixed-length slice of global history. The history lengths grow geometrically: a typical 5-component TAGE uses lengths 4, 10, 25, 64, and 160 bits. Each tagged entry carries a saturating counter for the prediction (3 bits is typical), a tag (8 to 16 bits) to verify the entry corresponds to the current (PC, history), and a useful bit (1 or 2 bits) for replacement.

A prediction proceeds as follows. The base bimodal produces its prediction. Each tagged component computes its index and reads the corresponding entry. If the entry’s tag matches the current (PC, history) hash, the component "hits" and contributes its prediction. The tagged components are checked in increasing history length, and the prediction comes from the longest- history component that hit. If no tagged component hits, the prediction comes from the bimodal.

Indexing and Tag Computation

Each tagged component uses a different history length. The hash function for component $i$ combines the branch PC with the most recent $h_i$ bits of the GHR. The exact hash matters: a common scheme is to fold the GHR into a smaller chunk by XOR (the folded history) and XOR the result with the PC. Different folding patterns are used for index and tag, so the index and tag are functions of overlapping but distinct subsets of the (PC, history) bits.

The tag is computed by a separate hash. Two different (PC, history) pairs that happen to share an index very likely have different tags, so the tag check filters out false matches. A tag width of 8 bits gives a $2^{-8}$ probability of accidental tag match. With a 1024-entry tagged component, the expected collision rate per access is roughly $1024 \cdot 2^{-8} = 4$ "could collide" candidates per access, of which a fraction live in the right index. The actual false-positive rate is low enough in practice that the predictor performs well.

The Update Rule

The update rule is what makes TAGE accurate over time. When the branch resolves, three things happen.

First, the provider component (the one that provided the final prediction) updates its counter: incremented if the actual outcome was taken, decremented otherwise, saturating at the range bounds.

Second, the useful bits are updated. The provider’s useful bit is set if the shorter-history components that also hit would have given a different prediction than the provider’s and the provider was correct (so the provider was actually contributing), and it is decremented if the predictions differ and the provider was wrong. The useful bit is also cleared periodically to allow unused entries to be evicted.

Third, on a misprediction, a new entry may be allocated. The predictor scans the tagged components with history lengths longer than the provider’s. For each, it picks an entry with useful bit cleared (a "free" entry) and writes a fresh tag and counter matching the current (PC, history). The new entry replaces an older entry that was not contributing. If no free entry is available, the allocation fails and the predictor relies on the provider to eventually self-correct.

TAGE Sizing in Production

A reference TAGE configuration at roughly 24 KiB total storage uses 5 tagged components with history lengths 4, 10, 25, 64, and 160, each holding 1024 entries with 3-bit counter, 8-bit tag, and 1-bit useful bit. Total per component is $1024 \times 12 = 12$ Kib = 1.5 KiB; total for 5 components is 7.5 KiB. The base bimodal is typically 16 KiB. Plus overhead and the GHR itself, the total is in the 20 to 30 KiB range, with accuracy in the 96 to 97 percent range on SPEC.

Production cores have larger budgets. Intel and AMD do not disclose the exact predictor designs in current cores, but performance counter studies and patents indicate that they use TAGE-like structures with total predictor budgets in the 80 to 200 KiB range. The ARM Neoverse predictors are similarly TAGE-like based on disclosed documents.

03.Indirect Target Prediction with ITTAGE

The TAGE structure transfers cleanly to indirect target prediction. ITTAGE replaces the direction bit in each tagged entry with a target address (32 or 48 bits depending on the addressing scheme) and the saturating counter with a smaller confidence counter. The longest-match selection rule is unchanged.

The motivation is the same. A single virtual call site in C++ can dispatch to a dozen different functions depending on the runtime type of the receiver. The "history" that distinguishes the cases is the chain of branches that determined the type, which often sits 20 or 30 branches back. A short-history target predictor mispredicts on every type change. ITTAGE’s long-history components catch the change.

Seznec presented ITTAGE in 2011 alongside the updated TAGE work [2], and it has since become the standard indirect predictor in CBP competition entries. The 64 KiB ITTAGE reference design reduces indirect misprediction rates from the 30 to 40 percent typical of simple BTB indirect prediction to under 5 percent on type-polymorphic workloads.

04.Perceptron Predictors

The perceptron predictor, introduced by Jiménez and Lin in 2001 [3], takes a different approach. Instead of indexing a table of saturating counters, it stores a vector of weights per branch PC and computes the prediction as a weighted sum of history bits.

A perceptron entry for branch PC $p$ holds $h + 1$ signed weights $w_0, w_1, \ldots, w_h$, where $h$ is the history length. The weight $w_0$ is the bias (history-independent component), and weight $w_i$ for $i \geq 1$ is the contribution of GHR bit $i$.

The prediction is computed as:

$y = w_0 + \sum_{i=1}^{h} w_i \cdot x_i$

where $x_i = +1$ if GHR bit $i$ is taken and $x_i = -1$ if not- taken. The predictor outputs "taken" if $y \geq 0$ and "not- taken" if $y < 0$. The magnitude of $y$ is the confidence.

The update rule on a resolved branch is:

$\begin{aligned} &\text{if } (\text{prediction} \ne \text{actual}) \text{ or } |y| < \theta : \\ &\qquad w_i \leftarrow w_i + t \cdot x_i \quad \text{for } i = 0, \ldots, h \end{aligned}$

where $t = +1$ if the actual outcome is taken, $t = -1$ otherwise, and $\theta$ is the training threshold. The threshold avoids saturating the weights when the predictor is already very confident, which preserves storage for learning new patterns.

The Linear-Separability Limit

A perceptron can only learn linearly separable functions of its history bits. A branch whose outcome is the XOR of two history bits ("taken iff bits $i$ and $j$ differ") cannot be predicted by a single perceptron, because no linear combination of $\pm 1$ inputs distinguishes the four XOR cases on output sign. Real branches sometimes exhibit XOR-like correlations, so single-layer perceptrons miss those.

The original Jiménez and Lin paper showed that despite this limit, perceptrons match or beat the best gshare variants of their era on SPEC, because the linearly-separable cases dominate in practice. Later work extended perceptrons in several directions to capture non-linear correlations.

Hashed Path-Based Perceptron

The path-based hashed perceptron (Jiménez, 2003) [4] uses the path of recent branch PCs (not just the direction bits) to index a shared weight table. This captures correlations that depend on which branches executed, not just whether they were taken. The weight table is shared across PCs, reducing the per-branch storage and allowing longer effective history at the same total budget.

A modern hashed perceptron with a path-based formulation can match TAGE on accuracy at similar storage budgets. The two families compete in CBP, with TAGE-derived entries taking the titles since 2006 but perceptron variants placing close behind.

05.BATAGE: Bayesian TAGE

BATAGE (Bayesian Adaptive TAGE) was introduced by Michaud in 2018 [5]. It replaces TAGE’s saturating-counter prediction with a Bayesian posterior estimate, treating each entry’s history of outcomes as evidence and computing the posterior probability of taken given that evidence.

The mechanical change is small. Each tagged entry stores two counters: $n_T$ (count of taken outcomes for this entry) and $n_N$ (count of not-taken outcomes). The prediction is "taken" if $n_T > n_N$ and the confidence is derived from the magnitude of the difference. The entry update on a resolved branch increments the appropriate counter (with saturation at some maximum, e.g., 32).

The Bayesian interpretation is that the counters approximate the posterior of a binomial distribution with a Beta prior. The predictor uses the maximum a posteriori estimate, which for a Beta-binomial is $(n_T + \alpha) / (n_T + n_N + \alpha + \beta)$ for prior parameters $\alpha, \beta$ (typically 1 each for a flat prior).

The accuracy gain over TAGE is small but consistent, roughly 0.3 to 0.7 percentage points at typical storage budgets on SPEC, and larger on workloads with high entropy. BATAGE postdates CBP-5 (2016), so its published results were measured against that competition’s trace suite after the fact rather than as an entry, and variants have been competitive in subsequent competitions.

The BATAGE update is computationally cheap. Two counters, two saturating arithmetic operations per resolved branch, and a simple posterior comparison at lookup time. The added storage is roughly $4 \times$ the original counter width (two 6-bit counters, so 12 bits per entry instead of 3), which is offset by removing the useful bit replacement logic in favor of a simpler "least confident entry" replacement.

06.Storage vs Accuracy and CBP Results

The Championship Branch Prediction competitions, organized at JILP since 2004, have shaped the field. Teams submit predictors constrained to a fixed storage budget (typically 8 KiB, 32 KiB, and 64 KiB tracks). Submissions run on a common trace suite, and the lowest aggregate misprediction rate wins.

The storage-accuracy curve from CBP results follows a power law. Each eightfold increase in the predictor budget reduces the misprediction rate by roughly 20 to 30 percent. The asymptotic limit on SPEC is around 0.5 to 1.0 misprediction per kilo-instruction, achieved by 1 MiB- class predictors that are too large for production cores.

A second metric the CBP results expose is predictor warmup cost. A predictor’s accuracy in its first 10 million instructions on a new workload is markedly worse than its steady-state accuracy on the same workload after 100 million instructions. TAGE warmup is slower than gshare’s because the tagged components need to allocate entries on mispredictions, and the allocation process is throttled by the useful-bit-clear requirement. CBP simulations now report both "all instructions" accuracy and "after-warmup" accuracy to distinguish steady-state behavior from cold-start.

07.Production Microarchitectures

Modern x86-64 and AArch64 cores all use TAGE-derived predictors. The details are not publicly disclosed at the level of components or history lengths, but architectural blog posts, patents, and performance counter studies converge on TAGE-like structures with hybrid extensions for indirect branches, returns, and loops. Intel’s optimization guide refers to "complex hybrid" predictors. AMD’s optimization guide uses similar language. ARM’s documentation for Neoverse cores describes "TAGE-style" direction prediction and ITTAGE-style indirect prediction in publicly available papers.

The total predictor storage budget is one of the most expensive parts of the front end on a modern core. Intel’s Golden Cove front end devotes an estimated 200 KiB to branch prediction state (TAGE tables, indirect predictor, BTB, RAS). AMD’s Zen 4 and ARM’s Neoverse V2 are in the same range. This is several times the L1 instruction cache size on the same core, and it is the structure most directly responsible for the front-end’s IPC.

08.Worked Examples

09.Exercises

References

1. [1]Seznec, Andr\'e (2006). “A Case for (Partially) TAgged GEometric History Length Branch Prediction.” In Journal of Instruction-Level Parallelism (JILP), Vol. 8.
2. [2]Seznec, Andr\'e (2011). “A New Case for the TAGE Branch Predictor.” In Proceedings of the 44th Annual International Symposium on Microarchitecture (MICRO), pp. 117--127. doi:10.1145/2155620.2155635
3. [3]Jim\'e (2001). “Dynamic Branch Prediction with Perceptrons.” In Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA), pp. 197--206. doi:10.1109/HPCA.2001.903263
4. [4]Jim\'e (2003). “Fast Path-Based Neural Branch Prediction.” In Proceedings of the 36th Annual International Symposium on Microarchitecture (MICRO), pp. 243--252. doi:10.1109/MICRO.2003.1253199
5. [5]Michaud, Pierre (2018). “An Alternative TAGE-like Conditional Branch Predictor.” In ACM Transactions on Architecture and Code Optimization, Vol. 15, No. 3, pp. 1--23. doi:10.1145/3226098