Predication, is another way that we can
try to deal with control hazards, Unlike branch
prediction. when we are really trying to guess
which way, the if-then-else or a bloop or
something branch will be going, predication, is another
way for dealing with control dependencies. Brown friction,
Is about guessing, where the program is going.,
Usually there is no penalty for being correct
in branch prediction, pretty much we just keep fetching, as
if the branch wasn't even there. Even if the branch
is actually taken, we can just keep fetching from the
right place and thus avoid any penalty. But the problem with
branch prediction, Is that in modern processor, there is a
huge penalty if we are wrong in predicting. Keep in
mind that modern processors have a deep bite, with lots
of stages, before the one in which we figure out the
mass prediction, And in each stage, we
have a number of instructions that we have
been doing. So, in this prediction, results
in throwing away all of that work. Usually,
at least several tens, of instructions worth
of work, So the penalty is usually 0
instructions here, and if we have something like,
maybe, a 12 stage pipeline,with four instructions, Per
cycle. We're talking about something like 48 possible
instructions or so, so let's say about 50
instructions, worth of work wasted. Predication is about
doing work, of the both of the directions,so
we basically do the work of both the taken and not taken direction of a branch,
that way the waste is up to 50% of the work that we have been doing.
Because at the position where the branch was supposed
to be, about half of the stuff we've been fetching.
could have been from one path, half of the
stuff was from the other and only half of that
work will actually be used, the rest will be
thrown away. And then we simply throw away the work
from the wrong path, So, what is good about this?
It seems like here, if we're correct, We lose nothing,
if we are wrong we lose a lot, but we can very accurate prediction. While here,
either way, we lose quite a bit. Well, let's see how the branch prediction
and something like predication,compare on different types
of condition branches we might want to predict.
For a loop, usually we want to
do branch prediction, Loop branches, the more iterations
we have, the more they are predictable. Whereas,
with predication, in each iteration of the loop, we
will be dividing our work into two. One is
do the next iteration, the other one is do
the work after the loop, So, if we
have 1,000 iterations, very little of the work will
end up being done correctly. Simply the branch is
diverging too much, When we need to decide whether
to stay in the loop or not, we will be starting the work of both of these.
One, path goes after the loop, the other one,goes
back into the loop and then here we have
a decision again to follow that path,or stay in
the loop that path, stay in the loop. So,
after awhile if we're still doing the work of
all of these paths concurrently, a very small fraction,
of the work we are doing ends up being the staying in the loop
work. And a lot of it has to do with various variants of exiting
the loop, in each iteration, So for a loop, we want to predict function
call returns, Same thing. Except, predication
really makes no sense, because calls and returns.
Always go there, so somehow the direction of not going there makes no sense
to do so we want to predict. Let's say no we have a
large if then else, so what happens we have a decision and
based on it we do,this or we do this, Now the question
is? Should we try to predict this decision or predicate so
that we are doing the work of both and eventually, they will merge and
re-continue, and the answer here, is that if we predict, we waste up to 50
instructions, More likely we wasted nothing. If
we predicate and these branches, have equal wave
then, let's say we have 100 instructions
here and 100 instructions here, We will execute
200 instructions, waste 100 of them either way.
To somehow, the amount of waste with predication here,
Is larger than even the penalty of branch
misprediction. Pretty much, if we predict, and we are
right, we lose nothing, If we predict, and
we are wrong, we lose 50 instructions, Here, we
lose 100 instructions. And we cannot be wrong or
right. But either iii way, we are losing 100
inst,ructions, So for a large if-then-else it seems
like we should be predicting, but let's see, how
things look like for a small if-then-else. Let's
say that we have a decision to make, and
depending on the decision, we have the, Then
or the L spot, but let's say each is
something like five instructions long, now it becomes
interesting. If we do predication, we will be executing,
ten instructions here followed by instructions that
we will do anyway, so the waste
is five instructions either way. Here we're
predicting, and if we're right we waste
nothing but if we're wrong we waste 50, instructions. So, our comparison is that
100% of the time, we waste five
instructions with predications, so we end up with
five on average. For instance of this, whereas here,our branch prediction
rate determines how often we waste this 50 so it's going to be,let's say 0 point
10 because it's 10%, probability of mis predicting in which case we
end up at five two. So if our accuracy of prediction is 90% or better,
then in this case we are better off predicting
the branch. But if our accuracy is less than
90%, we are better off predicating. If, if then
else, is even smaller, then it biases more in
favor of predication, and less in favor of branch
prediction. So for really small, if then elses, We
want to predicate unless we are reasonably sure, that
the branch prediction is going to be highly accurate.