Branch Prediction
Lucas McDaniel
What is a branch?
A branch is a point in a program where the flow of control can change.
Where are these found?
In assembly, this occurs with “jmp”, “je”, “jg”, “call”, “ret”, etc.
Why are these problematic?
Branches disrupt the instruction pipeline. Most modern day CPUs have some form of pipeline which is implemented to allow multiple independent instructions to be executed nearly concurrently. Since a CPU cannot know where the flow of control will go until after the branching statement has been evaluated, the pipeline is disrupted.
Methods to account for branching
Do Nothing
Description: Wait for the branching statement to finish being evaluated.
Pros: Easy to implement.
Cons: Inefficient use of time.
Always Predict 'T/F'
Description: Always choose true of false for a specific branch and if the incorrect assumption was attempted, then scrap all changes.
Pros: Easy to implement and more efficient on average than the “Do Nothing” method
Cons: Guesses cannot be updated based off of the state of the program.
Dual Bit Predictor
Description: Contains 4 states: Strongly taken, weakly taken, weakly not taken, strongly not taken. As a branch is taken, it moves up the chain towards 'strongly taken' and when a branch isn't taken it moves closer to 'strongly not taken'.
Pros: Able to quickly change to an accurate prediction when given a series of branching statements which evaluate the same.
Cons: Cannot handle evaluations rapidly changing.
Modifications
Local Prediction
Description: A modification in which each branching statement keeps a history of if it was taken or not taken.
Pros: Able to recognize when the same statement branches in a similar fashion repeatedly.
Cons: Not able to quickly recognize when neighboring branching statements influence the local statement.
Global Prediction
Description: A modification in which each branching statement updates the same global history.
Pros: Able to quickly recognize when neighboring branching statements affect each other.
Cons: Not able to quickly recognize when a single branch is taken or not taken frequently.
Loop Prediction
Description: For a loop with N repetitions, the branch will be taken N-1 times, and not be taken on the last occurrence.
Pros: Prediction correctly for loops.
Cons: Not always easy to detect a loop and to determine the number of iterations it must undergo.
Commercial Methods
Branch Target Buffer (BTB)
Description: The most recent indirect branches are saved in a look-up table for analysis. An indirect branch is a branching statements where the designated address to jump to is computed and referenced via a register.
Pros: Quickly able to recall previous jumps and can load this information in advanced.
Cons: Assumes the next jump will be similar to a previous jump.
Two – Level Adaptive Predictor
Description: The last n occurrences of the branches are saved and a series of 2n “Dual Bit Predictors” are used, one for each possible pattern of n.
Pros: Able to detect simple patterns in the branches very quickly and accurately.
Cons: More processes and memory intensive.