Combining Static and Dynamic Branch Prediction to Reduce Destructive Aliasing

Harish Patil and Joel Emer
Alpha Development Group, Compaq Computer Corporation

Dynamic branch predictor accuracy is known to be degraded by the problem of aliasing that occurs when two branches with different run-time behavior share an entry in the dynamic predictor and that sharing results in mispredictions for the branches. In this paper, we analyse the use of static prediction of certain branches to relieve the aliasing problem in dynamic predictors. We report on our experience with using profile-directed feedback to select branches that can profitably be predicted statically in combination with some well known dynamic branch predictors. We found prediction rate improvements of up to 75% for a simple branch predictor (ghist) and up to 14% for a very aggressive hybrid predictor (2bcgskew) for certain programs.

Full paper in pdf format, postscript format..