Multi-stage Cascaded Prediction

Two-level predictors deliver highly accurate conditional branch prediction,indirect branch target prediction and value prediction. Accurate predictionenables speculative execution of instructions, a technique that increasesinstruction level parallelism. Unfortunately, the accuracy of a two-levelpredictor is limited by the cost of the predictor table that storesassociations between history patterns and target predictions. Two-stagecascaded prediction, a recently proposed hybrid prediction architecture, usespattern filtering to reduce the cost of this table while preserving predictionaccuracy. In this study we generalize two-stage prediction to multi-stageprediction.We first determine the limit of accuracy on an indirect branch trace using amulti-stage predictor with an unlimited hardware budget. We then investigatepractical cascaded predictors with limited tables and a small number of stages.Compared to two-level prediction, multi-stage cascaded prediction deliverssuperior prediction accuracy for any given total table entry budget weconsidered.In particular, a 512-entry three-stage cascaded predictor reaches 92% accuracy,reducing table size by a factor of four compared to a two-level predictor. At1.5K entries, a three-stage predictor reaches 94% accuracy, the hit rate of ahypothetical two-level predictor with an unlimited, fully associative predictortable. At 6K entries, accuracy increases to 95%, the limit achieved by anidealized twelve-stage cascaded predictor with an unlimited hardware budget.These results indicate that highly accurate indirect branch target predictionis now well within the capability of current hardware technology.