So we have seen in the latest quiz, that the
one bit predictor works reasonably well for rules that have
a lot of iterations. So what are the problems with
one bit prediction that have related to better predictors. The
one bit predictor predicts well,branches that are always taken it
might make a mistake that first time it's used the
branch, but after that it's going to start predicting taken
and because of branches always take it always works well.
Similarly always not taken is predict as well because
the very first time it might mispredict, but after that
it learns the behavior and it stays the same so
we just have the always not taken. It also predicts
well,the branches where the number of taken outcomes is
vastly more than the number of not taken outcomes. Here
it's going to learn after the first taken outcome that the
next outcome should be predicted taken, and very, very rarely
it's going to be wrong because of a not taken
outcome. Similarly, the one way predictor predicts well when the
number of not taken outcomes is vastly more than the
number of taken outcomes for the same reason. Basically we
will see not taken, not taken, not taken many, many
times. The first time we see one of those we're
going to learn it. And then the taken outcome will be
mispredicted. So what's wrong with the one, one bit predictor.
What's wrong with it, can be glimpsed from these.
Let's look at the branch that is for example,
more taken than not. So it's been taken many
times. And then there is a not taken outcome and
then it's going to be taken many more times.
Let's now look at whether the one we predicted would
be right on these. It's been taken many times,
so it's going to predict taken, and then because it's
been taken it's going to predict the next one as
taken. The next one is going to be predicted taken,
taken again. When we reach the not taken outcome, the
last outcome was taken, so we will have a misprediction.
This would not be much of a problem if not
taken occurs very rarely, because we are basically mispredicting just
the very rare occurrences. However, there is an interesting problem
here, which is now that we are back to our
taken behavior, which is the vastly dominant behavior
in this case,. The last outcome was not not
taken. So we're going to mispredict this branch too.
Now, we're predicting not taken and the branch will
be taken. After this, the previous outcome was taken
so we predict taken. And we continue predicting taken.
So the problem really is. That each anomaly, such
as we have a branch that is almost always
taken but sometimes it's not taken, results in two
mispredictions. One for the anomalous behavior and then once
more for the normal behavior that follows the anomaly.
So the one bit predictor will not do so
well, when the branch is biased towards, let's say,
doing more taken branches but the number of not
taken branches is still significant, or when there is
more not taken branches. But the number of taken
branches is significant. Because for each of the less
dominant behavior is going to do mispredictions not just
one. Typically also a branch predictor like this will
not do well on short loops. Why? Because in a
short loop we have a branch,that for example, exits
the loop. Then we have some loop behavior and then
a branch that loops back. The branch that exits
the loop. Will be predicted correctly as long as we
stay in the loop by this predictor. The exit from
the loop will be mispredicted. The branch vector will now
be trained to take this path here. When we come
back to this short loop. It's going to mispredict the very
first iteration for this branch. Because now it's going to think
it should be this way. But, in fact, now we're
staying in the loop. So have, for example, an eight
iteration loop. We will have two mispredictions every 80 duration's.
One at the end of the loop and one
at the beginning of the loop because the previous
ending of the loop trained the predictor that way.
And then of course the one with predictor will be
pretty bad. When the number of taken and not taken outcomes is similar, yet
predictable. We will talk about this more later. But now, let's
first devise a predictor that will fix this. So, can we devise
a predictor that behaves similarly well here, but
does not mispredict twice whenever there is an anomaly.