Improving Indirect Branch Prediction With Source- and Arity-based Classification and Cascaded Prediction

Karel Driesen, Urs Hölzle

Abstract: Indirect branch prediction is likely to become more critical to program performance because indirect branches occur more frequently in object-oriented programs. We study indirect branch behavior in both procedural and object-oriented programs in order to build more accurate predictor architectures. First we use a statically classifying hybrid predictor with a shared history table and separate history buffers tuned for different branch classes. Opcode-based classification, which classifies branches according to their source code origin, leads to only minor improvements in prediction performance. Arity-based classification, which classifies branches according to the number of different targets, obtains better performance, competitive with recently proposed dual- path length hybrid predictors. Finally, we present cascaded branch predictors, which dynamically classifies easily predicted branches using an inexpensive predictor. By preventing insertion of these branches into a more powerful second stage predictor, cascaded prediction obtains prediction rates equivalent to that of the previously best known indirect branch predictors, but at roughly half the cost. Specifically, a cascaded predictor with a total of 288 history table entries achieves 89.3% prediction accuracy.

Technical Report TRCS98-07, Computer Science Department, University of California, Santa Barbara, 15 March 1998

To get the PostScript file, click here (PDF is here).