The Cascaded Predictor: Economic and Adaptive Branch TargetPrediction

Two-level predictors improve branch prediction accuracy by allowing predictortables to hold multiple predictions per branch. Unfortunately, the accuracy ofsuch predictors is impaired by two detrimental effects. Capacity missesincrease since each branch may occupies entries proportional to the number ofdifferent path histories leading up to the branch. The working set of a givenprogram therefore increases with history length. Similarly, cold start missesincrease with history length since the predictor must initially store aprediction separately for each history pattern.We describe a new predictor architecture, cascaded branch prediction, which canalleviate both of these effects while retaining the superior accuracy oftwo-level predictors. Cascaded predictors dynamically classify and predicteasily predicted branches using an inexpensive predictor, preventing insertionof these branches into a more powerful second stage predictor. We show thatfor path-based indirect branch predictors, cascaded prediction obtainsprediction rates equivalent to that of two-level predictors at approximatelyone fourth the cost. For example, a cascaded predictor with 64+1024 entriesachieves the same prediction accuracy as a 4096-entry two-level predictor.Although we have evaluated cascaded prediction only on indirect branches, webelieve that it could also improve conditional branch prediction and valueprediction.