Design of Microprocessor Branch Prediction Algorithms

MICROPROCESSOR BRANCH PREDICTION ALGORITHMS

Branch Prediction:

- A technique used in CPU design that attempts to guess the outcomes of a conditional operation and prepare for the most likely result

- The digital circuit which performs this operation is known as branch predictor

- It is an important component of modern CPU design.

- Improve the flow in the instruction pipeline

- Resolve a branch hazard by predicting which path will be taken

- Proceed under that assumption

- If the prediction is correct, avoid delay of the branch hazard

- If the prediction is incorrect, flush the wrong-path instructions from the pipeline & fetch the right path

Performance Improvement Depends On:

- Whether the prediction is correct (producing correct predictions is most of the innovation)

- How soon you can check the prediction

Dynamic Branch Prediction:

- The prediction determined at runtime & changes as program behavior changes

- Branch prediction mechanism implemented in hardware

- Common algorithm based on branch history

- Predict the branch taken if branched the last time

- Predict the branch not-taken if didn’t branch the last time

Alternative: Static Branch Prediction

- Compiler-determined prediction

- Fixed for the life of the program

Pipeline Without Branch Prediction:







In 5-stage pipeline, a branch completes in two cycles -> If the branch went the wrong way, one incorrect instruction is fetched -> One stall cycle per incorrect branch

1-Bit Bimodal Prediction:

- For each branch, keep track of what happened last time and use that outcome as prediction

- What are prediction accuracies for branch1 and branch 2 below:

- While(1)

{

For (i=0;i<10;i++) Branch-1

{}

For (j=0;j<20;j++) Branch-2

{}

}

Note: The prediction fails on start and end of for() loop every time.

2-Bit Bimodal Predictor:

- A single prediction bit does not work well with loops

- Misspredicts the first & last iterations of a nested loop

- Two-bit branch prediction for loops

- Algorithm: have to be wrong twice in a row before prediction is changed

- Uses 2-bit saturating counter



- The table keeps track of the common-case outcome for the branch






Works well when branches predominantly go in the same direction

- A second check is made to make sure that a short & temporary change of direction does not change the prediction away from the dominant direction

Correlating Predictors:

- Basic Branch Prediction: Maintain a 2- Bit saturating counter for each entry (or use 10 branch PC bits to index into one of 1024 counters) -capture the recent “Common Case” for each branch.

- Can we take advantages of additional information?

Ø If a branch recently went ‘01111’, expect ‘0’, If it went ‘11101’, expect ‘1’. Can we have a separate counter for each case?

Ø If the previous branches went ‘01’, expect ‘0’, if the previous branches went ‘11’, expect ‘1’. Can we have a separate counter for each case?

Hence, build Correlating Predictors!!!

Global/Local Predictors:

- Instead of maintaining a counter for each branch to capture the common case,

Ø Maintain a counter for each branch and surrounding pattern

Ø If the surrounding pattern belongs to the branch being predicted, the predictor is referred to as Local Predictor

Ø If the surrounding pattern includes neighboring branches, the predictor is referred to as a Global Predictor.

Global Predictor:

- Keeps track of all the branches happened in recent.









- The table keeps track of the common-case outcome for the branch/history combo

Local Predictor:

- Keeps track of same branch







Branch Aliasing: There may be a case when a same entry in BTB (Branch Target Buffer) can map to more than one Branch address (Because we are using only a part of PC address for indexing BTB)

Solution:





- The table keeps track of the common-case outcome for the branch/local history combo

Tournament Predictors:

- A local predictor might work well for some branches or programs, while a global predictor work well for others

- Provide one of each and maintain another predictor to identify which predictor is best for each branch


Branch Target Prediction:

- In addition to predicting the branch direction, we must also predict the branch target address

- Brach PC indexes into a predictor table, indirect branches might be problematic

- Most common indirect branch – return from a procedure – can be easily handles with a stack of return address




-------------------------------------------Happy Learning -----------------------------------------