Last Time Predictor. Last time predictor- Single bit per branch (stored in BTB)Indicates which direction branch went last time it executedTTTTTTTTTTNNNNNNNNNN → 90% accuracyAlways mispredicts the last iteration and the firstiteration of a loop branch Accuracy for a loop with N iterations = (N-2)/N+ Loop branches for loops with large number ofiterations-- Loop branches for loops will small number of iterationsTNTNTNTNTNTNTNTNTNTN >0% accuracyLast-time predictor CPl=[1+(0.20*0.15) *2] =1.06 (Assuming 85% accuracy)ComputerArchitecture16
Computer Architecture Last Time Predictor • Last time predictor – Single bit per branch (stored in BTB) – Indicates which direction branch went last time it executed TTTTTTTTTTNNNNNNNNNN à 90% accuracy • Always mispredicts the last iteration and the first iteration of a loop branch – Accuracy for a loop with N iterations = (N-2)/N + Loop branches for loops with large number of iterations - Loop branches for loops will small number of iterations TNTNTNTNTNTNTNTNTNTN à 0% accuracy 16 Last-Lme predictor CPI = [ 1 + (0.20*0.15) * 2 ] = 1.06 (Assuming 85% accuracy)
Implementing the Last-Time PredictorBTB idxtagN-bitOneBittagBTBtablePerbranchtaken?PC+4nextPcThe1-bit BHT (BranchHistoryTable)entry isupdatedwiththe correct outcomeaftereachexecutionof abranchComputerArchitecture17
Computer Architecture Implementing the Last-Time Predictor 17 BTB BTB idx N-bit tag table 1 0 PC+4 nextPC = The 1-bit BHT (Branch History Table) entry is updated with the correct outcome a_er each execuLon of a branch tag One Bit Per branch taken?
State Machine for Last-Time PredictionactuallytakenpredictactuallypredictactuallynotnottakentakentakentakenactuallynottakenComputerArchitecture18
Computer Architecture State Machine for Last-Time Prediction 18 predict taken predict not taken actually not taken actually taken actually taken actually not taken
Improving the Last Time PredictorProblem: A last-time predictor changes its predictionfrom T→>NT or NT>T too quicklyeven though the branch may be mostly taken or mostly nottaken Solution Idea: Add hysteresis to the predictor so thatprediction does not change on a single differentoutcome- Use two bits to track the history of predictions for a branchinstead of a single bit- Can have 2 states for T or NT instead of 1 state for eachSmith, "A Study of Branch Prediction Strategies," ISCA1981.ComputerArchitecture19
Computer Architecture Improving the Last Time Predictor • Problem: A last-time predictor changes its prediction from TàNT or NTàT too quickly – even though the branch may be mostly taken or mostly not taken • Solution Idea: Add hysteresis to the predictor so that prediction does not change on a single different outcome – Use two bits to track the history of predictions for a branch instead of a single bit – Can have 2 states for T or NT instead of 1 state for each • Smith, “A Study of Branch Prediction Strategies,” ISCA 1981. 19
Two-Bit Counter Based Prediction: Each branch associated with a two-bit counter: One more bit provides hysteresis: A strong prediction does not change with one singledifferent outcomeAccuracy for a loop with N iterations = (N-1)/NTNTNTNTNTNTNTNTNTNTN →50% accuraCy(assuming init to weakly taken)+ Better prediction accuracy2BC predictor CPl=[1 + (0.20*0.10) *2] =1.04 (90% accuracy)-- More hardware cost (but counter can be part of a BTB entry)ComputerArchitecture20
Computer Architecture Two-Bit Counter Based Prediction • Each branch associated with a two-bit counter • One more bit provides hysteresis • A strong prediction does not change with one single different outcome n Accuracy for a loop with N iterations = (N-1)/N TNTNTNTNTNTNTNTNTNTN à 50% accuracy (assuming init to weakly taken) + Better prediction accuracy - More hardware cost (but counter can be part of a BTB entry) 20 2BC predictor CPI = [ 1 + (0.20*0.10) * 2 ] = 1.04 (90% accuracy)