The predictor that fixes the two mis-predictions per anomaly behavior of the one
bit predictor is called a two bit predictor. Often we write that as
2BP,or even a 2BC which stands for
a 2-bit counter. We will see that this predictor behaves like a 2-bit counter.
The 2-bit predictor has possible values zero, zero, zero, one, one, zero, and
one, one. The way it works, is that the more
significant bit of the predictor tells us what the prediction should be.
So this is what we will call the prediction bit, the more significant bit of
this predictor. This prediction bit really functions similarly to.
How the 1-bit predictor functions. This lower bit, here,
is called the Histeresis or Conviction Bit. This tells us
how sure are we that we should be predicting what the prediction bit is saying.
Usually, the state zero, zero is treated as a strong not-taken state.
This means that we will be predicting not taken. And
we are fairly convinced that not taken is the dominant behavior of this branch.
The zero one state will be the weak not taken prediction state.
Were still going to predict not taken but
this time we are less sure that that's the dominant behavior. Similarly here for
the, predict taken, states we have, Weak Taken, and the Strong Taken state.
So how does this predictor work? The 1-bit predictor only had the, not-taken and
the taken state. If, our state is zero, we will predict not-taken.
If we indeed see the not-taken decision later, we stay in this state.
Next time we'll predict not-taken too. If however, we're predicting not-taken,
but this decision turns out to be taken, we change our mind and
move to the taken state. In the taken state, we stay there if the branches
in it taken, but if we predict taken and see that the branch is not-taken,
we go back to the not-taken state and state predicting that. So pretty much,
one outcome changes our mind completely about what to do with a branch.
And that has resulted in two mis-predictions per anomaly.
let's say that the dominant behavior is not-taken, the first time the branch
is seen to be taken we move here and then the branch moves back to the dominant
behavior we will predict taken and mis-predict again before we move here.
With 2-bit predictor we have four states. Zero zero, zero one,
one zero, and one one. Now this is our strong not-taken state. And
of course if we see a not-taken decision we stay there. We were convinced
that the branch will be not taken and the outcome really confirms that.
If we see a single taken decision from the strong not taken state we move to
the weak not taken. So now we're predicting that the branch is still not-taken,
but we are less convinced about that. In the case when the not-taken behavior is
the dominant one this would be the anomaly and we would move back to the strong
not-taken state. Once we see that the branch is not-taken, so the idea is that,
unlike here, where the anomaly itself will result in a mis-prediction, and
then we will predict differently so
that the dominant behavior again will be mis-predicted for once.
Here, this taken while in the strong not-taken state will be a mis-prediction.
But then, we will predict not-taken. It's just a weak prediction. So we will be
right for this not-taken outcome. So if the branch really is mostly not-taken,
we only have a mis-prediction. When the anomaly happens, not also,
not when the dominant behavior happens after the anomaly. Similarly,
if we are in the strong taken state, we believe now that the taken behavior
is the dominant one. A single not taken will result in a mis-prediction, but
move us to a weak taken state. So that if we see a taken outcome again,
we don't mis-predict and we move back to the strong taken state.
Of course we stay in the strong taken state as long as we are seeing the taken
outcome. So the idea is that if not-taken is a dominant behavior, we expect
the predictor to stay in these two states. If taken is the dominant behavior, we
expect the predictor to stay in these two states. Either way, it's predicting so
that only the anomaly gets mis-predicted, but not the dominant behavior that
follows the anomaly. However, we can have a branch that, for example,
tends to be not-taken for a while, and then changes its mind about it and
starts being taken for a while. Thus, if we are in the weak taken state, and
we see another taken outcome, we will go to one of the taken states,
and similarly, if we are in a weak taken state, and we see another not-taken,
we will move to one of the not taken states. So, the idea is,
if we see a branch that is mostly not taken. Periodically it's maybe taken and
then again stays not taken. We stay in these two states and keep predicting not
taken. But if the branch starts being taken very often from now on,
it will take one, two mis-predictions before we are in the taken states and
start predicting taken again. So somehow, a single anomaly will cost us one
mis-prediction. A switch in behavior will cost us two mis-predictions. So
why we call this a 2-bit counter is because if you look at what this is doing,
is, it's a counter that counts up. When the branch is taken, and
saturates at three. And counts down when it's not-taken, and
saturates at zero. So really it's a 2-bit counter that just
counts up when the branch is taken, and counts down as the branch is not-taken.
This also means that this is a relatively easy behavior to implement.
Basically it's very easy to implement this type of predictor