So after the initial warm-up period, we have seen,
that the 2-bit history predictor will start predicting this,
with 100% accuracy. We also see, that this predictor is really wasting
one of its four 2-bit counters because, it's only using three of the four,
to predict this pattern. And the fourth one simply never gets used. So
we have it in the entry, but we really didn't need it.
Now let's see what happens if this same 2-bit history predictor is trying to
predict, the alternating pattern, the not taken taken, not taken taken, and so
on. For that pattern, when we are trying to predict this non-taken here,
we're seeing a history of 01. That means the counter 1, will be counting down.
When we are trying to predict this, we have a history of 10, and
when we have 10, that means counter 2. Is counting up. For this,
we again have a history of 01. So, counter 1 counts down. And
when we try to predict this, we have 10, in history. So counter 2,
is counting up. As you can see, for this pattern, counter 1 and
counter 2 will very soon start predicting correctly. And there are really,
only two of these counters used. One because the history can be 01, and
one because the history can be 10. We never can see the history of 00,
or 11, which means, after the initial warm-up period, this predictor will also
predict this with 100% accuracy. We have already seen that the 1-bit
history predictor can predict this with a 100% accuracy, which is good.
But, this predictor is not using half of its 2-bit predictor entries. So
basically, in the entry that corresponds to this branch, we are really
using only two of the four 2-bit counters, so the waste is larger. In general,
an N-bit history predictor, will correctly predict all patterns of length.
Less than, or equal to, N plus 1. We have seen that a single bit predictor,
can predict correctly the pattern that is of line two. A 2-bit predictor
can predict correctly a pattern of length three and also of length two.
Both of them, of course, can predict a pattern of length one, which amounts to
always taken, or always not taken. In general, an N-bit history predictor,
will predict all patterns of length, its history size, plus one, or
less than that. However, the N-bit history predictor, will cost us,
the N-bit of history plus, 2 to the Nth, 2-bit counters. Per entry.
Each branch will have an entry that we index into that will be of this size.
So the entries become very large. For example,
if it's a 10-bit history we're talking about several kilobits worth of stuff,
for a single branch to be predicted. If we have, for example,
a loop that has something like a. Loop out branch and a loop back branch.
That will spend two of these entries. And, how about the waste? Most of
the 2-bit counters that we have in our entry will be wasted. Why? Well because,
if we have for example,. A 10-bit history, there are 1,024 entries.
We can only predict patterns that are up to 11th in length, and
a pattern of length 11, will have 11 possible histories at most. So
of the more than a thousand histories, we will really be using. Only up to 11 of
them, for accurate prediction. The rest of the histories are mainly, waste. So
as as we can see, by increasing the N here which is the length of the history,
we're improving, our ability to predict longer and
longer patterns. But, our predictor becomes very expensive,
very quickly and much of the cost that we are adding is waste. So
the question is, why would we want to have N large? Why not just settle for
something like, patterns of length three? Well it turns out,
that a very common type of a pattern, is a loop, where we have something like,
this would be. Don't exit the loop, don't exit the loop, exit the loop.
So it's a tri-iteration loop, and then we repeat that loop many times. So for
example, in order to do something like a eight iteration loop,
we have to have a pattern, of eight or nine length. Which means we need,
an 7 or 8-bit history in order to predict that successfully. So
we do want to have a long history, but we'd rather have it,
without this huge cost and without the huge waste that the cost comes with.