CPE 631 Branch Prediction Electrical and Computer Engineering University of Alabama in Huntsville Aleksandar Milenkovic milenka ece uah edu http www ece uah edu milenka The Case for Branch Prediction Dynamic scheduling increases the amount of ILP control dependence becomes the limiting factor Multiple issue processors AM LaCASA Branches will arrive up to N times faster in an n issue processor Amdahl s Law relative impact of the control stalls will be larger with the lower potential CPI in an n issue processor What have we done Static schemes for dealing with branches compiler optimizes the the branch behavior by scheduling it at compile time 2 7 Branch Prediction Schemes 1 bit Branch Prediction Buffer 2 bit Branch Prediction Buffer Correlating Branch Prediction Buffer Tournament Branch Predictor Branch Target Buffer Integrated Instruction Fetch Units Return Address Predictors AM LaCASA 3 Basic Branch Prediction 1 Performance accuracy cost of misprediction Branch History Table a small table of 1 bit values indexed by the lower bits of PC address AM LaCASA Says whether or not branch taken last time Useful only to reduce branch delay when it is longer than the time to compute the possible target PC No address check BHT has no address tags so the prediction bit may have been put by another branch that has the same low order bits Prediction is a hint assumed to be correct fetching begins in the predicted direction if it turns out to be wrong the prediction bit is inverted and stored back 4 Basic Branch Prediction 2 Problem in a loop 1 bit BHT will cause 2 mispredictions avg is 9 iterations before exit AM LaCASA End of loop case when it exits instead of looping as before First time through loop on next time through code when it predicts exit instead of looping Only 80 accuracy even if loop 90 of the time Ideally for highly regular branches the accuracy of predictor taken branch frequency Solution use two bit prediction schemes 5 2 bit Scheme States in a two bit prediction scheme T Predict Taken NT Predict Taken T T NT NT Predict Not Taken AM LaCASA Predict Not Taken T NT Red stop not taken Green go taken Adds hysteresis to decision making process 6 BHT Implementation 1 Small special cache accessed with the instruction address during the IF pipe stage 2 Pair of bits attached to each block in the instruction cache and fetched with the instruction AM LaCASA How many branches per instruction Complexity Instruction is decoded as branch and branch is predicted as taken fetch from the target as soon as the PC is known Note Does this scheme help for simple MIPS 7 BHT Performance Prediction accuracy of 2 bit predictor with 4096 entries is ranging from over 99 to 82 or misprediction rate of 1 to 18 Real impact on performance prediction accuracy branch cost branch frequency How to improve prediction accuracy AM LaCASA Increase the size of the buffer number of entries Increase the accuracy for each prediction increase the number of bits Both have limited impact 8 Case for Correlating Predictors Basic two bit predictor schemes use recent behavior of a branch to predict its future behavior Improve the prediction accuracy look also at recent behavior of other branches if aa 2 aa 0 AM LaCASA L1 if bb 2 bb 0 if aa bb L2 subi R3 R1 2 bnez R3 L1 b1 add R1 R0 R0 subi R3 R2 2 bnez R3 L2 b2 add R2 R0 R0 sub R3 R1 R2 beqz R3 L3 b3 b3 is correlated with b1 and b2 If b1 and b2 are both untaken then b3 will be taken Use correlating predictors or two level predictors 9 An Example L1 L2 AM LaCASA if d 0 d 1 Initial value of d d 0 b1 Value of d before b2 d 1 b2 if d 1 0 Yes NT 1 Yes NT 1 No T 1 Yes NT bnez R1 L1 b1 2 No T 2 No T addi R1 R0 1 if b1 is NT then b2 is NT subi R3 R1 1 bnez R3 L2 b2 Behavior of one bit Standard Predictor initialized to not taken d alternates between 0b1 and 2 b2 d b1 b1 New b2 new b2 prediction action prediction prediction action prediction 2 NT T T NT T T 0 T NT NT T NT NT 2 NT T T NT T T 0 T NT NT T NT NT All branches are mispredicted 10 An Example Introduce one bit of correlation d AM LaCASA Each branch has two separate prediction bits one prediction assuming the last branch executed was not taken and another prediction assuming it was taken Predictio n bits Prediction if last branch NT Prediction if last branch T NT NT NT NT NT T NT T T NT T NT T T T T Behavior of one bit predictor with one bit of correlation initialized to NT NT Assume last branch NT b1 b1 New b1 b2 b2 new b2 prediction action prediction NT prediction action prediction b1 T 2 NT NT T T NT NT NT T NT T b2 T 0 T NT NT T NT NT T NT NT T b1 NT 2 T NT T T NT NT T T NT T b2 NT 0 T NT NT T NT NT T NT NT T b1 T b2 T b1 NT b2 NT Only misprediction is on the first iteration 11 1 1 Predictor 1 1 predictor from the previous example m n predictor AM LaCASA Uses the behavior of the last branch to choose from among a pair of one bit branch predictors Uses the behavior of the last m branches to choose from among 2m predictors each of which is a n bit predictor for a single branch Global history of the most recent branches can be recorded in an m bit shift register each bit records whether a branch is taken or not 12 2 2 Predictor 2 bit global history to choose from among 4 predictors for each branch address 2 bit local predictor 2 2 predictor is implemented as a linear memory array that is 2 bits wide the indexing is done by AM concatenating the global history bits and the number of required bits from the branch address LaCASA Branch address 4 bits 2 bits per branch local predictors Prediction Prediction 2 bit global branch history 01 not taken then taken 13 Fair Predictor Comparison Compare predictors that use the same number of state bits AM LaCASA number of state bits for m n 2m n number of prediction entries number of state bits for 0 n n number of prediction entries Example How many branch selected entries are in a 2 2 predictor that has a total of 8K state bits 22 2 number of entries 8K number of branch selected entries is 1K 14 Accuracy of Different Schemes 20 Frequency of Mispredictions Frequency of Mispredictions 18 14 12 LaCASA 11 10 8 6 6 6 6 5 5 4 4 2 AM 4096 Entries 2 bit BHT Unlimited Entries 2 bit BHT …