Analysis of Branch Prediction Strategies in Computer Architecture

This report provides an overview of branch prediction techniques in computer architecture, focusing on how these techniques improve the flow of instructions in a pipeline. It explains that branch prediction is crucial for high performance in modern microprocessors, particularly in handling conditional jump instructions. The report details the challenges of two-way branching and the delays caused by mispredictions, emphasizing the role of branch predictors in speculatively executing instructions. It also discusses how branch predictors learn from past behavior to make informed predictions, reducing the need for processors to stall while waiting for the outcome of conditional jumps. The time wasted due to branch misprediction is also discussed in detail.

In computer architecture, a branch predictor is a digital circuit that tries to
guess which way a branch (e.g. an if-then-else structure) will go before this is known
for sure. The purpose of the branch predictor is to improve the flow in the instruction
pipeline. Branch predictors play a critical role in achieving high
effective performance in many modernpipelined microprocessor architectures such
as x86.
Figure 1: Example of 4-stage pipeline. The colored boxes represent instructions
independent of each other
Two-way branching is usually implemented with a conditional
jump instruction. A conditional jump can either be "not taken" and continue
execution with the first branch of code which follows immediately after the
conditional jump, or it can be "taken" and jump to a different place in program
memory where the second branch of code is stored. It is not known for certain
whether a conditional jump will be taken or not taken until the condition has been
calculated and the conditional jump has passed the execution stage in the instruction
pipeline (see fig. 1).
Without branch prediction, the processor would have to wait until the
conditional jump instruction has passed the execute stage before the next instruction
can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this
waste of time by trying to guess whether the conditional jump is most likely to be
taken or not taken. The branch that is guessed to be the most likely is then fetched
and speculatively executed. If it is later detected that the guess was wrong then the
speculatively executed or partially executed instructions are discarded and the
pipeline starts over with the correct branch, incurring a delay.

The time that is wasted in case of a branch misprediction is equal to the
number of stages in the pipeline from the fetch stage to the execute stage. Modern
microprocessors tend to have quite long pipelines so that the misprediction delay is
between 10 and 20 clock cycles. As a result, making a pipeline longer increases the
need for a more advanced branch predictor.
The first time a conditional jump instruction is encountered, there is not much
information to base a prediction on. But the branch predictor keeps records of
whether branches are taken or not taken. When it encounters a conditional jump that
has been seen several times before then it can base the prediction on the history. The
branch predictor may, for example, recognize that the conditional jump is taken more
often than not, or that it is taken every second time.