The Cascaded Predictor: Economic and Adaptive Branch Target Prediction

. Two-level predictors improve branch prediction accuracy by allowing predictor tables to hold multiple predictions per branch. Unfortunately, the accuracy of such predictors is impaired by two detrimental effects. Capacity misses increase since each branch may occupies entries proportional to the number of different path histories leading up to the branch. The working set of a given program therefore increases with history length. Similarly, cold start misses increase with history length since the predictor must initially store a prediction separately for each history pattern. We describe a new predictor architecture, cascaded branch prediction, which can alleviate both of these effects while retaining the superior accuracy of two-level predictors. Cascaded predictors dynamically classify and predict easily predicted branches using an inexpensive predictor, preventing insertion of these branches into a more powerful second stage predictor. We show that for pathbased indirect branch pr..