Trading conflict and capacity aliasing in conditional branch predictors

As modern microprocessors employ deeper pipelines and is-sue multiple instructions per cycle, they are becoming increasingly dependent on accurate branch prediction. Because hardware re-sources 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 multi-ple 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 hard-ware caches. In this paper we propose a new classification for branch alias-ing 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 asso-ciativity to the predictor tables – is not a cost-effective solution. To address this problem, we propose the skewed branch predic-tor, 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 re-dundancy to the branch-predictor tables. Although this redundancy increases capacity aliasing compared to a standard one-bank struc-ture 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 or-ganization but with half the storage requirements