So we have seen that our predict not taken predictor, that is very simple to
implement, is pretty accurate. For about 88% of all instructions it
predicts correctly. So why do we even need any better predictors?
Because anything better than this will require some investment of hardware to do
the prediction better. We will answer this question in two ways. First, we will
compare the CPI with the not taken predictor, that is, let's say 88% accurate.
And with a better predictor that let's say 99% accurate. And we will do this for
a five stage pipe line that results branches in the thirrd stage, so
it has a two cycle penalty when ever there is a misprediction. So
it has a two cycle penalty when there is a misprediction. We will also do it for
a 14 stage pipeline that results branches in the eleventh stage, so
it has a 10 cycle penalty for a misprediction, and for
another pipeline that has 14 stages results branches in eleventh. Stage but
this one executes 4 instructions per cycle, so this is very close to
what modern processors look like. So for a not taken predictor and
a 5 stage pipe, the CPA we get is 1 plus how often we mispredict,
which is 12% of all instructions, times the penalty of a misprediction,
which is 2 cycles, which gives us a total CPI of 1.24.
What happens when we have a better predictor? Well,
we now get 1 plus 0.01 only 1% of the time we mispredict and
we get a 2 cycle penalty then. So the CPI now is 1.02.
And now let's look also at the speed up that we get from a better predictor.
If the frequency of the processor stays the same and it executes the same number
of instructions, then the speedup is simply the improvement in the CPI.
So the speedup would be the CPI of the not taken predictor but
divided by the CPI of the better predictor. And
we get a speed up of 1.22. This is actually a noticeable speed up.
But things get more interesting when we have a deeper pipeline.
In that case, we have a 1 plus still 12% I couldn't see for not taken.
But this time the penalty because where is all the branches in the eleventh
stage will be 10, and we get an overall CPI of 2.2. This
is much worse than the 1 that we will be getting with no mispredictions.
With a better predictor we get 1 plus 1% misprediction rate times 10 for
a total CPI of 1.1. And that gives us a speed up of 2.
So as we can see now, the better predictor is giving us twice the performance of
the not taken predictor. And we have seen this already,
that the deeper the pipeline, the more benefit we get from a better predictor.
But what happens when we also do multiple instructions per cycle? So
this processor can do four instructions in a cycle. So
the ideal cycles per instruction is one-quarter of a cycle. We add to that
how often we have missed predictions times how many cycles do we waste for
a missed prediction? We still detect missed predictions in the eleventh stage.
So everything done in the ten cycles after the branch was fetched, is wasted.
So, we still have a ten cycle penalty here. And we get an overall CPI of 1.45.
That's actually less than one instruction per cycle.
It's better than a single instruction per cycle processor, but
not that much better for something that should be four times as capable. Now,
let's look at the better predictor, which should give us the ideal CPI plus
1% of the time ten cycle penalty and that results in CPI
of 0.35, or about three instructions per cycle even with the branches.
If we compute the speed-up it's 4.14. So as you can see, if we
have a deeper pipeline or if we are able to execute more instructions per cycle,
then the better predictor is more important than in simpler processors.