Okay, lets get started. So today we're gonna be continuing our venture into out of order processors and super scours. And we're gonna be, start talking about how to fix write after write dependencies, and write after read dependencies in, in a processor pipeline. We're also gonna talk a little bit about one of the questions we had last time. About on a branch what do you do to the Reorder buffer and how do you clean up the state in the reorder buffer. So let's, let's start off, so, so, a little bit about what we're doing today. We're gonna talk about speculation branches. As I said, we're gonna review about that. And then answer, answer the question we had last time about what happens to the reorder buffer when you have a speculative branch. And what are good strategies there. Then we're going to talk about registry naming and how to break write after write and write after read dependencies. And then we're going to talk about memory disambiguation, if we have time. And memory disambiguation is basically figuring out how to have loads and stores execute out, or out of order relative to each other and figuring out how to get the right data for a particular load, after a store. And we call that memory disambiguation. Okay so let's start off by looking once again at our in order, in order, in order, in order pipeline or i4 for short and let's look at what happens on a branch. So here we have some code. Instruction three is a branch. Branches to target T here. And it's executing along. And because everything is in order we don't actually have to worry about, any form of control hazard really happening here. Or, or any, form of real, really bad hazard happening here if we can just basically reach behind us and kill all of the instructions, behind us. None of them will have committed any state at that point. So this is, this is pretty nice, so none of the, we did have speculative instructions here, these three ads, and they started doing stuff. But, they don't have a chance to get to the right back state of the pipe. So they don't even touch the physical register file. So we don't have to clean up, physical register file. We don't have to clean up any of the, the, the state here. We do need to, reset the scoreboard when we take, a, branch mispredict here. And the speculative instruction, the speculative state is wrong. But otherwise, everything, everything is okay. Okay so life gets a little more complicated. When we start to look at in order. Fetch, in order, instruction fetch in order, instruction issue out of order. Executing right back and out of order. Commit. So, here is, here is our pipeline diagram. And, what's interesting to see here, is here we have our branch, note that the, sort of, what is happening in the instructions moves around a little bit. Well, besides that, nothing, nothing much else is really changing here. We're still able to catch our speckle of instructions, before they write back. And what's key here is, we're doing in-order issue. And it's because we do the in order issue that the subsequent speculative instructions, while they are speculative, they're not gonna run ahead and write back early if you will. And what that basically mean is we'd have like a, like a, for this add instruction, there's no W sitting here before this branch hits the branch resolution spot in the pipe. And well let's say we resolve our branches in X0. And then, so this branch here can just redirect the front of the pipe, it can, squash all the subsequent instructions, and reset the scoreboard. So life, life is relatively easy. In order issue or, excuse me, in order fetch, in order issue, out of order writeback, in order commit. Gets a little more complicated here. Well, what's nice here is. We can prevent instructions from writing the physical register file for the same reason as the other pipe, because we did in order issue. The subsequent respective instructions can not go execute any earlier. And we know that, you know, it's pretty quick to go actually issue the or, it's pretty quickly after we issue the branch instruction that we can resolve the target. So, there's maybe, a little bit of shadow there, but if it's one cycle nothing is going to be able to the right back stage of the pipe. Now we do need to clean up the reorder buffer, because this pipe, starts to have, a reorder buffer. So it's not just a, scoreboard that we need to clean up. But we need to actually clean up the reorder buffer here. And, and we have, we have an option. We can either remove from the reorder buffer immediately, or we can wait until these other instructions sorta get to the commit stage to remove from the reorder buffer. And this is the question we had last time. And I'll address them in two more slides in a little more detail. Okay so now we start to get to out of order issue processors. So here we have in order fetch, out of order issue, out of order right back and out of order commit processor. And if you recall this is the processor that we looked at last time that which we said could not have precise interrupts. Because you can have things basically right early. Well for that same reason. You can have instructions that write the register file or write the physical register file early in a pipeline like this. Or actually in this pipe there is both architectural register file, physical register files all together. But if you take a look here, let's take a look at this ad. This ad writes the register file before the branch which is dependent on the multiply has been resolved. Uh-oh. Well we just wrote, the architectural register file. We wrote non-roll, roll-backable state, if you will, or state that is not able to be rolled back. And we actually committed the wrong state and this speculative instruction was not supposed to have executed in the correct program order. So this is the same problem we see with imprecise exceptions showing up here. So, you know, one thing you could do is, if you have a pipeline like this, you can try to fix this by not having any form of control speculation. You can basically stall all these subsequent instructions here, these three adds. And, and, actually, potentially all the rest of these question mark instructions here until the, branch has been resolved. But that's gonna limit your performance. So there's a, there's a problem with this form of pipeline with out of order commit here, is that you have no way to sort of roll back any state. Okay, so this takes us to the, our pinnacle pipeline that we had last time. In order, issue, or excuse me, in order such out of order issue. Out of order executing right back and in order commit. And let's, let's, let's take a look at this. That's sort of competing questions here that we have to think about. First thing is we see that this actually does a write, right here before the branch is known. But conveniently, its writing a different data structure. Its not running our architectural stage. Its running our physical register file. And just like on a, interrupt of some form, we can rollback the architectural register file into the physical register file. We can do that for a branch here also, . So, one of the interesting questions that comes up is, where do we resolve? The branch. And when do we try to kill subsequent instructions? Do we try to do that right when the branch gets resolved? Oops. Or do we wait'til the branch commits. Hmm. Okay, so this, this is, actually goes back to the question we had last time of how easy is it to go clean up the re-order buffer, and how easy is it to go clean up the physical register file. So let's take a look at this example here. Now, having said that, this is all doable. People who build pipelines actually do go clean up all these sort of in-flight instructions. Well, let's look at the complexity of that. So here we have, right when we know the branch gets resolved we actually Kill all of these instructions. And we redirect the front of the pipe to go fetch our target, Our, our true target. Well let's go look what's happening in the physical register file for this case. So in this case in the physical register file this mall has been in the in the physical register file that's a good value. We don't wanna keep that mall. This add here is also read in the physical register file. We don't want to keep that. Ugh. Life starts to get a lot more complicated here. In a pipeline like this, what we're really gonna have to do is we're gonna have to clean up speculative state in the physical register file and we're gonna have to do selective rollback. So instead of just taking the entire architecture register file and overwriting the physical register file, on rollback, we're gonna have to figure out which of these things were speculative and which of these things were not speculative. That's doable. Well, you probably need some structures to go do that, over what we've, over and above what we've already talked about in class. Or rather you, we would have to track which physical registers need to be rolled back on a, a speculation mis predict. Something a little bit easier. Is just a wait to the commit stage. So if we wait to the commit stage, we can see here as we commit. Well, we know that all of the previous instructions of this branch have committed now to the architectural register file. So we know the architectural register file is up to date, relative to the branch, so we can, and then these other sets of instructions may or may not be in the physical register file. They, if the physical register file is completely outdated at this point. So what's nice here is we can copy the entire architectural register file to the physical register file, and effectively roll back everything. Okay. So this, this brings us to the question that we had, During last class about the reorder buffer and, and what do you do with reorder pointers in this branch misspeculation case. So it's, the question really here is well. Do we have to wait for these instructions here to get to the end of the pipe, these, these speculative instructions to get all the way to the end of the pipe, to go clean up the reorder buffer? Or can we just adjust a pointer of the next instruction in the reorder buffer? And the answer, so I've spent a bunch of time thinking about this, is, is we should just be able to adjust the pointer in the reorder buffer to say where the next location is and just fill that in with this target instruction here and that will effectively clean out all of this state here. But where this gets tricky, that's, that, that works great in this case. But as I said, if you go look at this other case here where you actually have, you're trying to pre-emptively sort of kill things, this is not going to work in this case. Because what's really going to happen is we have selective roll back we're going to have to perform here, and just changing the pointer in the router buffer is not enough to go do that, we're going to have to sort of individually clean up entries if we wanna go do that, and that gets a lot more complicated. One other thing which we haven't talked about yet, and one, one motivation for why you may want to wait. To actually clean up the reorder buffer until un, you have, you wanna wait til the expected instructions reach the end of the, the commit stage of the pipe if you will. To clean up the reorder buffer is this other structures, if you have a registry namer, which you're gonna wanna clean up in that same manner. So when we talk about registry renaming in this in this lecture, and what happens is if you sorta think about these inflight speculative instructions. If you have more physical registers than architectural registers. It's possible that if you have to abort these instructions, these speculative instructions, you have other structures like a free list of physical registers, which you have to de-allocate somehow. And if you serve to a bulk deallocate whats a convenient place to sort of deallocate when it tries to commit. So let's look at that in a minute, but that's kind of what I want to get across so you can adjust the pointer for the simple case Trying to do something more aggressive, gets quite a bit harder, because you have to speculatively roll back the physical register file in addition to the rear order buffer. Well, the rear buffering is just a pointer, but the, the physical register you can't just do that with. And if you wait to the end of the pipe you can get you can deallocate physical registers a little bit easier.
