Published in the Proceedings of the 22nd Annual International Symposium on Computer Architecture June 1995 A Comparative Analysis of Schemes for Correlated Branch Prediction Cliff Young Nicolas Gloy and Michael D Smith Division of Applied Sciences Harvard University Cambridge MA 02138 cyoung ng smith das harvard edu Abstract Why branch prediction schemes perform differently is just as important as how well they perform Only after explaining why a scheme works can one understand appropriate ways to improve or alter it Recent work by McFarling 9 and by Chang et al 4 uses analysis reasoning and experimentation to devise better hardware schemes for correlated branch prediction In particular McFarling 9 noticed significant redundancy in the two level index of the correlation based branch prediction scheme proposed by Pan So and Rahmeh 11 By hashing the branch history with the branch address McFarling s gshare scheme often improves prediction accuracy under the constraint of a fixed size table of predictors Similarly Chang et al 4 noticed that for a fixed size table of predictors branches biased to one particular branch direction more than 95 of the time exhibited better prediction accuracies on a two level adaptive scheme 14 when one decreased the branch history length while the rest of the branches exhibited better prediction accuracies when one increased the branch history length This observation led them to propose several new hybrid branch prediction schemes with better overall prediction accuracies Modern high performance architectures require extremely accurate branch prediction to overcome the performance limitations of conditional branches We present a framework that categorizes branch prediction schemes by the way in which they partition dynamic branches and by the kind of predictor that they use The framework allows us to compare and contrast branch prediction schemes and to analyze why they work We use the framework to show how a static correlated branch prediction scheme increases branch bias and thus improves overall branch prediction accuracy We also use the framework to identify the fundamental differences between static and dynamic correlated branch prediction schemes This study shows that there is room to improve the prediction accuracy of existing branch prediction schemes Keywords branch prediction branch correlation branch stream characteristics 1 Introduction Still it is more difficult to understand the actual workings of today s branch prediction schemes than it needs to be To make it easier to develop optimizations such as those proposed by McFarling 9 and Chang et al 4 we present a unifying framework that allows one to analyze and categorize branch prediction schemes Because the framework is based on a theoretical model of the branch prediction problem it is general enough to encompass all branch prediction schemes proposed to date The framework focuses attention on how a prediction scheme assigns the dynamic branches of the program to individual predictors This information then directs our analysis of and our search for weaknesses in a particular scheme and allows us to isolate and compare different factors that affect prediction accuracy In particular we explore the fundamental differences between hardware and software based branch prediction schemes that exploit branch correlation This analysis suggests several ways to improve the overall prediction accuracy of today s branch prediction schemes Recent work in branch prediction has led to the development of both hardware and software schemes that achieve good prediction accuracy by exploiting branch correlation 4 9 11 14 15 16 17 However little attention has been paid to why these schemes behave better than prior ones and to where further improvements can be made In this paper we describe an analytic framework that helps answer these questions based on the fundamental characteristics of the branch prediction problem In addition we use the observations based upon this framework to indicate potentiallyfruitful research directions that will allow computer architects to improve branch prediction accuracy Further improvements in branch prediction accuracy will enhance the effectiveness of global instruction schedulers and the performance of multiple instructionissue machines Branch prediction addresses two basic problems predicting the direction of conditional branches and quickly fetching instructions from the predicted target These problems can be addressed separately and in this paper we limit ourselves to the former In other words we consider a branch prediction scheme to be a technique for improving performance by anticipating the outcome of conditional branches Other work has shown how to couple a branch prediction scheme with a branch target buffer to eliminate the performance penalties of branches 7 Section 2 describes our framework for classifying and analyzing branch prediction schemes To demonstrate the generality of our framework Section 2 presents many of today s popular branch prediction schemes in framework terms In Section 3 we use the framework to explore the issues in when and thus why static schemes for correlated branch prediction work Section 4 goes on to compare the differences between static and dynamic schemes for correlated branch prediction As an example of the power of our approach we also describe changes to correlation based static and dynamic prediction schemes that improve their overall prediction accuracy Section 5 summarizes the findings of this work 1 2 A Framework for Branch Prediction 2 2 Given a conditional branch in a program the goal of a branch prediction scheme is to predict accurately the outcome of that conditional branch i e that the branch will take or that the branch will fall through 1 The most accurate branch prediction schemes predict the next action of a branch based on some function of the past actions of that branch and possibly other branches in the program To understand the capabilities of these branch prediction schemes and to compare competing schemes in a meaningful manner we must be able to identify and quantify the important properties of branch prediction schemes To achieve this goal this section defines a set of mathematical tools that allow us to analyze program and branch behavior in an abstract manner 2 1 Based on our formal definition of a prediction scheme the key to building a more accurate prediction scheme involves the selection of the right
View Full Document
Unlocking...