Elastic history buffer: a low-cost method to improve branch prediction accuracy
- 23 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Two-level dynamic branch predictors try to predict the outcomes of conditional branches using both a table of state counters associated with specific branch instructions and a buffer of recent branch outcomes to correlate the counters with specific branch histories. However there is always a question of how much correlation to use, and some programs benefit from higher levels of correlation than others. This paper presents the Elastic History Buffer (EHB), a low-cost yet effective scheme that can exploit the property that each branch instruction may have a different degree of correlation with other branches, while keeping the simple structure of a single global branch history. We have simulated the EHB on SPECint92 for two architectures. On average, the EHB has 25% fewer mispredictions than fixed-correlation schemes and 10% fewer than frequency-based branch classification schemes. With limited hardware (1KB), the EHB is close to the optimum measured by repeating the experiments on an “oracle” two-level predictorKeywords
This publication has 6 references indexed in Scilit:
- A Study of the EARTH-MANNA Multithreaded SystemInternational Journal of Parallel Programming, 1996
- The performance of counter- and correlation-based schemes for branch target buffersIEEE Transactions on Computers, 1995
- Branch classificationPublished by Association for Computing Machinery (ACM) ,1994
- A comparison of dynamic branch predictors that use two levels of branch historyPublished by Association for Computing Machinery (ACM) ,1993
- Improving the accuracy of dynamic branch prediction using branch correlationPublished by Association for Computing Machinery (ACM) ,1992
- Branch Prediction Strategies and Branch Target Buffer DesignComputer, 1984