Editing Branch predictor (section)

===One-level branch prediction===
====Saturating counter====
A 1-bit saturating counter (essentially a [[flip-flop (electronics)|flip-flop]]) records the last outcome of the branch. This is the most simple version of dynamic branch predictor possible, although it is not very accurate.

A 2-bit [[saturation arithmetic|saturating counter]]<ref name="dbp-class-report" /> is a [[state machine]] with four states:
[[File:Branch prediction 2bit saturating counter-dia.svg|600px|thumb|right|Figure 2: State diagram of 2-bit saturating counter]]
<!-- 2-bit saturating counter is different from bimodal predictor -->
* Strongly not taken
* Weakly not taken
* Weakly taken
* Strongly taken

When a branch is evaluated, the corresponding state machine is updated. Branches evaluated as not taken change the state toward strongly not taken, and branches evaluated as taken change the state toward strongly taken. The advantage of the two-bit counter scheme over a one-bit scheme is that a conditional jump has to deviate twice from what it has done most in the past before the prediction changes. For example, a loop-closing conditional jump is mispredicted once rather than twice.

The original, non-MMX [[Original Intel Pentium (P5 microarchitecture)|Intel Pentium]] processor uses a saturating counter, though with an imperfect implementation.<ref name="Fog_Microarchitecture"/>

On the [[Standard Performance Evaluation Corporation|SPEC]]'89 benchmarks, very large bimodal predictors saturate at 93.5% correct, once every branch maps to a unique counter.<ref name="decwrl-tn-36">{{cite web |author-first=Scott |author-last=McFarling |title=Combining Branch Predictors |id=Digital Western Research Lab (WRL) Technical Report, TN-36 |date=June 1993 |url=https://hplabs.itcs.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf}}</ref>{{rp|3}}

The predictor table is indexed with the instruction [[memory address|address]] bits, so that the processor can fetch a prediction for every instruction before the instruction is decoded.