Abstract
Accurate Indirect Branch Prediction
by: Karel Driesen and Urs Hï½lzle
Abstract:
Indirect branch prediction is likely to become increasingly important in thefuture because indirect branches occur more frequently in object-orientedprograms. With misprediction rates of around 25% on current processors,indirect branches can incur a significant fraction of branch mispredictionoverhead even though they remain less frequent than the more predictableconditional branches. We investigate a wide range of two-level predictorsdedicated exclusively to indirect branches. Starting with predictors that usefull-precision addresses and unlimited tables, we progressively introducehardware constraints and minimize the loss of predictor performance at eachstep. For programs from the SPECint95 suite as well as a suite of large C++applications, a two-level predictor achieves a misprediction rate of 9.8% witha 1K-entry table and 7.3% with an 8K-entry table, representing more than athreefold improvement over an ideal BTB. A hybrid predictor further reducesthe misprediction rates to 8.98% and 5.95%, respectively.
Keywords:
indirect branch prediction, Holzle, Hoelzle
Date:
December 1997
Document: 1997-19
