So now let's look at branch prediction accuracy and how it affect performance.
Our CPI can be written as one, which is the CPI we get with ideal pipe lining,
plus the cycles we add on average per instruction because of branch
mis-predictions. And that can be written as how often we have missed predictions
times the penalty we pay in terms of cycles every time we have
a missed prediction. Note that this part is determined by predictor accuracy.
It really says how often do we mispredict.
This part is determined by our pipeline. Where in the pipeline we figure out
that we have mispredicted. That's approximately how many cycles we pay.
Let's look at a more specific example. Let's look at the processor that
resolves branches in its third stage of the pipeline. And at the processor that
resolves branches in its tenth stage of the pipeline. This is actually much
closer to what modern processors do. let's also look at different accuracies for
predictors. We will look at the predictor that is 50% accurate for
branches and 100% accurate for all other instructions.
And we will look at the predictor that ID 90% accurate for
branches and 100% accurate for all other instructions and in all of
this we will be assuming that about 20% of all instructions are branches.
This is pretty common in programs. Now, let's compute our CPIs.
here we have a CPI of 1 plus how many mispredictions did we get per instruction.
We get 50% this prediction for branches.
So we get 0.5 of branches are mis-predicted, but branches are only 0.2 of
all instructions. So these two really are the mis-predictions per instruction,
it's really the mis-predictions per branch times branches per instruction and
this is multiplied by the penalty that we get per misprediction. If we resolve
branches in the third stage at that time we have two stages of the pipeline
where wrong stuff is already fetched. So the penalty will be two cycles.
Note that it will resolve the branch in the first stage, then there would be
no penalty because next cycle we can fetch the correct instruction. So
branch is being resolved in some stage means really that we pay one cycle less
than that in penalties. And we get an overall CPI of 1.2 here.
If we resolve the branches in the tenth stage, this part is the same,
the accuracy of the predictor and the frequency of branches, but the penalty now
would be nine cycles. So we have 1 plus 0.5 times 0.2
times 9 in this case for the overall CPI of 1.9.
This is a significantly worse CPI than we were getting here. Now let's look at
the more accurate branch prediction. Now what we have is 1 plus mispredictions
per instruction are going to be how many mispredictions we have per branch.
We had 90% accurate, that means we have 10% mispredictions times
0.2 because not all instructions are branches, times 2,
which is our penalty. And we add that with 1.04, so
this is a significant improvement from a more accurate predictor.
Let's look now at this processor. Here we have 1 plus 0.1 times
0.2 times 9, and when we compute this,
we get 1.18. What we can conclude from this, is that a better branch
vector will help us regardless of whether we have a shallow or a deep pipeline,
but the amount of help from a better predictor changes depending on
how deep the pipeline is. Here we have a speed up of 1.15 when
we go from worse to better predictor in a shallow pipeline, but
here we have a speed up of 1.61 when we go from the same worse
predictor to the same better predictor in a deeper pipeline. As you can see,
the deeper the pipeline, the more dependent it is on having a good predictor for
good performance. And that is really why research in
branch vectors continues to this day, although our predictors and
now pretty good. They're significantly better than 90% accurate for branches.
However, our pipelines are deep, so we still benefit from further improvements.