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.


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.