Now that we have four possible states for our two bit predictor there is
an interesting question of does it matter in which state we start the predictor
off. So with the one bit predictor we had to start it in either zero or
one state. If we start it in the not taken state, zero, that means that if
the branch is not taken it will start predicting correctly right off the bat.
Is we start predicting zero but the branches actually mostly taken we will have
a single mis-prediction before we start doing taken. For a two bit predictor,
however, the question is really should we start in one of the strong
conviction states or should we start in one of the weak prediction states.
If we start in a strong state, for example zero, zero, and
the actual decisions are not taken, then we will stay in that
same strong state and never have any missed predictions. However,
if we start in the strong state zero, zero, but the branch tends to be taken.
We will mispredict once, move to the zero one, the weak not taken state.
Missed predict again and then start predicting correctly. If we start in
a strong state and it's the correct strong state we have no missed predictions,
if it's the wrong strong state we have two missed predictions.
If however we start in a weak state such as zero one. And
we started in the correct weak state. We will just move to the strong state and
still have all correct predictions. So, in the case when we
guessed right what should be the dominant behavior in the starting state,
we have perfect prediction regardless of whether we start in the strong or
weak state. However, If we were wrong about where to start and
we start in, let's say, zero, one, but now the branch is mostly taken,
we will have one missed prediction here and now we will be moving to
the weak taken state and start having correct predictions from then on.
So if we start in a weak state, we don't lose anything if we were right. But
we gain one less misprediction, if we were wrong about what should be the bias.
So this argument means that probably, we should be starting in the weak state.
Pick one, doesn't really matter. However, there is a flip side to it.
Let's say that the branch is taken, not taken, taken, not taken. And
we start in the strong state. The branch is taken so we move to the weak state.
Then it's not taken so we move back to the strong state. And so on,
we missed predict here, but we correctly predicted here and here, so
half the time we have missed predictions. If we started in the one, one state,
we would have a similar behavior, we would mis-predict every other time, but
if we start in the wrong weak state and have the same behavior here.
If the branch is taken and we have a weak not taken. We mis-predict and
we move to the weak taken state. Now the branch is not taken so
we mis-predict again. And move back to the weak not taken state. Branch is
taken again and so we mis-predict again. And we keep mis-predicting like this.
So as far as worse case behavior on alternating branch decisions is concerned.
Starting in a weak state, around some more risk of having this worst case
behavior of always missed predicting. Fortunately, this is much more
common behavior than this. So probably it's a good idea to start in a weak
taken state because taken branches are slightly more common than not taken. But
in reality, as you can see, it doesn't really matter much because if
the branch is mostly taken, one missed prediction initially is
not really going to be very costly to us because from then on it's going to
behave the same way regardless of what we started off with. So in reality,
although it seems like it's a good idea to start in the weak taken state.
In practice the overall accuracy of the branch predictor is
effected very little by what exactly do we start of in. So we might a well just
start of in zero zero state because that the easiest state to initialize into.