7th Branch Prediction Championship : Part II

This is the second (and final) post in the series covering the Next Generation Branch Prediction Champtionship (CBP-NG). Part-I details the provided infrastructure and the winning submissions.

Distilled Branch Predictors (Simha Sethumadhavan – Columbia University)

The author proposes an ‘Ensemble Predictor’ composed of a fast, one-cycle predictor P1 and a slower (but more accurate) two-cycle predictor P2. However, instead of training them both independently on the actual branch outcomes, P1 is trained on the predictions made by P2 (which continues to be trained on branch outcomes), turning it into a faster, distilled version of the more accurate predictor. This student-teacher model improves the VFS score by lowering the misprediction recovery latency. An additional PC-tagged structure is added to identify one-sided branches and prevent the usage of P2 to predict them, further lowering the energy consumption. In the final submission, a bimodal predictor is used as P1, and P2 is an 8-table TAGE predictor.

Run-Ahead Block TAGE (Prakhar Gupta, Yuwei Sun, Rishav Sen, Reet Sinha, Swetha Karthikeyan – University of Illinois Urbana-Champaign)

The authors use a single (15-table, geometric history length) TAGE predictor. Ahead Pipelining is implemented to hide the table access latency, so that the effective prediction latency is one cycle. To correctly use ahead-pipelining, a secondary tag is added to all table entries; an entry can be used only if the tag calculated from the last branch PC of the previous block matches with the stored tag. The resulting increase in throughput outweighs the increase in TAGE MPKI, boosting the VFS score. A maximum of 7 branches can be predicted at once, over a 256-instruction predict block. An 8k-entry bimodal predictor is used as a fallback when TAGE is unable to provide a prediction. Independent Resolution Chains allocate a tag, usefulness and hysteresis field to each slot in the predict block, allowing each slot to use a different TAGE table. Using independent history length per branch improves the MPKI for most cases, but is detrimental when there is intra-block correlation.

Coding Agents as Design Searchers: An Autonomous TAGE Tuning Campaign
(Matt Pallan – University of Maryland)

This submission stands out because its primary contribution is the methodology, not the predictor. The author proposes a systematic approach to leverage AI for design space exploration – the tasks are split between two independent agents Ag1 (Claude Code) and Ag2 (OpenAI Codex). Ag1 is responsible for coming up with structural (table size, hashing, indexing, etc.) or behavioral (update policy, initial value, etc.) changes and their implementation. Ag2 acts as a critic – questioning the intent behind Ag1’s changes and coming up with out-of-the-box architectural ideas. The agents stay in sync through shared collateral – a journal and a machine-readable ledger, which are updated after every experiment. The only human inputs for this study are the objective (maximizing the VFS score), the record-keeping mechanism and some hard constraints to reduce the search space (such as capping the predictor latency at 2 cycles). Each configuration proposed by Ag1 is first tested on a reduced instruction count on the provided traces, only those that perform well (31 out of 2300+) are run on the full instruction count. Out of these, only six changes proved beneficial and survived cross-inspection by Ag2. The final TAGE model is tuned to prioritize throughput over accuracy and ditches the Statistical Corrector mechanism as it is deemed infeasible for HARCOM implementation.

Offset-Free TAGE-SC
(Yashwant Kumar Balivada, Sairam Viswanathan Susarla – Texas A&M University)

A two-level predictor is implemented – the first level is a single-cycle gShare that gives fast predictions. The second level consists of a TAGE-SC predictor which is more accurate. The key distinction of the latter is its usage of Branch Number instead of Branch Offset within a predict block. This leverages the championship-specific assumption that we can magically identify conditional branches, to reduce storage and energy expenditure. The VFS score is maximized when predicting upto 8 branches in a 64-instruction window. The Statistical Corrector uses 3 components – branch-PC bias, taken branch history and global path history.

Key Takeaways

The usage of TAGE was a common trend in the championship, with all the submissions implementing some form of tagged history tables in their predictor to reduce MPKI. Ahead Pipelining was another popular technique that many of the contestants used to hide the table-access latency for large predictors. This was also the first championship to have a submission developed by AI agents; the easily reproducible methodology holds great potential for future computer architecture research.

This was the first Branch Prediction Championship to make energy consumption a part of the final score. Naturally, the submissions saw a shift from the highly accurate and complex predictors that dominated the past championships to simpler, implementation-friendly models. This, along with the usage of HARCOM to model the predictors in a hardware description language (or something close to it) ensured that the industry can easily adopt the novel ideas that were proposed.

However, despite this imposition of practicality, the provided infrastructure made some simplifying assumptions that were criticized by some of the popular names in Branch Prediction. The first issue was the magical detection of conditional branches by the simulator, which is quite unrealistic. Allowing the contestants to implement a BTB (Branch Target Buffer) and RAS (Return Address Stack) could help paint a more complete picture. Secondly, the usage of high throughput techniques like Ahead Pipelining requires some consideration of the misprediction recovery mechanism, which is a key stage in any high performance branch predictor.

About the Author

Digvijay Singh obtained his Bachelor’s degree from BITS Pilani, India and his Master’s degree from Texas A&M University where he worked on data prefetching as part of the CAMSIN research group. He currently works as a Silicon Architect in Google’s mobile CPU team.

Disclaimer: These posts are written by individual contributors to share their thoughts on the Computer Architecture Today blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGARCH or its parent organization, ACM.