Re-order buffer

Transcription

So in the last video, we had examined this many cycle pipeline. And we were looking at what problems are introduced by that. So we had already talked about multiple writes finishing in the same cycle and then the problems with read after write and write after write hazards. I am next going to talk about what happens with possibly imprecise exceptions, which is a huge topic in itself. Before I get to that, let me close the page on hazards. So we've talked about two kinds of hazards. There are two other possible hazards. Write after read and read after read hazards. So let's look at the first one. So when does this happen? When there is a read from R1 and sometime later there is a write into R1. So this is write after read. And we expect that the write into R1 will happen later. If you were to reverse the order somehow, that will lead to a wrong result. So can that happen in our basic five-stage pipeline? Let's look at an example. So you have instruction one, which starts in cycle one and then it does the register read in cycle two. Instruction I2 coming behind it starts in cycle two and it does the register write in cycle six. So it guaranteed that the register write happens much after the register read. So you can never have these two being reversed in order and so you will never violate this write after read hazard. Now with our new design, we have things possibly competing out of program order, right? So we said that instructions go through here in program order, but because of the different paths they take and the different latencies for those paths, you could have instructions finishing out of program order. So can that cause a problem? So let's assume the first instruction is this really long divide operation. Thankfully, the register read still happens in the second cycle because you do your register read over here and then you get into this really long 25-cycle path. So thankfully, the divide also does its read very early. And if the second instruction is an add, which finishes really fast, it could do its register write as early as, say, cycle 5 or 6, which, again, thankfully, is after when the read happens. So even with our design, because the register read happens so early, it is impossible to violate this write after read dependency. So this is not possible in this new pipeline. The last hazard is read after read where two instructions are both reading from, say, R1. And this is not a true dependence because it's not as if one instruction is producing a result that is being consumed by the other one. Both are reading R1. Even if I were to reorder these two instructions, you would get exactly the same result. So read after read hazards are usually not a problem. And it's something that we will generally ignore through this course. Now, let's get to this topic of imprecise exceptions. So what exactly is going on over here? All right. So as I said before, things are going in order over here, but there is out-of-order completion of instructions. And how does that possibly give rise to a problem? Let's take an example. So let's say we have an instruction over here, which is a multiply operation, and it writes something into R1. If it starts in cycle one, it's going to take 1, 2, 9 cycles. We have deleted this stage over here so it will finish. So in cycle 10 is when R1 gets written into. Meanwhile, the next instruction was, let's say, an add. So it starts in cycle 2, 3, 4, 5. So maybe it writes into R3 and that write happens as earlier cycle five. And then there's a load over here, which writes into R9. That finishes in cycle seven. So there are all these instructions, which are finishing out of order and they're modifying the contents of R3, R9, and so on. Meanwhile, much later in time, the multiply finishes and you discover that it had an overflow. So at that point, you raise an exception and you want to panic and tell the programmer that something went wrong. And this is where the program went from. And now when the programmer inspects the state of the machine, if they were to inspect the contents of R3 and R9 they would find that it is different from what they expect because the assumption is that you were executing programs in order. There was a fault over here. And surprisingly, these instructions have also had an effect on my process data. This is not a good thing. So you have to make sure that things finished in program order. Or alternatively, it's possible that some instruction showed up over here, you want to jump somewhere else, execute something else, and then you want to come back to this program. And when you come back, you want to continue from here on. But if these instructions have already finished and modified the contents of the register file and if you were to redo those instructions, you could end up with something completely different. So in general, you want to provide an interface where instructions are actually modifying registers in program order. And then if you choose to raise an exception or an interrupt over here, you want to save the state of the program as of this instruction. So you want to save away the program counter. You want to save away the register file. And then after you do whatever else, you want to come back and resume execution over here. And so you have to make sure that the register file stayed that is saved away does not include the effects of these instructions, which happened after this exception point. So a processor that allows the register file to be modified in program order will end up providing precise exceptions. So how do we enforce that? How do we make sure that my processor does allow these in-order modification of the register file? So let me just clear out the screen again. And what I'm going to do [INAUDIBLE] that this state has disappeared, and what I've introduced is a specific buffer over here. And actually, it's a little wider so I'll make this a little bigger. And this buffer is called the reorder buffer. So as instructions come in and get decoded in program order, they create an entry for themselves in the reorder buffer. So the multiply comes first. And it says here on the multiply instruction. And I'm trying to write something into R1. Then the add comes along and says, I'm trying to write something into R3. Then is a load, which writes something into R9, and so on. So now, the add quickly goes through this part of the pipeline and produces a result as early as cycle five. And now, it's getting ready to write to the register file. And it first examines the reorder buffer. And it says that, oh, I'm not the oldest instruction in the reorder buffer. It looks like the multiply has to be allowed to modify R1 before I can go and modify R3. So until the multiply has finished, I will just put my result in over here. And I'll move away. If somebody else wants to come along and read the value R3, they can get it from here. I can give this value to whoever needs it. But for now, I'm not ready to modify the register file. I will just save my value in this reorder buffer. Maybe a couple of cycles later, the load goes through its own stage, comes over here, and also realizes that the multiply has not finished. So I too will write my result into this reorder buffer entry. And I'll update the register file later. In cycle 10, the multiply finally finishes, and it comes here and it says, oh, I'm the oldest instruction. So I can go ahead and modify the register file. So it goes right in and changes the value in R1. And it removes this entry from the reorder buffer. And so that allows this add to now recognize that it is the oldest instruction. Since it's the oldest instruction, it can make its state permanent. So the value that is sitting over here gets written into R3. Next cycle, this instruction becomes the oldest and says the value that is sitting over here can now be copied into R9. So we've, essentially, introduced one more stage over here. There is a reorder buffer stage. And then from the reorder buffer, I copy things into my register file. So that's my register write stage. So things came in order and then because of instructions taking these different paths, you have out-of-order completion into the reorder buffer. And now, we have introduced this new commit process, which says that in program order I'm going to copy the results into the register file. So this, again, becomes an in-order commit process. So instructions enter the pipeline in program order. They finish the results out of program order, which could create a problem if there were an exception. So to deal with that problem, I've said that I'm always going to copy results in program order. So if there's ever an exception, the instructions after that accepting point would not yet have copied the results into the register file. Those results would be sitting somewhere in my reorder buffer and I can just discard them. So I've now introduced this in-order commit process, which ensures that the register file contents are being modified in program sequential order. So if I ever raise an exception, the register file state is always clean and it can be copied away and it can be reinstated later. So that's how we dealt with this final problem. So this is where I've defined an exception. And I've said that a processor-- if it fulfills these conditions then it provides precise exceptions. And I've also shown how to deal with each of these problems. So the multiple writes to the register file is handled by throwing more resources at the problem. Write after write hazards are done by detecting the hazard during the instruction decode stage. And imprecise exceptions are being handled by buffering the results as a complete in the reorder buffer. And then they are made permanent in the register file in program order and in order commit process.