Improving Branch Predictors by Correlating on Data Values Timothy H Heil1 Zak Smith2 J E Smith1 1Electrical 2VLSI and Computer Engineering University of Wisconsin Madison Madison WI 53706 heilt jes ece wisc edu Abstract Branch predictors typically use combinations of branch PC bits and branch histories to make predictions Recent improvements in branch predictors have come from reducing the effect of interference i e multiple branches mapping to the same table entries In contrast the branch difference predictor BDP uses data values as additional information to improve the accuracy of conditional branch predictors The BDP maintains a history of differences between branch source register operands and feeds these into the prediction process An important component of the BDP is a rare event predictor REP which reduces learning time and table interference An REP is a cache like structure designed to store patterns whose predictions differ from the norm Initially ideal interference free predictors are evaluated to determine how data values improve correlation Next execution driven simulations of complete designs realize this potential The BDP reduces the misprediction rate of five SPEC95 integer benchmarks by up to 33 compared to gshare and by up to 15 compared to Bi Mode predictors 1 Introduction Conditional branch prediction is an important technique for improving processor performance Correct branch predictions avoid control dependences and provide a smooth flow of instructions to be executed On the other hand branch mispredictions halt fetching of usable instructions until the branch outcome is known In outof order processors this serializes program execution dividing the out of order instruction window into sequentially executed segments Since these problems become worse with increasing window size improved branch prediction is considered a key hurdle for future microarchitectures Consequently there continues to be ongoing research and progress in branch prediction mechanisms The first dynamic branch predictors 23 primarily relied on local history information to make their predictions Since that time conditional branch predictors have undergone steady improvements These improvements fall into three basic categories 1 Technology Lab Hewlett Packard 3404 E Harmony Rd Ft Collins CO 80528 9599 zak fc hp com adding global path and history information 19 24 27 2 refining the ways that global and local history are combined 3 15 3 reducing table interference through more intelligent table indexing schemes 5 10 12 16 22 Virtually all the conditional branch predictors proposed to date use control flow information as basic inputs either in the form of branch outcomes or branch PCs In effect proposed predictors combine the same type of information in increasingly clever ways And despite the steady improvements that have been made many branches are still mispredicted and branch prediction remains an impediment to performance To find new ways to improve branch prediction we first took a microscopic view examining the execution of individual branches to understand why some conditional branches are difficult to predict For many important branches PCs and branch outcomes alone do not contain the right information or the information is not in the right form However many of these branches become easily predictable if data value information can be used This led us to develop a new class of branch predictors that use data values a development culminating in the branch difference predictor BDP the topic of this paper A straightforward method of integrating data values into branch prediction is what we refer to as speculative branch execution illustrated in Fig 1 With this type of predictor a conventional data value predictor 13 20 21 26 is first used to predict the input values for a branch instruction then the branch instruction is evaluated using the predicted values Because conventional branch predictors predict some branches very well a chooser selects between a conventional predictor and prediction through speculative branch execution We initially considered this mechanism 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 into the branch predictor In effect the predictor correlates on data values similar to the way conventional predictors correlate on global branch history This method has a couple of advantages First it leads to a lower latency predictor than speculative branch execution As explained in Section 3 1 all predictor tables are accessed in parallel on selected branches 1 The rest of this paper is organized as follows Section 2 illustrates reasons for branch mispredictions with examples motivating the use of data values Section 3 describes the branch difference predictor in detail Section 4 reports the potential performance of the proposed predictor using trace driven simulations of interference free predictors Section 5 reports results of execution driven simulations using fixed size predictors Section 6 discusses future research and concludes the paper Chooser Global Branch History Branch Predictor Branch PC Data Value Predictor Data Value History 2 Why branches are mispredicted Branch Execution Fig 1 Branch prediction via speculative execution while speculative branch execution requires one or two serial tables accesses depending on the data value predictor used followed by execution of the branch instruction Second it allows some branches to be predicted using combined branch outcomes and data value information speculative branch execution as shown in Fig 2 uses either branch history or data values but not both As a result we found the direct method Fig 2 provides better prediction accuracy even when compared to speculative branch execution using a data value predictor of unlimited size and an oracle chooser that selects the best prediction mechanism for each static branch 9 Global Branch History Branch PC Predictor Data Value History Fig 2 Using data values for branch prediction directly Prediction through speculative branch execution was recently 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 of using global history and data value history together by developing a chooser based on path information Other related work uses compiler synthesized dynamic branch prediction 1 as a software
View Full Document
Unlocking...