Branch prediction research

This research spans from 1996 to 2016 (and hopefully will continue later).

 

Multiple-block Ahead branch prediction

In 1996, we proposed Multiple-block ahead branch prediction. Multiple Branch Ahead prediction provides an efficient way to predict the addresses of two or more instruction blocks in a single cycle. Such an approach would be very useful for wide dispatch superscalar processors. In fact, it is also adapted for implementing multi-cycle prediction. In 2001-2002, we explored in details the effective design of a complete instruction fetch mechanism featuring multiple-block ahead prediction for a pipelined design.

Related publications:

Skewed branch predictors

Between 1996 and 2000, we have investigated the use of the majority vote as a mean to avoid aliasing impact on global history branch predictors leading to the skewed branch predictor and the 2bcgskew branch predictor. The 2bcgskew predictor was the basis of the branch predictor of cancelled Alpha EV8. 2bcgskew is often considered in the litterature as the most efficient conventional predictor (2-bit counter based) as opposed to neural predictors and more recent TAGE-like predictors. Its accuracy is also often underestimated in comparative studies. The parameters described in “An optimized 2bcgskew branch predictor ” should be used in comparative studies.

Related publications:

Understanding global history branch predictors

Improving the perceptron branch predictor

In 2003-2004, we have begun to explore the potential of the use of the perceptron predictor. Our preliminary work showed that this potential was largely underestimated in the pioneer work from Jiménez and Lin. Then we proposed The MAC-RHSP (Multiply Accumulate Contribution Redundant History Skewed Perceptron) predictor with lower hardware complexity than the perceptron predictor, but much better prediction accuracy. These studies were never published in major conferences, but were the seeds that further lead to GEHL and TAGE predictors.

Related publications:

GEHL and TAGE: Pushing limits on global history predictors

In 2004-2005, we have proposed new global history predictors for exploiting very long global history, in the hundred bits range, first GEHL, then TAGE.

In 2004, the OGEHL and the PPM-like predictor were selected for the 1st CBP contest. They both feature a limited number of tables and exploit very long global histories. The PPM-like predictor uses partial tag matching as the prediction selection function while the OGEHL predictor uses a tree adder. OGEHL was ranked 2nd at 1st CBP contest and won the best practice award.

OGEHL uses a geometric series of history lengths to index prediction tables and a perceptron-like prediction computation. In 2005, we proposed the TAGE predictor that mixes the partial tag matching (and an optimized update policy) with usage of geometric series of history lengths. (L-)TAGE won the 2nd CBP contest in the realistic predictors category in 2006.
For exploring the limits of branch prediction, the GTL predictor was defined. GTL essentially combines a TAGE predictor and an OGEHL predictor. GTL won the 2nd CBP contest in the idealistic predictors category in 2006.

ISL-TAGE derived from TAGE won the 3rd CBP contest in 2006 . We also showed that indirect jumps can be predicted using the same principles as conditional branches through the ITTAGE predictor. The 3 first ranked predictors at the 3rd CBP contest were derived from ITTAGE.

TAGE-SC-L won the 4th CBP contest in 2014 in both the 32Kbits and 256 Kbits categories. It also won the 5th CBP contest in 2016 in both categories.

Related publications:

Exploiting the Inner Most Loop Iteration Counter

For some branches encapsulated in a multidimensional loop, their outcomes are correlated with those of the same branch in neighbor iterations, but in the previous outer loop iteration. The IMLI-based predictor components are practical predictor components to exploit this branch outcome correlation in multidimensional loops. They can be incorporated in TAGE-based predictors or neural predictors.

Branch predictors simulation code

For the 1st Championship Branch Prediction

Branch predictors packaged for the 2nd Championship Branch Prediction

  • realistic predictor: L-TAGE 3.314 misp/KI
  • idealistic predictor GTL 2.717 misp/KI

Branch predictors packaged for the 3rd Championship Branch Prediction

Branch predictors packaged for the 4th Championship Branch Prediction

Branch predictors packaged for the 5th Championship Branch Prediction

Championship Branch Prediction Record

  1. A. Seznec, The O-GEHL Branch Predictor CBP-1, December 2004, 2nd, Best Practice Award
  2. A. Seznec “Looking for limits in branch prediction with the GTL predictor”, ppt presentation, CBP-2, December 2006, Champion unlimited size conditional branch predictor
  3. A. Seznec “A 256 Kbits L-TAGE predictor”, ppt presentation, CBP-2, December 2006, Champion 256Kbits conditional branch predictor
  4. A. Seznec, ”A 64 Kbytes ISL-TAGE branch predictor”, slides, JWAC-2 : Championship Branch Prediction, june 2011, Champion conditional branch predictor
  5. A. Seznec, ”A 64-Kbytes ITTAGE indirect branch predictor”, slides, JWAC-2 : Championship Branch Prediction, june 2011, Champion indirect branch predictor
  6. A.Seznec, “TAGE-SC-L branch predictors”, slides JWAC-4: Championship Branch Prediction, june 2014, Champion 32Kbits and 256 Kbits conditional branch predictor
  7. P. Michaud, A. Seznec , “Pushing the Branch Predictability Limits with the Multi-poTAGE+SC Predictor”, slides Championship Branch Prediction, june 2014, Champion unlimited size conditional branch predictor
  8. André Seznec. TAGE-SC-L Branch Predictors Again. 5th JILP Workshop on Computer Architecture Competitions (JWAC-5): Championship Branch Prediction (CBP-5), Jun 2016, Seoul, South Korea. <http://www.jilp.org/cbp2016/>. <hal-01354253> Champion 32Kbits and 256 Kbits conditional branch predictor
  9. André Seznec. Exploring branch predictability limits with the MTAGE+SC predictor *. 5th JILP Workshop on Computer Architecture Competitions (JWAC-5): Championship Branch Prediction (CBP-5), Jun 2016, Seoul, South Korea. <http://www.jilp.org/cbp2016/>. <hal-01354251> Champion unlimited size conditional branch predictor

Comments are closed.