Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[MUSIC PLAYING] PROFESSOR: Hi.
Welcome back to pipelining. So we have looked at structural hazards and data hazards so far.
And we have seen that we deal with structural hazards by provisioning enough hardware in our pipeline such that multiple instructions that are in different phases of execution can be executed concurrently.
On the other hand, those data hazards that are associated with consecutive instructions of R-type or I-type that, in the subsequent instruction, in the following instruction, use the value in the source register.
It was just written into the destination register or supposed to be written into the destination register by the preceding instruction.
In order for them to execute correctly, we need to use data forwarding or data bypassing. So those are those added multiplexers in our pipeline.
So let's take a look at the third type of hazards that we can encounter in our code that is running through the pipeline.
Those are the control hazards that are associated with branches and jumps. And we're going to focus on branches because jumps are a more straightforward condition of our control hazard.
Branches are conditional, and we actually don't know, until later, whether a branch is going to be taken or not. So let's take a look at the branch execution.
So we fetch the instruction, and after the instruction decode phase, we find out that it's a branch.
At that time, we also fetch the values of t1 and t0 from the register file.
And the earliest time when we can figure out whether a branch is taken or not, whether the values of t0 and t1 are equal to each other, is at the end of the execution phase.
That is the earliest time that, if we have appropriate hardware, that we can update the program counter to the address that points to the label, or that we should be executing the next instruction in the stream.
So our next instruction is a sub, in this case. And this sub instruction will enter the pipeline before we actually know whether the previous instruction is a branch or not.
So it is going to be executed regardless of the outcome of the branch. And the same thing holds for the next instruction, which is an or.
So these two instructions are going to be executed regardless of the branch outcome.
But what can happen if the branch is supposed to be taken, we are supposed to update the program counter to a label that is somewhere else.
And these two instructions should not have been executed. The subsequent instructions, this xor, is okay.
The PC will be updated by that point, and we'll know whether the branch was taken or not. So that one is okay, and all the other instructions that follow that.
So in order to have correct execution, because we won't know whether a branch is taken or not for two cycles after we fetch it, we should not be executing the two following instructions.
So we should have two stall cycles after every single branch in the pipeline.
We have no other option because we don't know what is going to be — what is going to happen to the branch, so we better not start executing something — not quite.
Let's take a look at how can we minimize this fairly severe penalty of two clock cycles that are associated with two stops.
So first, a quick observation here — if the branch is not taken, then instructions fetch sequentially after the branch are correct.
We didn't have to cancel, so we could have just gone ahead and executed them. But on the other hand, if the branch is taken, then we need to flush the pipeline.
So we can actually — if the branch turns out to be taken 50% of the time, we can reduce this penalty.
On the other hand, the branch is somehow taken 99% of the time, that's not going to help us because 99% of the time we'll have to cancel these two instructions that are already in the pipeline.
Let's recap how do we cancel them. Well, we basically in-flight convert them to nops. How do we do that? Well, the same way how we did that with the load instruction.
We alter the control bits for the instructions that are employed such that they don't change the state of the processor.
So if the branch — when we find out that the branch is taken during the early phase, we go ahead and change this instruction sub to a nop.
And you have to do the same thing with the or that follows that. Both of those instructions are essentially converted to nops. They do not alter the processor state.
Now, keep in mind what is different here is that we are not — unlike what we have seen in load delay hazards, we are not going to go ahead and repeat these instructions because they shouldn't be taken after this branch.
So after we convert these to two nops, we can update — our program counter is updated.
And you can execute the next instruction that may be in a different part of a code that is sitting at the label, and there we may find an xor.
And all the other instructions are going to follow. So the branch penalty here is reduced to the penalty that only applies when the branch is taken.
So when the branch is taken, we have to insert these two nops in the pipeline. So let's take a look at, is there a way to try to reduce these branch penalties.
So every taken branch is the one that costs us. And it costs us exactly to that cycles of execution. There is a way to do that.
We can observe that branches that are either mostly taken or mostly not taken. And we can predict whether they're going to be taken or not. How do we do that?
I mean, isn't that going to take us a lot of hardware and a lot of effort? Well, it turned out not to be.
The nature of the branches is that we generally use them for some kind of loopy code.
We have seen that we generally loop around some piece of a code in some — say, a while-or a for-loop.
So if our for-loop is supposed to execute 100 times, our branch is going to be taken only once. And 99 times, it's not going to be taken.
So if we predict correctly that this is a branch that is very rarely — 1% of the time — being taken, then we can save on — we can eliminate most of its penalty.
We can reduce this branch penalty to 1% of two stall cycles.
So we would go ahead and execute that code that is inside the loop all of the time, and only occasionally cancel it if our prediction didn't turn out to be correct.
Now, how do we predict if a branch has been taken or not — should be taken or not? Well, there are fairly sophisticated predictors out there.
But the simplest one is just a single bit predictor that keeps track whether the branch was taken last time or not.
It's a pretty good indication if it is going to be taken the next time. So you just keep one bit that says this branch was taken.
It's going to be correct most of the time. And that's what we essentially do. There are much more sophisticated branch predictors, as I mentioned.
If you take, say, CS152, you will learn about some of them.
These branch predictors have been quite well tuned, and they are accurate in high-90s of percent of the time, regardless of a code. It doesn't have to be a loop to 100.
So let's take a look at what does the branch prediction do for us. We are still executing this branch of equal instruction.
And if the branch is taken, we are going to predict that it is going to be taken and start executing code from the label.
We are immediately just loading that label into the program counter. We are going to go ahead with that guess program counter, execute and execute instructions.
But after finishing instructions, we have an opportunity to check our guess and correct ourselves if we are not — if we didn't predict it right. So if our guess was right, everything is good.
If the guess was not right, then we have to go ahead and convert those to instructions that have been executed into nops. And that is it.
This essentially wraps all of the hazards that we have been dealing with — structural, data, and control hazards — to the level that is good enough to enable us to build a functional pipeline.
And it's already fairly high performance. Of course, it can get much higher performance. But for that, you'll have to take some other classes.
We're going to go cover one more topic, but that will happen after a quick break.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.