Branch predictor

Not to be confused with Predication (computer architecture).

In computer architecture, a branch predictor[1][2][3][4][5] 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 definitively. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high performance in many modern pipelined microprocessor architectures.

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 "taken" and jump to a different place in program memory, or it can be "not taken" and continue execution immediately after the conditional jump. 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.[6]

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.

Branch prediction is not the same as branch target prediction. Branch prediction attempts to guess whether a conditional jump will be taken or not. Branch target prediction attempts to guess the target of a taken conditional or unconditional jump before it is computed by decoding and executing the instruction itself. Branch prediction and branch target prediction are often combined into the same circuitry.

  1. ^ Malishevsky, Alexey; Beck, Douglas; Schmid, Andreas; Landry, Eric. "Dynamic Branch Prediction". Archived from the original on 2019-07-17. Retrieved 2017-03-22.
  2. ^ Cheng, Chih-Cheng. "The Schemes and Performances of Dynamic Branch predictors" (PDF).
  3. ^ Parihar, Raj. "Branch Prediction Techniques and Optimizations" (PDF). Archived from the original (PDF) on 2017-05-16. Retrieved 2017-04-02.
  4. ^ Mutlu, Onur (2013-02-11). "18-447 Computer Architecture Lecture 11: Branch Prediction" (PDF). Archived from the original (PDF) on 2015-03-25.
  5. ^ Michaud, Pierre; Seznec, André; Uhlig, Richard (September 1996). Skewed branch predictors. HAL (report). S2CID 3712157.
  6. ^ Eyerman, S.; Smith, J.E.; Eeckhout, L. (2006). Characterizing the branch misprediction penalty. 2006 IEEE International Symposium on Performance Analysis of Systems and Software. IEEE. pp. 48–58. doi:10.1109/ispass.2006.1620789. ISBN 1-4244-0186-0. S2CID 72217.