Improving Branch Predictors by Correlating on Data ValuesTimothy H. Heil1, Zak Smith2, J. E. Smith11Electrical and Computer EngineeringUniversity of Wisconsin-MadisonMadison, WI 53706{heilt,jes}@ece.wisc.edu2VLSI Technology Lab, Hewlett-Packard3404 E. Harmony Rd.Ft. Collins, CO [email protected] predictors typically use combinations ofbranch PC bits and branch histories to make predictions.Recent improvements in branch predictors have comefrom reducing the effect of interference, i.e. multiplebranches mapping to the same table entries. In contrast,the branch difference predictor (BDP) uses data values asadditional information to improve the accuracy of condi-tional branch predictors. The BDP maintains a history ofdifferences between branch source register operands, andfeeds these into the prediction process.An important component of the BDP is a rare eventpredictor (REP) which reduces learning time and tableinterference. An REP is a cache-like structure designedto store patterns whose predictions differ from the norm.Initially, ideal interference-free predictors areevaluated to determine how data values improve correla-tion. Next, execution driven simulations of completedesigns realize this potential. The BDP reduces themisprediction rate of five SPEC95 integer benchmarks byup to 33% compared to gshare and by up to 15% com-pared to Bi-Mode predictors.1. IntroductionConditional branch prediction is an important tech-nique for improving processor performance. Correctbranch predictions avoid control dependences and providea smooth flow of instructions to be executed. On theother hand, branch mispredictions halt fetching of usableinstructions until the branch outcome is known. In out-of-order processors this serializes program execution,dividing the out-of-order instruction window into sequen-tially executed segments. Since these problems becomeworse with increasing window size, improved branchprediction is considered a key hurdle for future microar-chitectures. Consequently, there continues to be ongoingresearch (and progress) in branch prediction mechanisms.The first dynamic branch predictors [23] primarilyrelied on local history information to make their predic-tions. Since that time, conditional branch predictors haveundergone steady improvements. These improvementsfall into three basic categories.(1) adding global path and history information [19,24, 27](2) refining the ways that global and local history arecombined [3, 15](3) reducing table interference through more intelli-gent table indexing schemes [5, 10, 12, 16, 22]Virtually all the conditional branch predictors pro-posed to date use control flow information as basic inputseither in the form of branch outcomes or branch PCs. Ineffect, proposed predictors combine the same type ofinformation in increasingly clever ways. And, despite thesteady improvements that have been made, manybranches are still mispredicted, and branch predictionremains an impediment to performance.To find new ways to improve branch prediction, wefirst took a microscopic view, examining the execution ofindividual branches to understand why some conditionalbranches are difficult to predict. For many importantbranches, PCs and branch outcomes alone do not containthe right information, or the information is not in the rightform. However, many of these branches become easilypredictable if data-value information can be used. Thisled us to develop a new class of branch predictors that usedata values; a development culminating in the branchdifference predictor (BDP) -- the topic of this paper.A straightforward method of integrating data valuesinto branch prediction is what we refer to as speculativebranch execution, illustrated in Fig. 1. With this type ofpredictor, a conventional data-value predictor [13, 20, 21,26] is first used to predict the input values for a branchinstruction, then the branch instruction is evaluated usingthe predicted values. Because conventional branch predic-tors predict some branches very well, a chooser selectsbetween a conventional predictor and prediction throughspeculative branch execution. We initially considered thismechanism [9], but ultimately chose a different approach.We chose to pursue the method illustrated in Fig. 2,where data-value history information is fed directly intothe branch predictor. In effect, the predictor correlates ondata values similar to the way conventional predictorscorrelate on global branch history. This method has a cou-ple of advantages. First, it leads to a lower latency predic-tor than speculative branch execution. As explained inSection 3.1, all predictor tables are accessed in parallel,Branch PCGlobal Branch HistoryPredictorData-ValuePredictorBranchChooserBranch ExecutionData Value HistoryFig. 1. Branch prediction via speculative exe-cution.while speculative branch execution requires one or twoserial tables accesses (depending on the data-value pred-ictor used), followed by execution of the branch instruc-tion. Second, it allows some branches to be predictedusing combined branch outcomes and data value informa-tion; speculative branch execution, as shown in Fig. 2,uses either branch history or data values, but not both.Asa result we found the direct method (Fig. 2) providesbetter prediction accuracy, even when compared to specu-lative branch execution using a data-value predictor ofunlimited size and an oracle chooser that selects the bestprediction mechanism for each static branch [9].Branch PC PredictorGlobal Branch HistoryData Value HistoryFig. 2. Using data values for branch pred-iction directly.Prediction through speculative branch execution wasrecently pursued independently by Gonzalez y Gonzalez[7], and a similar scheme was studied by Farcy et al. [6].Gonzalez and Gonzalez also recognized the importance ofusing global history and data-value history together bydeveloping a chooser based on path information.Other related work uses compiler synthesized dynamicbranch prediction [1] as a software-based approach forusing data values. Compiler synthesized prediction usesan execution profile to guide a compiler in insertinginstructions into the binary that compute branch-specificprediction functions. The results of these functions, whichare based on register values, are supplied to hardwarepredictors at runtime through ISA extensions. Thismechanism is evaluated for a class of prediction functionson selected branches [1].The rest of this paper is organized as follows. Section2
View Full Document
Unlocking...