n-Bit Branch Predictor

computer-architecture

Definition

$n$-Bit Branch Predictor

An $n$-bit branch predictor is a dynamic branch prediction scheme that uses an $n$-bit saturating counter to predict the direction of a branch.

The counter implements a finite-state machine with $2^n$ states. A taken outcome increments the counter (up to the maximum), and a not taken outcome decrements it (down to the minimum). The branch is predicted taken when the counter is in the upper half of its range and not taken otherwise.

Because the counter saturates, a single anomalous outcome cannot immediately flip a prediction that has been consistently reinforced. This hysteresis is what distinguishes an $n$-bit predictor ($n>1$) from a simple last-outcome predictor.

Hysteresis

In a $n$-bit branch predictor, hysteresis means that one anomalous not taken outcome does not change a strongly taken prediction to not taken — it only weakens it to weakly taken.

Schemes

1-Bit

Definition

1-Bit Branch Predictor

A 1-bit branch predictor is an n-bit branch predictor with $n=1$, giving exactly two states: predict not taken and predict taken.

The prediction is simply the last outcome of that branch. If the branch was taken last time, it is predicted taken; if it was not taken, it is predicted not taken.

Because there is no hysteresis, the prediction flips after every misprediction. In a loop that is taken $k$ times and then falls through once, a 1-bit predictor mispredicts twice per loop iteration — once on the exit and once on the first iteration of the next entry.

Link to original

2-Bit

Definition

2-Bit Branch Predictor

A 2-bit branch predictor is an [[Knowledge/n-Bit Branch Predictor|$n$-bit branch predictor]] with $n=2$, giving four states: strongly not taken (00), weakly not taken (01), weakly taken (10), and strongly taken (11).

The prediction is not taken in states 00 and 01, and taken in states 10 and 11. Because the counter saturates, a single anomalous outcome cannot reverse a strong prediction — it only weakens it. Two consecutive opposite outcomes are needed to flip the prediction direction.

This is the most common practical predictor width. The 2-bit saturating counter fixes the oversensitivity of the 1-bit predictor while remaining cheap to implement.

Link to original