Cached Two-Level Adaptive Branch Predictors with Multiple Stages

C. Egan, G.B. Steven, L. Vintan

    Research output: Contribution to journalArticlepeer-review

    2 Citations (Scopus)
    53 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)179-191
    JournalLecture Notes in Computer Science (LNCS)
    Publication statusPublished - 2002


    Dive into the research topics of 'Cached Two-Level Adaptive Branch Predictors with Multiple Stages'. Together they form a unique fingerprint.

    Cite this