1A Comparative Analysis of Schemesfor Correlated Branch PredictionCliff Young, Nicolas Gloy, and Michael D. SmithDivision of Applied SciencesHarvard University, Cambridge, MA 02138{cyoung, ng, smith}@das.harvard.eduAbstractModern high-performance architectures require extremely accuratebranch prediction to overcome the performance limitations of con-ditional branches. We present a framework that categorizes branchprediction schemes by the way in which they partition dynamicbranches and by the kind of predictor that they use. The frameworkallows us to compare and contrast branch prediction schemes, andto analyze why they work. We use the framework to show how astatic correlated branch prediction scheme increases branch biasand thus improves overall branch prediction accuracy. We also usethe framework to identify the fundamental differences betweenstatic and dynamic correlated branch prediction schemes. Thisstudy shows that there is room to improve the prediction accuracyof existing branch prediction schemes.Keywords: branch prediction, branch correlation, branch streamcharacteristics.1 IntroductionRecent work in branch prediction has led to the development ofboth hardware and software schemes that achieve good predictionaccuracy by exploiting branch correlation [4, 9, 11, 14, 15, 16, 17].However, little attention has been paid to why these schemesbehave better than prior ones and to where further improvementscan be made. In this paper, we describe an analytic framework thathelps answer these questions based on the fundamental character-istics of the branch prediction problem. In addition, we use theobservations based upon this framework to indicate potentially-fruitful research directions that will allow computer architects toimprove branch prediction accuracy. Further improvements inbranch prediction accuracy will enhance the effectiveness of globalinstruction schedulers and the performance of multiple-instruction-issue machines.Branch prediction addresses two basic problems: predicting thedirection of conditional branches, and quickly fetching instructionsfrom the predicted target. These problems can be addressed sepa-rately, and in this paper, we limit ourselves to the former. In otherwords, we consider a branch prediction scheme to be a techniquefor improving performance by anticipating the outcome of condi-tional branches. Other work has shown how to couple a branchprediction scheme with a branch target buffer to eliminate the per-formance penalties of branches [7].Why branch prediction schemes perform differently is just asimportant as how well they perform. Only after explaining why ascheme works can one understand appropriate ways to improve oralter it. Recent work by McFarling [9] and by Chang et al. [4] usesanalysis, reasoning, and experimentation to devise better hardwareschemes for correlated branch prediction. In particular, McFarling[9] noticed significant redundancy in the two-level index of thecorrelation-based branch prediction scheme proposed by Pan, So,and Rahmeh [11]. By hashing the branch history with the branchaddress, McFarling’s gshare scheme often improves predictionaccuracy under the constraint of a fixed-size table of predictors.Similarly, Chang et al. [4] noticed that, for a fixed-size table of pre-dictors, branches biased to one particular branch direction morethan 95% of the time exhibited better prediction accuracies on atwo-level adaptive scheme [14] when one decreased the branchhistory length, while the rest of the branches exhibited better pre-diction accuracies when one increased the branch history length.This observation led them to propose several new hybrid branchprediction schemes with better overall prediction accuracies.Still, it is more difficult to understand the actual workings oftoday’s branch prediction schemes than it needs to be. To make iteasier to develop optimizations such as those proposed by McFar-ling [9] and Chang et al. [4], we present a unifying framework thatallows one to analyze and categorize branch prediction schemes.Because the framework is based on a theoretical model of thebranch prediction problem, it is general enough to encompass allbranch prediction schemes proposed to date. The frameworkfocuses attention on how a prediction scheme assigns the dynamicbranches of the program to individual predictors. This informationthen directs our analysis of and our search for weaknesses in a par-ticular scheme, and allows us to isolate and compare different fac-tors that affect prediction accuracy. In particular, we explore thefundamental differences between hardware- and software-basedbranch prediction schemes that exploit branch correlation. Thisanalysis suggests several ways to improve the overall predictionaccuracy of today’s branch prediction schemes.Section 2 describes our framework for classifying and analyzingbranch prediction schemes. To demonstrate the generality of ourframework, Section 2 presents many of today’s popular branchprediction schemes in framework terms. In Section 3, we use theframework to explore the issues in when (and thus why) staticschemes for correlated branch prediction work. Section 4 goes onto compare the differences between static and dynamic schemesfor correlated branch prediction. As an example of the power ofour approach, we also describe changes to correlation-based staticand dynamic prediction schemes that improve their overall predic-tion accuracy. Section 5 summarizes the findings of this work.Published in the Proceedings of the 22ndAnnual International Symposium onComputer Architecture, June 1995.22 A Framework for Branch PredictionGiven a conditional branch in a program, the goal of a branch pre-diction scheme is to predict accurately the outcome of that condi-tional branch (i.e. that the branch will take or that the branch willfall through).1 The most accurate branch prediction schemes pre-dict the next action of a branch based on some function of the pastactions of that branch and possibly other branches in the program.To understand the capabilities of these branch prediction schemesand to compare competing schemes in a meaningful manner, wemust be able to identify and quantify the important properties ofbranch prediction schemes. To achieve this goal, this sectiondefines a set of mathematical tools that allow us to analyze pro-gram and branch behavior in an abstract manner.2.1 Basic Definitions and GoalsLet a branch execution , be a pairconsisting of an identifier and a
View Full Document
Unlocking...