Branch prediction
In computer architecture, a branch predictor is the part of a processor that determines whether a conditional branch (jump) in the instruction flow of a program is likely to be taken or not. This is called branch prediction.
Branch predictors are important in today's modern, superscalar processors for achieving high performance. They allow processors to fetch and execute instructions without waiting for a branch to be resolved.
Almost all pipelined processors do branch prediction of some form, because they must guess the address of the next instruction to fetch before the current instruction has been executed.
Many earlier microprogrammed CPUs did not do branch prediction because there was little or no performance requirements; for this reason there is no need for altering the flow of the instruction stream.
Branch Prediction Media
Figure 1: Example of 4-stage pipeline. The colored boxes represent instructions independent of each other.
Figure 2: State diagram of 2-bit saturating counter
Figure 3: Two-level adaptive branch predictor. Every entry in the pattern history table represents a 2-bit saturating counter of the type shown in figure 2.
Other websites
- Seznec et al. (1996). "Multiple-Block Ahead Branch Predictors Archived 2008-07-20 at the Wayback Machine" – demonstrates prediction accuracy is not impaired by indexing with previous branch address.
- Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor Archived 2008-07-20 at the Wayback Machine" – describes the Alpha EV8 branch predictor. This paper does an excellent job discussing how they arrived at their design from various hardware constraints and simulation studies.
- Jimenez (2003). "Reconsidering Complex Branch Predictors Archived 2007-12-27 at the Wayback Machine" – describes the EV6 and K8 branch predictors, and pipelining considerations.
- Agner Fog. Branch Prediction in the Pentium Family
- Jeff Andrews (2007-10-30). "Branch and Loop Reorganization to Prevent Mispredicts". Intel Software Network. Archived from the original on 2008-04-17. Retrieved 2008-08-20.
