Cached Two-Level Adaptive Branch Predictors with Multiple Stages

During the last decade, the accuracy of branch predictors was significantly improved by the development of Two-Level Adaptive Branch Predictors. However, although these predictors deliver very high prediction rates, they have several disadvantages. Firstly, the size of the secondlevel Pattern History Table (PHT) increases exponentially as a function of history register length and therefore becomes very costly if a large amount of branch history is exploited. Secondly, many of the prediction counters in the PHT are never used. Thirdly, predictions are frequently generated from non-initialised counters. Finally, several branches may update the same counter, resulting in interference between branch predictions. In this paper, we quantify the performance of a novel family of multi-stage Two-Level Adaptive Predictors. In each two-level predictor, the PHT is replaced by a Prediction Cache. Unlike a PHT, a Prediction Cache saves only relevant branch prediction information. Furthermore, predictions are never based on uninitialised entries and interference between branches is eliminated. In the case of a Prediction Cache miss in the first stage, our two-stage predictors uses a default two-bit prediction counter stored in a second stage. We demonstrate that a two-stage Cached Predictor is more accurate than a conventional two-level predictor and quantify the crucial contribution made by the second prediction stage in achieving this high accuracy. We then extend our Cached Predictor by adding a third stage and demonstrate that a Three-Stage Cached Predictor further improves the accuracy of cached predictors.