In this course, you will learn to design the computer architecture of complex modern microprocessors.

Loading...

From the course by Princeton University

Computer Architecture

252 ratings

In this course, you will learn to design the computer architecture of complex modern microprocessors.

From the lesson

Branch Prediction

This lecture covers the motivation and implementation of branch predictors.

- David WentzlaffAssistant Professor

Electrical Engineering

So this brings us to some techniques. So we're going to start it off by talking

about prediction and how we can use branch prediction to determine two things.

The outcome and the target address. So branch prediction.

Everyone always thinks that it means this first, thing.

That's not what it means. Encompasses both things, you are to

predict the outcome, so that's whether the branch is taken or not taken and you also

want to predict the target address. Now if you think about that, the first one

sounds relatively trivial. I could sort of pull numbers out, or, I

could, I could pull something out of a hat.

Taken, not taken. You know, just sort of choose randomly.

It's going to do okay, probably. I could probably try to correlate it

somehow using heuristics. The second part here, I have to get the

number exact. So if I choose at random for my branch

prediction outcome, I'm going to get it 50 percent right.

Or if I just always choose, I don't know, we'll, we'll say, if I just always choose

not taken, or something like that. We're probably going to do pretty good.

But, getting the actual destination correct, you have to be exact.

You have to choose a number out of let's say if you have a 32-bit instruction

pointer, two, you have to choose some random number, out of two of the 32

locations and get it right all the time with high accuracy.

So we'll, we'll spend some time about this, talking about this and some

strategies to, to getting the prediction target, and predicting our branch target

and our jump target correct. But, you have to think about both of them,

is all I really wanted to get, get across here.

Okay, so this, this is something we, this is a little bit more review from something

we talked about in lecture, I think, two. We talked a little bit about figuring out

where we can resolve a branch. So here's a little bit longer pipe.

One, two, three, four, five, six, six stages, not quite a five stage pipe.

But put issue stage in here. And let's look to see where everything

gets known. So we know that our target address, for

branches, jumps, and jumping link, will likely be known here.

But that's not really helpful, unless we know which way, the branch is.

Or rather, which way the branch is going, or the branch outcome.

Because even if we know at least for jumps and jumping links we know the outcome.

It's taken. But for conditional branches, we may not

know that, until somewhere over here. So we can't necessarily use that

information, until later in the pipe, for branches, to, to do something useful, in

the naive approach. In the execute stage, we know the branch

outcome. We'd talked about a trick in Mips at least

where you can try to pull that forward a stage into our decode stage by having some

sort of special comparator on the output of a register file, comparing it with

zero. But that doesn't work for all branch

types. So if you have something like a branch

equals where you're actually trying to compare two real registers, you have to

wait for the full bypass doing a 32 bit compare is sort of the equivalent of doing

a full 32 bit sort of tract. You're not really going to know that until

the end of the execute stage. That trick doesn't, doesn't really hold

water. It holds water for comparing with zero.

You might even be able to do it if you have lots of extra time in your decode

stage. But let's assume that, you don't.

Also target addresses for jump registers and jump and link register.

Jump registers, jump and link register. You need to read the actual address that

you're going to out of register somewhere. So this, you can't even have a chance of

trying to predict it out here, or the destination.

It's pretty hard. Because, I don't know, it's somewhere in

the bypass, you just compute some value, then you jump through it.

Hm. So the, the, the, we don't, at least down

here, by the time they're done here we have one of two address excuse me, we have

the both of the addresses that the branch can potentially go to.

Go to either the fall through address or the branch target.

We know that sort of at the end of decode stage.

For jumping link registers and jump registers, we don't even have that

information. It's not encoded in the instruction

anywhere. It's encoded in the register.

So, we need to go fetch something from the register.

Might have to go through the bypass network.

So, we're going to have to wait.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.