Trading conflict and capacity aliasing in conditional branch predictors
- 1 May 1997
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 25 (2), 292-303
- https://doi.org/10.1145/384286.264211
Abstract
As modern microprocessors employ deeper pipelines and issue multiple instructions per cycle, they are becoming increasingly dependent on accurate branch prediction. Because hardware resources for branch-predictor tables are invariably limited, it is not possible to hold all relevant branch history for all active branches at the same time, especially for large workloads consisting of multiple processes and operating-system code. The problem that results, commonly referred to as aliasing in the branch-predictor tables, is in many ways similar to the misses that occur in finite-sized hardware caches.In this paper we propose a new classification for branch aliasing based on the three-Cs model for caches, and show that conflict aliasing is a significant source of mispredictions. Unfortunately, the obvious method for removing conflicts --- adding tags and associativity to the predictor tables --- is not a cost-effective solution.To address this problem, we propose the skewed branch predictor, a multi-bank, tag-less branch predictor, designed specifically to reduce the impact of conflict aliasing. Through both analytical and simulation models, we show that the skewed branch predictor removes a substantial portion of conflict aliasing by introducing redundancy to the branch-predictor tables. Although this redundancy increases capacity aliasing compared to a standard one-bank structure of comparable size, our simulations show that the reduction in conflict aliasing overcomes this effect to yield a gain in prediction accuracy. Alternatively, we show that a skewed organization can achieve the same prediction accuracy as a standard one-bank organization but with half the storage requirements.Keywords
This publication has 13 references indexed in Scilit:
- Analysis of branch prediction via data compressionPublished by Association for Computing Machinery (ACM) ,1996
- An analysis of dynamic branch prediction schemes on system workloadsPublished by Association for Computing Machinery (ACM) ,1996
- Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switchesPublished by Association for Computing Machinery (ACM) ,1996
- Instruction fetchingPublished by Association for Computing Machinery (ACM) ,1995
- A comparative analysis of schemes for correlated branch predictionPublished by Association for Computing Machinery (ACM) ,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
- Alternative implementations of two-level adaptive branch predictionPublished by Association for Computing Machinery (ACM) ,1992
- Two-level adaptive training branch predictionPublished by Association for Computing Machinery (ACM) ,1991