In this course, you will learn to design the computer architecture of complex modern microprocessors.
Branch Cost Motivation
Loading...
From the course by Princeton University
Computer Architecture
252 оценки
From the lesson
Branch Prediction
This lecture covers the motivation and implementation of branch predictors.
Meet the Instructors
David WentzlaffAssistant Professor
Electrical Engineering
Why is branch prediction important? So talk a little bit about motivation.
Then we're going to move on and start talking about branch prediction and the
two things we need to predict when we're predicting branches.
And the top thing that jumps to mind is, is the branch take-in or not; the outcome
of the branch. But, that's only half of the, half the
story. And today, we are also going to talk about
figuring out where you actually go when you take a branch.
When I say branch, we're going to loosely put all forms of flow control into this.
So, it's not just a branch; it's a branch, a jump.
You might even think about trying to put something like a interrupt, cuz that
changes your control flow of your program. But, most people try not to predict their
interrupts. It's hypothetically possible.
So let's start by talking about why, why branch prediction and what is the big
motivation for branch prediction? So as I said longer pipelines and more
complex pipelines require us to have relatively good accuracy trying to figure
when we take a branch or when we don't take a branch.
So here we have our in order issue or it's gonna be in order fetch, out of order
issue, out of order execute, in order commit pipeline.
And a couple of things we should note here is, you know, we added this extra stage
out here, we added this issue stage. But we also added this issue queue or
instruction buffer here, or issue window, depending what book you read in the front
here. Well, instructions pile up into this.
And if you don't actually figure out if the branch is taken or not, let's say
until somewhere here, the execute stage. Then, you're going to have more,
basically, instructions you need to kill when you take a branch mis-predict.
So, when you start to go to these out of order processors, when you sort of have
this seemingly short pipeline, seemingly easy pipeline.
More instructions can get sort of queued up into some of these structures,
especially if you have a queue. So this effectively lengthens the front of
your pipeline and makes it such that if you mispredict or you fetch the wrong
instructions relatively often, you're just going to be out in the weeds and you're
going to be killing lots of instructions and having done extra work that you didn't
really want to do. So also, if you wait all the way until the
end of the pipe in sort of these out of order processors to resolve your branch,
that's also going to make life even worse here cuz that makes your mispredict
penalty even longer. Most people don't actually do that.
I mean you might say oh, I don't want to actually kill the instructions until I
know the branch commits and that was sort of a simplistic example we had when we are
talking about these out of order processors we wait all the way till the
end of the pipe and then sort of cleaned out things.
You can wait for it to go to the end of the pipe to actually fully clean out
things but you don't want to redirect in front of the pipe or redirect the fetch or
the PC in the front of the pipe as quickly as possible cuz you just don't want to be
fetching off into the weeds cuz you are then just wasting cycles.
Here we have going back to our super pipelining lecture that we had before.
And we look at the, for some real processors the, the Pentium three, and the
Pentium four, what their branch mis-predict penalty is.
And you know, in this Pentium four here, you have twenty, twenty odd cycles here of
branch mispredicts penalty. That can be pretty painful if you take
branch mispredicts quite often cuz you're going to be taking branches, and the
branch penalty is going to be quite, quite high if you don't have the correct
subsequent instructions after you. Now, you know, we talked about, some
techniques. You could just stall and wait, so you
don't actually predict the branch. But then, if you have to wait for every
branch to get to, let's say, the twentieth stage of the pipe before you go and fetch
the subsequent instruction, that's pretty painful.
So we talked about speculating the next PC or the PC plus four, we'll say in a NIP
style architecture or our architecture where the, each instruction is 32 bits
long. But that doesn't really help you when
you're trying to predict or when, doesn't really help you if you high probability
you think the branch is going to be taken or you think control flow is going to be
taken. So you need to start thinking about how to
actually deal with that in a pipe line. And up to this point we've only talked
about speculating the fall through case. We talked briefly about speculating the
non fall through case, but we didn't say how you could possibly do that.
And today we're going to talk about what the hardware is to do that.
Also making, making life worse is if you start to go wide.
This hurts also. So, if we start to go wide here let's say
we have a dual issue processor but if you go wide here, when you go to kill
instructions you are killing twice as many instructions in flight in the pipe if you
take a branch the wrong direction or mispredict the branch.
So showing that from our pipeline diagram perspective here, this is just recapping
the incidence in a previous lecture. But, here we have a fetch for this branch.
And, we're fetching two instructions per cycle here.
So even if we're relatively short pipeline, you end up with one, two, three,
four, five, six, seven dead instructions on a mispredict.
So, what this really comes down to here is you have the pipeline width or, or
approximately how much depth you end up getting killed, is the pipeline width
multiplied by the branch penalty. So, its width times length before you can
resolve the branch. In, if you can shorten the time it takes
you to resolve the branch, that's good. Or if you can make the processor narrower,
that may be good. It's good from, you know, fewer
instructions being killed. But, we like to execute multiple
instructions at a time cuz that improves our performance.
So this is really the motivation for thinking about trying to put something
useful in this time here and to also trying to reduce the probability that we
start fetching in correcting instructions at all.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
