DOC PREVIEW
UNC-Chapel Hill COMP 206 - LECTURE NOTES

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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)2ReadingReadingHP3, 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 schedulingschedulingcontrol dependences now become the bottleneckcontrol dependences now become the bottleneckSince 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 pipelineWhat we must predictWhat we must predictBranch 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 = 0minimum branch penalty = minimum branch penalty = j*Tj*TLet Let ss be the pipeline stage where BTA becomes be the pipeline stage where BTA becomes knownknownThen Then j = s-1j = s-1SeeSee static prediction methods in Lecture 7static prediction methods in Lecture 7Thus, performance of any branch prediction Thus, performance of any branch prediction strategy is limited bystrategy is limited bys,s, the location of the pipeline stage that develops BTA the location of the pipeline stage that develops BTAA,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 TAKENPredict all branches as TAKENPredict all branches as TAKENPredict 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 TAKENPredict all forward branches as NOT TAKEN, and all Predict all forward branches as NOT TAKEN, and all backward branches as TAKENbackward branches as TAKENOpcodes 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 decidedDynamic 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 instrsuch 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 MPredictor misses twice on typical loop branchesPredictor misses twice on typical loop branchesOnce at the end of loopOnce at the end of loopOnce at the end of the 1Once at the end of the 1stst iteration of next execution of loop iteration of next execution of loopThe 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 0A four-state Moore machineA four-state Moore machinePredictor misses once on typical loop branchesPredictor misses once on typical loop brancheshence popularhence popularOutcome 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

UNC-Chapel Hill COMP 206 - LECTURE NOTES

Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?