Prophet/Critic Hybrid Branch Prediction

This paper introduces the prophet/critic hybrid condi-tional branch predictor, which has two component pre-dictors that play the role of either prophet or critic. The prophet is a conventional predictor that uses branch history to predict the direction of the current branch. Further ac-cesses of the prophet yield predictions for the branches fol-lowing the current one. Predictions for the current branch and the ones that follow are collectively known as the branch’s future. They are actually a prophecy, or predicted branch future. The critic uses both the branch’s history and future to give a critique of the prophet’s prediction for the current branch. The critique, either agree or disagree, is used to generate the final prediction for the branch. Our results show an 8K+8K byte prophet/critic hybrid has 39 % fewer mispredicts than a 16K byte 2Bc-gskew predictor—a predictor similar to that of the proposed Com-paq Alpha EV8 processor—across a wide range of appli-cations. The distance between pipeline flushes due to mis-predicts increases from one flush per 418 micro-operations (uops) to one per 680 uops. For gcc, the percentage of mis-predicted branches drops from 3.11 % to 1.23%. On a ma-chine based on the Intel R Pentium R 4 processor, this im-proves uPC (Uops Per Cycle) by 7.8 % (18 % for gcc) and reduces the number of uops fetched (along both correct and incorrect paths) by 8.6%. 1