So let's look at the example history based projector that
has a 1-bit history with 2-bit counters, for each history. So
the general approach to this branch vector stays the same,
we take some bits of the PC, we index into the
branch history table, but instead of having a 1-bit counter
or a 2-bit counter in each entry. Now we have a
single bit history in each entry, a two bit counter for
when the history is 0, and the separate two bit counter
for when the history is 1. So the state of the predictor is now not just
the state of a single 1-bit or 2-bit
counter, it's the state of a single bit history
and two of these counters. So now let's
look at the behavior of predictors over time,
like this. We have the predictors state, the
prediction, the outcome, and whether the prediction was correct.
Let's start the predictor in a state where the
history bit is and the 2, 2-bit predictors are
both in the strong not taken state. So again
all three of these together are now the state of
the predictor. The prediction in this type of predictor
is formed by using the history bit to tell
us which of the two predictor to use. Because
the history is 0, we will be using the first
of the two counters. It's saying strong not
taken, so the prediction will be not taken.
Let's say that this is a branch where
the outcome is taken, not taken, taken, not
taken, et cetera, and in this case the
prediction and the outcome differ. So, we have
an incorrect prediction. Now we will update the
state depending on the outcome. The way we update
the predictor, is to use the history to
index into the two counters. Meaning we will
be using this counter and modify the counter
according to the outcome. In this case, the
outcome is taken, so the first of the two counters will be moved to the weak
not-taken state from the strong. So this counter
becomes weak not taken, this counter is not affected,
and then we shift into the history the actual
outcome, which was taken, so the history becomes 1. When
the history is 1, we're going to be using the second
of the two counters. So pretty much, we use the
history to kind of index into this array of
counters that only has two counters, so when it's 1
we use this one. The prediction will be not taken
and it will be right. The state of the predictor
is now updated, so that we use the
history to index again into the counter, modify that
counter according to the outcome. It stays strong
not taken, because that's already as convinced about the
not taken outcome as it can be. The
other counter just stays the same. And the history
now shifts in the zero because of the
not taken outcome. So now we have the state
of 0 weak not taken, strong not taken to
predict the next outcome. Our prediction now will index into
the array of counters, get the first one. Weak
not taken means that we still predict not taken. We
are wrong. We update the predictor by finding the
counter that corresponds to the history and this case 0
means we use this one. We update it using the
outcome from weak not take we go to weak taken.
The other counter stays the same, the history shifts
in the one for taken and this is the new
state that we use to predict the next outcome. 1
means we use this counter, that counter says strong not
taken, so we predict not taken. We are correct,
update the predictor, 1 means we update this counter with
not taken, so it stays strong not taken, this one
stays weak not taken because it's not affected by this.
Not taken is shifted into the history so we
can 0, and now we use this to predict
the next outcome. 0 means we use this counter,
this counter say weak taken so we predict taken and
we predict correctly. We update the predictor by using
0 to tell us which counter to update. Taken is
used to update the counter, so from weak taken
it becomes strong taken. The other counter stays the same.
The history shifts in a 1, so we get
this. 1 means we use this counter next. It says
not taken. We predict not taken and we are
right. Update the state of the predictor. 1 means we
update this one with not taken. It stays strongly
not taken, this one stays the same. History shifts in
a 0 so it becomes 0. We use 0
to tell us which counter. This one it's strong taken,
so we predict taken and we will be right. And as you can see, from now on we get
perfect prediction in this predictor. Why? Well, because if
the previous outcome was 0, we are now guessing that
the next outcome will be taken. If the previous
outcome was 1, then we are predicting that the next
outcome will be not taken. And now we do this
continuously because both of these counters have learned strong decisions,
because every time we have seen a 0, it
was followed by taken, every time we have seen a
1, it was followed by not taken. So this predictor
learned the pattern of taken, not taken, taken et cetera.