Editing Branch predictor (section)

===Two-level predictor===
The Two-Level Branch Predictor, also referred to as Correlation-Based Branch Predictor, uses a two-dimensional table of counters, also called "Pattern History Table". The table entries are two-bit counters.

====Two-level adaptive predictor====
[[File:Two-level branch prediction.svg|420px|thumb|right|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.<ref>{{cite journal |title=New Algorithm Improves Branch Prediction: 3/27/95|url=https://www.cs.cmu.edu/afs/cs/academic/class/15213-f00/docs/mpr-branchpredict.pdf |journal=[[Microprocessor Report]] |volume=9 |issue=4 |date=March 27, 1995 |access-date=2016-02-02 |archive-url=https://web.archive.org/web/20150310190847/https://www.cs.cmu.edu/afs/cs/academic/class/15213-f00/docs/mpr-branchpredict.pdf |archive-date=2015-03-10 |url-status=live}}</ref>]]

If an <code>if</code> statement is executed three times, the decision made on the third execution might depend upon whether the previous two were taken or not. In such scenarios, a two-level adaptive predictor works more efficiently than a saturation counter. Conditional jumps that are taken every second time or have some other regularly recurring pattern are not predicted well by the saturating counter. A two-level adaptive predictor remembers the history of the last n occurrences of the branch and uses one saturating counter for each of the possible 2<sup>n</sup> history patterns. This method is illustrated in figure 3.

Consider the example of n&nbsp;= 2. This means that the last two occurrences of the branch are stored in a two-bit [[shift register]]. This branch history register can have four different [[binary numeral system|binary]] values, 00, 01, 10, and 11, where zero means "not taken" and one means "taken". A pattern history table contains four entries per branch, one for each of the 2<sup>2</sup>&nbsp;= 4 possible branch histories, and each entry in the table contains a two-bit saturating counter of the same type as in figure 2 for each branch. The branch history register is used for choosing which of the four saturating counters to use. If the history is 00, then the first counter is used; if the history is 11, then the last of the four counters is used.

Assume, for example, that a conditional jump is taken every third time. The branch sequence is 001001001... In this case, entry number 00 in the pattern history table will go to state "strongly taken", indicating that after two zeroes comes a one. Entry number 01 will go to state "strongly not taken", indicating that after 01 comes a zero. The same is the case with entry number 10, while entry number 11 is never used because there are never two consecutive ones.

The general rule for a two-level adaptive predictor with an n-bit history is that it can predict any repetitive sequence with any period if all n-bit [[subsequence|sub-sequences]] are different.<ref name="Fog_Microarchitecture"/>

The advantage of the two-level adaptive predictor is that it can quickly learn to predict an arbitrary repetitive pattern. This method was invented by T.-Y. Yeh and [[Yale Patt]] at the [[University of Michigan]].<ref>{{cite conference |author-first1=T.-Y. |author-last1=Yeh |author-last2=Patt |author-first2=Y. N. |author-link2=Yale Patt |title=Two-Level Adaptive Training Branch Prediction |book-title=Proceedings of the 24th annual international symposium on Microarchitecture |pages=51–61 |publisher=ACM |date=1991 |location=Albuquerque, New Mexico, Puerto Rico |doi=10.1145/123465.123475|doi-access=free }}</ref> Since the initial publication in 1991, this method has become very popular. Variants of this prediction method are used in most modern microprocessors.{{citation needed|date=September 2015}}

====Two-level neural predictor====
A two-level branch predictor where the second level is replaced with a [[neural network]] has been proposed.<ref>{{cite journal|url=https://www.researchgate.net/publication/264708564|title=Two-Level Branch Prediction using Neural Networks|last1=Egan|first1=Colin|last2=Steven|first2=Gordon|last3=Quick|first3=P.|last4=Anguera|first4=R.|last5=Vintan|first5=Lucian|date=December 2003|journal=Journal of Systems Architecture|volume=49|issue=12–15|pages=557–570|doi=10.1016/S1383-7621(03)00095-X}}</ref>