Background

The Next Generation Branch Prediction Championship (CBP-NG) aimed to address practical implementation challenges in branch prediction, moving beyond metrics used in earlier iterations. By emphasizing energy-adjusted performance—incorporating throughput, timing, and dynamic energy alongside traditional Misprediction Per Kilo-Instruction (MPKI) metrics—the championship sought to align research with industry design constraints. Utilizing an extensive set of 1579 traces derived from ARM and Ampere architectures, the event evaluated predictors through a two-level model: a first-level (P1) predictor for immediate output and a second-level (P2) predictor that verifies and corrects potential mis-predictions. All submissions were required to be implemented using the HARCOM C++ library that imposes restrictions on the behaviour of all variables and structures, treating them as hardware components such as wires, registers and SRAMs arrays. The energy consumption was approximated based on the ‘hardware’ used, assuming 5nm FinFET technology. The final scoring was done using a mathematical formula that combines:

• IPC: Number of instructions predicted per cycle
• CPI: Number of mispredictions (by the L2 predictor) per correct-path instruction times misprediction penalty
• EPI: Energy consumed per correct-path instruction

into a Voltage Frequency-scaled Speedup (VFS) score. The objective is to maximize this VFS score.

In this blog post, we first describe the gSHare-N-ahead predictor, which delivers the highest VFS score among all example predictors provided with the infrastructure. It implements a mechanism called ahead-pipelining, which inspired several submissions in this championship. This is followed by an overview of the championship winners – starting from first place to third. The remaining submissions will be discussed in Part 2 of this blog post.

GShare N-Ahead Predictor

GShare N-ahead is one of the predictors provided as part of the simulation infrastructure. It supplements the conventional N-wide (N predictions per cycle) gShare predictor with ‘Ahead Pipelining’. Instead of using the current block B1’s address (PC_B1), it uses the prior block B0’s address (PC_B0) to index the prediction tables. Since PC_B0 is available one cycle earlier than PC_B1, predictions can be made earlier, effectively reducing prediction latency. The only catch is that in a predict block with N branches, there can be N+1 paths leading out of it, so until PC_B1 is known, we have to consider all possibilities and make (N+1)*N predictions in BP0. Once PC_B1 is known in BP1, it is combined with B0’s last conditional branch direction and the number of conditional branches in B0 to multiplex the BP0 predictions to obtain the final N predictions.
The particular implementation used in the championship predicts N = 7 branches per cycle as a P1 predictor; P2 simply reuses the P1 prediction for super-aggressive prediction throughput.

MORSL: Minimal-Overhead Rank-Based Predictor with Summation-Free Correction and Lazy Access (Toru Koizumi, Masanari Mizuno, Soma Nishida – Nagoya Institute of Technology; Kanata Abe – The University of Tokyo; Tomoaki Tsumura – Nagoya Institute of Technology; Ryota Shioya – The University of Tokyo). First place

The authors started with a TAGE predictor for high prediction accuracy, and implemented the following features: 

• Ahead-pipelining is enabled for a higher throughput.
• While deciding the TAGE history lengths, the shortest history length is increased to compensate for the reduced context due to ahead pipelining. Furthermore, the larger history lengths are spread farther apart than the smaller ones. This allows for pseudo-skewed associativity within smaller tables, since each TAGE table has a single tag per entry. 
• A Tagged Corrector (TC) mechanism consisting of two tagged predictors.  TC-Bias is indexed using the current block address and can override the TAGE prediction  in case of a high confidence tag match. TC-History uses the previous block’s address, BrIMLI and Path History to override the TAGE + TC-Bias prediction in case of a tag match. Using overrides instead of summation reduces energy consumption by avoiding multiple table reads on the adder datapath.
• An ‘allocation guided’ access filter is implemented (as two 1-bit tables indexed by PC and PC XOR shortest history), which records whether a branch PC had any allocations in a longer TAGE table in the past. The intuition is that if the PC did not trigger allocations to a longer table, the shorter tables were able to accurately make predictions for it. Unless both the access filter table reads return 1, the ‘mini-TAGE’ mode is activated and only the two shortest TAGE tables are read to save energy.

Ahead-Pipelined N-branch GShare with Tagged Tables (Jun Fan). Second Place

This proposal improves the accuracy of the ahead-pipelined gShare predictor by using 18-bit history and 2 hysteresis bits. Furthermore, the gShare RAM size is halved to make room for two ahead-pipelined tagged tables (20 and 80-bit histories, respectively). These three tables are looked up in parallel during prediction, and the longest matching entry is used to make the first stage prediction P1. The final prediction P2 simply reuses P1 to maximize throughput. Upon a branch misprediction, the table that produced the prediction is updated, and new entries are allocated in tables with longer histories.  If a wrong prediction came from the 20-bit table, a new entry will be allocated only in the 80-bit table, but if it came from the 18-bit table, the 20 and 80-bit tables will both have new allocations. Finally, a direct-mapped ‘bias’ table is added which stores a PC along with  a 3-bit saturating counter in each entry. When gShare is used to make the final prediction and the corresponding PC is found in the table with a strong bias (000 or 111), the predictor is updated with the stored strongly biased value.  

Energy-Efficient Ahead-Pipelined TAGE
(Nhat Dang, Eric Rotenberg – North Carolina State University). Third Place 

The authors implement a single branch predictor to reduce the energy consumption due to multiple table reads and updates in a dual-predictor scenario. Ahead Pipelined TAGE is implemented, consisting of a baseline bimodal predictor and 10 tagged tables with geometric history lengths. It uses the previous block’s address to predict upto 4 branches per cycle in a 256-instruction region. A 6-bit secondary tag (generated from the lower bits of the last branch PC) is added to the TAGE entries to allow disambiguation of the missing history for the previous block. Additionally, the access to  6 largest TAGE tables is gated. Specifically, if there have been no mispredictions in the last 512 blocks, and the total number of mispredictions is less than the (number of retired branches / 1024), these tables are not accessed, to save dynamic energy. Further energy optimizations include placing the tag comparison logic near the tag SRAMs, and placing the SRAMs accessed during prediction together.

Stay tuned for Part-2 of this article to learn more about other submissions and the industry/academia’s perception of this contest.

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.