One-bit vs. two-bit predictors
A one-bit predictor correctly predicts a branch at the end of a loop iteration, as long as the loop does not exit.
In nested loops, a one-bit prediction scheme will cause two mispredictions for the inner loop:
- One at the end of the loop, when the iteration exits the loop instead of looping again, and
- one when executing the first loop iteration, when it predicts exit instead of looping.
Such a double misprediction in nested loops is avoided by a two-bit predictor scheme.
Two-bit Prediction: A prediction must miss twice before it is changed when a two-bit prediction scheme is applied.