So let's look at some techniques to deal with outcome prediction for branches, and
we're gonna look at this mostly, first of all, in the static domain.
So things that are not trying to watch the genetic instruction sequence, but instead
are, can, basically statically analyze the instruction sequence and with some high
probability, we'll say, try to predict the location.
The first technique is actually not a prediction at all.
The first technique, we had talked about this a few lectures ago, or we, actually
we talked about this in lecture, two adding delay slots.
So, instead of, I don't know, having that time just be dead cycles, when we're
trying to resolve the branch. We, let's say we put a, if we don't
resolve the branch 'til here, we have what say one delay slot, two delay slots, three
delay slots, and we have three instructions, we'll say.
Or maybe you can redirect at this point out of X and you have two branched delay
slots, depending on how you sort of wire that in if you can make the cycle time.
Let's say if two branch delay slots, what ends up happening is you have instruction
EEQZ here. Let's say that is at address 100.
Then you have two instructions which execute no matter whether the branch is
taken or not taken, that follow it. So these instructions are in the delay
slots of the branch, and you know, if you have architectures have which have things
like load delay slots and other things like that.
But for right now we'll talk about branches.
And we can force these instructions always to execute.
Unfortunately, if you go look at the sort of percentages of probability that you can
actually fill these delay slots, it's pretty low.
It's, always not easy to find work to, to shove down here, 'cuz you're basically
taking work that was above the branch, and in the compiler, reordering the code to
put the, instructions that were before the branch, after the branch.
Hm. Okay.
Well, this is good. I mean, if you can actually make this work
out, this is, this is great. One of the problems with this, though, is
the probability of filling one branch delay slot, let's say is 70%.
The probability to filling two branch delay slots is even lower than that.
It's maybe, 50ish to 40ish%. As we said before, if you have a monkey
pulling out of a, a hat, or just some random process pulling out of a hat,
you're going to do 50%, correct. So.
And as we'll see today, if you use some more fancy branch prediction, or the
outcome prediction techniques, you can get the prediction accuracy of a branch all
the way up into the sort of 95, 96, 97 percent probability.
And all the way people have built, if you look at your sort of out of order
super-scaler on your desktop, your core, or I-7 these days from Intel, that's
probably somewhere in the neighborhood of 98 to 99 percent correct.
So, being able to fill these delay slots, with some probability which is less than
98%, is not a good, good trade off. You would've better been served possibly
by allowing some fancier prediction mechanism trying to fill it, if you care
about performance. Now if you care about complexity, or
reducing complexity in area, a static prediction might be a good, good way to
go. So let's, let's look at some basic rules
of thumb here about static prediction. So the, the overall probability of branch
is taken with say out of something like spec int is 60 to 70%.
But it's not equally distributed. Backwards branches have a much higher
probability of being taken than forward branches.
Okay. So, we got a question coming up here.
Why is this? Yes, so, so loops with high probability or
by definition, to be a loop, you don't have to jump backwards.
You jump forwards, it's, it's pretty hard to loop.
So you jump backwards, it's a loop. And in fact, people like to execute loops,
loops, and stay in loops for a while, 'cause that's where a lot of work is done.
So if you're seeing a loop, and you're just spinning in this, this is increasing
the probability that the backwards branch is taken, and that says a high
probability. Such that this half forward branches 50%.
Hm. Can we, what's, what's going on there?
Forward branch, 50 percent going forward. These are usually some swarm of data
dependent branches, like an if then else clause.
So that's why the probability of this is much, much lower.