Taming Wild Branches: Overcoming Hard - to - Predict Branches using the Bullseye Predictor DOI: How.to.remove.this?(Not.ACM) Conference: 6th Championship Branch Prediction; June 21, 2025; Tokyo, Japan CCS: Computer systems organization Multicore architectures
Emet Behrendt, Shing Wai Pun, Prashant J. Nair · 2025
Read Taming Wild Branches: Overcoming Hard - to - Predict Branches using the Bullseye Predictor DOI: How.to.remove.this?(Not.ACM) Conference: 6th Championship Branch Prediction; June 21, 2025; Tokyo, Japan CCS: Computer systems organization Multicore architectures by Emet Behrendt, Shing Wai Pun, Prashant J. Nair (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06773.txt.
Introduction
Emet Behrendt, Shing Wai Pun, and Prashant Nair target the hardest branch guesses inside computer chips in this 2025 paper. Processors guess which way a program will jump, and a small set of wild branches causes over half of all wrong guesses in a champion predictor. Making the main tables bigger barely helps.
Their add-on, Bullseye, spots the troublemaker branches and hands them to small dedicated learners. A trial phase keeps a branch in the special unit only if it truly beats the main predictor. The extra hardware is modest and runs in parallel. Average wrong guesses per thousand instructions fell to a strong mark in championship tests.
Catalog record
| CREATOR | Emet Behrendt, Shing Wai Pun, Prashant J. Nair |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06773
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Taming Wild Branches: Overcoming Hard - to - Predict Branches using the Bullseye Predictor DOI: How.to.remove.this?(Not.ACM) Conference: 6th Championship Branch Prediction; June 21, 2025; Tokyo, Japan CCS: Computer systems organization Multicore architectures Emet Behrendt, Shing Wai Pun, Prashant J. Nair Abstract . Branch prediction is key to the performance of out - of - order processors. While the CBP-2016 winner TAGE-SC-L combines geometric-history tables, a statistical corrector, and a loop predictor, over half of its remaining mispredictions stem from a small set of hard-to-predict (H2P) branches. These branches occur under diverse global histories, causing repeated thrashing in TAGE and eviction before usefulness counters can mature. Prior work shows that simply enlarging the tables offers only marginal improvement. We augment a 159 KB TAGE-SC-L predictor with a 28 KB H2P-targeted subsystem called the Bullseye predictor. It identifies problematic PCs using a set-associative H2P Identification Table (HIT) and steers them to one of two branch-specific perceptrons, one indexed by hashed local history and the other by folded global history. A short trial phase tracks head-to-head accuracy in an H2P cache. A branch becomes perceptron-resident only if the perceptron’s sustained accuracy and output magnitude exceed dynamic thresholds, after which TAGE updates for that PC are suppressed to reduce pollution. The HIT, cache, and perceptron operate fully in parallel with TAGE-SC-L, providing higher fidelity on the H2P tail. This achieves an average MPKI of 3.4045 and CycWpPKI of 145.09. 1. Introduction Modern out-of-order CPUs depend heavily on aggressive speculative execution, where each fetched instruction block is predicted to either fall through or take a branch long before the branch condition is resolved. A single misprediction triggers a pipeline flush, drains the front-end, and requires re-fetching along the correct path, typically incurring a penalty of 15–30 cycles. As a result, the design and accuracy of the branch predictor have direct and significant performance implications, affecting instruction throughput, energy efficiency, and speculation-dependent microarchitectural features. Branch prediction accuracy remains a first-order design constraint, shaping front-end bandwidth, retirement rates, and security mitigation strategies. Over the past three decades, predictors have evolved from simple bimodal schemes to sophisticated hybrid, perceptron-based, and multi-component designs. The TAGE-SC-L predictor, the CBP-2016 competition winner, combines tagged geometric history tables (TAGE) with a statistical corrector and a loop predictor to cover a broad spectrum of control-flow behaviors. However, despite this architectural complexity, TAGE-SC-L still leaves substantial accuracy on the table, especially for a small but critical subset of dynamic branches. Despite TAGE-SC-L’s advanced use of long-range geometric histories, statistical correction, and loop-specific components, its residual mispredictions remain highly skewed. Lin et al. ( Lin and Tarsa 2019 ) showed that in a 30-million-instruction SPEC-INT 2017 trace, over 50% of mispredictions stem from fewer than ten static hard-to-predict (H2P) branches. These branches exhibit volatile control-flow behavior, with dynamic instances appearing under widely varying global histories. As a result, TAGE’s tag-matching struggles to retrieve consistent predictor state, leading to frequent allocations with low confidence. Since usefulness counters only increment on correct predictions, these entries are quickly evicted, creating a self-reinforcing cycle of misprediction, reallocation, and eviction that prevents the predictor from learning stable correlations. An H2P branch may see hundreds of distinct TAGE entries within a single millisecond of execution, none surviving long enough to gather confidence. Intuitively, one might expect that adding more storage, such as enlarging each component table or appending extra history lengths, would amortize the thrashing. Yet idealized studies by Seznec ( Seznec 2007 ) and the independent branch - runahead framework of Pruett et al. ( Pruett and Patt 2021 ) , demonstrate that even a hypothetical TAGE - SC - L with unbounded capacity converges only marginally beyond the accuracy of the published 64 kB design. Capacity alone cannot compensate for the entropy inherent in the branch’s context. Thus, the predictor tends to lack a representation capable of generalizing across diverging histories that precede each H2P instance. We introduce Bullseye, a compact H2P subsystem that augments a 159.3 kB TAGE - SC - L to address these challenges. Bullseye first pinpoints the few branches that dominate the residual error and then hands them off to branch - specific perceptrons. Detection is handled by the H2P Identification Table (HIT), a set - associative array that records each static branch’s execution and misprediction counts. A branch becomes H2P - active only after it surpasses adaptive thresholds on executions, mispredictions, and accuracy limits that tighten as the number of active H2P branches grows. Real workloads seldom activate more than eight to ten PCs simultaneously, so the HIT remains small and latency - neutral. Once Bullseye flags a program counter, the branch enters a brief trial phase: TAGE - SC - L and two perceptron engines predict in parallel while an H2P cache tracks their head - to - head accuracy. Suppose either perceptron maintains higher accuracy than TAGE - SC - L and produces outputs above a dynamic magnitude threshold. In that case, Bullseye promotes the branch to perceptron - resident status and suppresses further TAGE updates for that PC, eliminating table pollution. Branches that fail the trial fall back to the HIT with negligible overhead. Bullseye’s prediction engines comprise two lightweight perceptrons that capture patterns that TAGE’s geometric indexing misses. One leverages hashed - window local history for fine - grained, per - branch behavior; the other uses a folded global history vector to learn long - range correlations. During each fetch, the HIT probe, both perceptron evaluations, and the baseline TAGE - SC - L lookup proceed in parallel. A single - cycle arbiter selects a perceptron’s output when its confidence dominates; otherwise, TAGE - SC - L supplies the prediction. By confining extra complexity to the stubborn H2P tail, Bullseye sharpens overall accuracy while preserving the critical - path speed of the underlying predictor. 2. Background and Related Work Modern branch predictors can be broadly classified into TAGE-based and perceptron-based categories. 2.1. The TAGE-based Predictor The TAGE predictor architecture combines a tagless bimodal table of PC-indexed 2-bit counters with multiple tagged components indexed using geometrically increasing history lengths. Each tagged entry includes a prediction counter, a partial tag, and a usefulness counter. The final prediction is selected from the tagged component with the longest matching history. TAGE-SC-L enhances this core design with two additional components: (i) a statistical corrector (SC) that aggregates predictions from biased, global, and local history tables to override low-confidence TAGE outcomes, and (ii) a loop predictor (L) optimized for detecting constant-iteration loops ( Seznec and Michaud 2006 ) . TAGE-SC-L was the winning submission in CBP-2016 and serves as the baseline for the predictor proposed in this work. 2.2. The Perceptron-Based Predictor Perceptron-based predictors take a fundamentally different approach by framing branch prediction as a form of single-layer neural inference. Each prediction is computed as a weighted sum of recent branch outcomes combined with a bias term; the sign of the resulting sum determines whether the branch is predicted as taken or not taken ( Jimenez and Lin 2001 ) . Weights are updated at retirement based on the correctness of the prediction, allowing the perceptron to learn long-term correlations that traditional counter-based predictors typically miss. While perceptrons are well-suited for linearly separable patterns, they introduce