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

Loading...

From the course by Princeton University

Computer Architecture

234 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.