COMP 206: Computer Architecture and ImplementationReadingWhy Do We Need Branch Prediction?A General Model of Branch PredictionTheoretical Limits of Branch PredictionReview: Static Branch Prediction MethodsDynamic Branch PredictionBHT Methods for Branch PredictionA One-Bit PredictorA Two-Bit PredictorSlide 11Correlating Branch Outcome PredictorsAnother Example of Branch CorrelationA Correlating Branch PredictorOrganization of (m,n) Correlating PredictorImproved Dynamic Branch PredictionUsing BTB and BHT TogetherParameters of Real MachinesCoupled BTB and BHTDecoupled BTB and BHTReducing Misprediction PenaltiesPredicting Dynamic BTAs1COMP 206:COMP 206:Computer Architecture and Computer Architecture and ImplementationImplementationMontek SinghMontek SinghWed, Oct 12, 2005Wed, Oct 12, 2005Topic: Topic: Instruction-Level ParallelismInstruction-Level Parallelism(Dynamic Branch Prediction)(Dynamic Branch Prediction)2ReadingReadingHP3, Section 3.4-3.5HP3, Section 3.4-3.53Why Do We Need Branch Why Do We Need Branch Prediction?Prediction?Basic blocks are short, and we have done Basic blocks are short, and we have done about all we can do for them with dynamic about all we can do for them with dynamic schedulingschedulingcontrol dependences now become the bottleneckcontrol dependences now become the bottleneckSince branches disrupt sequential flow of Since branches disrupt sequential flow of instrs…instrs…we need to be able to predict branch behavior to we need to be able to predict branch behavior to avoid stalling the pipelineavoid stalling the pipelineWhat we must predictWhat we must predictBranch outcome (Is the branch taken?)Branch outcome (Is the branch taken?)Branch Target Address (What is the next non-Branch Target Address (What is the next non-sequential PC value?)sequential PC value?)4A General Model of Branch A General Model of Branch PredictionPredictionAPPTPPTPPpPPPPpPPPPntntttntntntttntttntnttntntnttntnttttntttt//////////////11TakenNot Predict TakenPredict TakenNot TakennmkjTakenNot Predict TakenPredict TakenNot Taken• T: probability of branch being taken• p: fraction of branches that are predicted to be taken• A: accuracy of prediction• j, k, m, n: associated delays (penalties) for the four events (n is usually 0)ntnttntnttttPnPmPkPj////Branch penalty of a particular prediction methodBranch predictor accuracyBranch penalties5Theoretical Limits of Branch Theoretical Limits of Branch PredictionPredictionBest case: Best case: branches are perfectly predicted branches are perfectly predicted (A = (A = 1)1)also assume that also assume that n = 0n = 0minimum branch penalty = minimum branch penalty = j*Tj*TLet Let ss be the pipeline stage where BTA becomes be the pipeline stage where BTA becomes knownknownThen Then j = s-1j = s-1SeeSee static prediction methods in Lecture 7static prediction methods in Lecture 7Thus, performance of any branch prediction Thus, performance of any branch prediction strategy is limited bystrategy is limited bys,s, the location of the pipeline stage that develops BTA the location of the pipeline stage that develops BTAA,A, the accuracy of the prediction the accuracy of the prediction6Review: Static Branch Prediction Review: Static Branch Prediction MethodsMethodsSeveral Several staticstatic prediction strategies: prediction strategies:Predict all branches as NOT TAKENPredict all branches as NOT TAKENPredict all branches as TAKENPredict all branches as TAKENPredict all branches with certain opcodes as TAKEN, Predict all branches with certain opcodes as TAKEN, and all others as NOT TAKENand all others as NOT TAKENPredict all forward branches as NOT TAKEN, and all Predict all forward branches as NOT TAKEN, and all backward branches as TAKENbackward branches as TAKENOpcodes have default predictions, which the compiler Opcodes have default predictions, which the compiler may reverse by setting a bit in the instructionmay reverse by setting a bit in the instructionReview material in Lecture 87Dynamic Branch PredictionDynamic Branch PredictionPremise: Premise: HistoryHistory of a branch instr’s outcome of a branch instr’s outcome matters!matters!whether a branch will be taken depends greatly on the whether a branch will be taken depends greatly on the way previous dynamic instances of the same branch way previous dynamic instances of the same branch were decidedwere decidedDynamic prediction methods:Dynamic prediction methods:take advantage of this fact by making their take advantage of this fact by making their predictions dependent on the past behavior of the predictions dependent on the past behavior of the same branch instrsame branch instrsuch methods are called Branch History Table (BHT) such methods are called Branch History Table (BHT) methodsmethods8BHT Methods for Branch BHT Methods for Branch PredictionPrediction9NTA One-Bit PredictorA One-Bit Predictor Branch outcomePrediction State Taken Not TakenTaken 1 1 0Not Taken 0 1 0Actual T T T NT T T T T NT T NT T NT TState 1 1 1 1 0 1 1 1 1 0 1 0 1 0 1Predicts T T T T NT T T T T NT T NT T NTHit/Miss H H H M M H H H M M M M M MPredictor misses twice on typical loop branchesPredictor misses twice on typical loop branchesOnce at the end of loopOnce at the end of loopOnce at the end of the 1Once at the end of the 1stst iteration of next execution of loop iteration of next execution of loopThe outcome sequence NT-T-NT-T makes it miss all the timeThe outcome sequence NT-T-NT-T makes it miss all the timeState 0Predict Not TakenState 1Predict TakenTTNT10A Two-Bit PredictorA Two-Bit PredictorBranch outcomePrediction State Taken Not TakenTaken 3 3 2Taken 2 3 0Not Taken 0 1 0Not Taken 1 3 0A four-state Moore machineA four-state Moore machinePredictor misses once on typical loop branchesPredictor misses once on typical loop brancheshence popularhence popularOutcome sequence NT-NT-T-T-NT-NT-T-T make it Outcome sequence NT-NT-T-T-NT-NT-T-T make it miss all the timemiss all the timeNTState 2PredictTakenState 3Predict TakenTTNTState 0Predict Not TakenState 1Predict Not TakenTNTNTT11A Two-Bit PredictorA Two-Bit PredictorBranch outcomePrediction State Taken Not TakenTaken 3 3 2Taken 2 3 0Not Taken 0 1 0Not Taken 1 3 0Actual T T T NT T T T T NT NT T T NT NTState 3 3 3 3 2 3 3 3 3 2 0 1 3 2 0Predicts T T T T T T T T T
View Full Document