1 00:00:03,089 --> 00:00:05,891 Okay. So, we've talked about structural hazard, 2 00:00:05,891 --> 00:00:11,656 or we've talked about pipe-lining basics. And now, we're going to go into the three 3 00:00:11,656 --> 00:00:16,075 main types of hazards. Structural hazard, data hazards, and 4 00:00:16,075 --> 00:00:20,008 control hazards. Let's start off by talking about 5 00:00:20,008 --> 00:00:22,112 structural hazards. Okay. 6 00:00:22,112 --> 00:00:25,896 So, let's, we'll review structural hazards here. 7 00:00:25,896 --> 00:00:31,675 So, structural hazards, as I said before, occurs when two instructions need to use 8 00:00:31,675 --> 00:00:35,073 the same hardware resource at the same time. 9 00:00:35,073 --> 00:00:40,075 And there's a couple approaches on how to resolve this problem. 10 00:00:40,075 --> 00:00:46,529 I mean, we can't actually throw up our hands and just stop the pipeline or maybe, 11 00:00:46,529 --> 00:00:49,320 maybe that kind of is one of the solutions. 12 00:00:49,320 --> 00:00:54,538 But, you need to somehow, think really hard about how to deal with the structural 13 00:00:54,538 --> 00:00:55,892 hazard. One thing you can do is you can explicitly 14 00:00:55,892 --> 00:00:57,964 avoid having different instructions that will be in the pipeline at the same time, 15 00:00:57,964 --> 00:01:02,059 use one structure at the same time. And, you can do this by the programmer, or 16 00:01:02,059 --> 00:01:06,059 maybe the compiler can do this. Next way that you can go about doing this 17 00:01:06,059 --> 00:01:10,080 is you actually have the hardware take care of, basically, all of the problems. 18 00:01:10,080 --> 00:01:15,018 And, there's some complexities to actually building this, but you want to stall the 19 00:01:15,018 --> 00:01:18,408 processor, or stall a portion of the processor, or stall the dependent 20 00:01:18,408 --> 00:01:23,007 instructions or just going to, you, you stall, let's say, the earlier one, when 21 00:01:23,007 --> 00:01:27,590 you go for the contended resource. So, a good example of this is if you have 22 00:01:27,590 --> 00:01:30,223 one resource, two things are trying to use it. 23 00:01:30,223 --> 00:01:35,046 You have a priority encoder in there and the priority encoder says, the earlier 24 00:01:35,046 --> 00:01:40,051 instruction gets to use that because if you sort of invert the priority order, you 25 00:01:40,051 --> 00:01:44,071 might end up with deadlocks. Another good way to do this is you 26 00:01:44,071 --> 00:01:48,596 actually can duplicate the hardware resources, or you can add more ports to a 27 00:01:48,596 --> 00:01:52,304 memory structure, which is sort of the colon of duplicating the hardware 28 00:01:52,304 --> 00:01:55,002 resource. And this is to some extent a solution that 29 00:01:55,162 --> 00:01:59,028 is used pretty widely in something like the, the MIPS pipeline, the basic 5-stage 30 00:01:59,028 --> 00:02:02,005 MIPS pipeline. It lets you duplicate certain resources. 31 00:02:02,005 --> 00:02:06,011 For instance, there's two memory arrays. There's an instruction memory array, and 32 00:02:06,011 --> 00:02:09,072 the data memory array. And we'll look at an example where those 33 00:02:09,072 --> 00:02:13,067 two things are together. But, the simple 5-stage MIPS pipeline was 34 00:02:13,067 --> 00:02:18,089 really designed not to have any structural hazards and the ISA was basically designed 35 00:02:18,089 --> 00:02:22,083 for that to be the case. But, more complex instruction sets and 36 00:02:22,083 --> 00:02:27,081 pipeline designs, you know, you might have to deal with something like a structural 37 00:02:27,081 --> 00:02:30,084 hazard. And even if with the MIPS ISA, if you go 38 00:02:30,084 --> 00:02:35,051 into deeper pipelines you might end up with structural hazards and, and we'll, 39 00:02:35,051 --> 00:02:38,061 we're going to talk about that now. Okay. 40 00:02:38,061 --> 00:02:43,486 So, the first thing we're going to talk about here is structural hazards if we 41 00:02:43,486 --> 00:02:48,003 want to unify the memory. So, as I said in the 5-stage MIPS 42 00:02:48,003 --> 00:02:53,071 pipeline, you have all the hardware you need for every stage, and all the stages 43 00:02:53,071 --> 00:02:58,030 are basically independent. But, let's say, we were going to modify 44 00:02:58,030 --> 00:03:04,998 this, and instead have one memory here. And we wire out, and, and we only have one 45 00:03:04,998 --> 00:03:08,431 port into this memory. So, only one thing can access the memory 46 00:03:08,431 --> 00:03:11,309 at a time. And we wire the program counter into here 47 00:03:11,309 --> 00:03:15,620 to [inaudible] our instructions, we wire the data out up here into the instruction 48 00:03:15,620 --> 00:03:20,538 register so it's just wired in the same place as the instruction memory was 49 00:03:20,538 --> 00:03:23,146 before. And we take the, where we had the data 50 00:03:23,146 --> 00:03:27,068 memory access when we want to do load a restore, and we run those wires down here. 51 00:03:27,068 --> 00:03:31,905 And, we put a multiplexer here to share the address and only one of these 52 00:03:31,905 --> 00:03:34,691 resources can use it as time. Hm. 53 00:03:34,691 --> 00:03:43,900 Okay, well let's draw the pipeline diagram for what happens with something, something 54 00:03:43,900 --> 00:03:52,148 like this hap, when, when you go to execute a load instruction, we'll say, on 55 00:03:52,148 --> 00:03:59,054 a unified memory architecture. So, if we take a look at this structural 56 00:03:59,054 --> 00:04:06,270 hazard example where we have a unified memory, where we have the one memory here 57 00:04:06,270 --> 00:04:11,702 which is replacing both our instruction memory, and our, our data memory. 58 00:04:11,702 --> 00:04:18,386 We need to do a walk through, let's use this example to walk through the pipeline 59 00:04:18,386 --> 00:04:23,798 diagram of how instructions will flow down, this, this example here. 60 00:04:23,798 --> 00:04:29,414 So, let's start off by executing something like a load first. 61 00:04:30,470 --> 00:04:38,651 Then, let's say, we have an add followed by an add followed by an add. 62 00:04:38,651 --> 00:04:43,016 Okay. So, this is our first pipeline diagram 63 00:04:43,016 --> 00:04:44,911 here. We're going to have the load coming down 64 00:04:44,911 --> 00:04:50,473 the pipe, and it's going to execute, or it's going to enter the fetch stage. 65 00:04:50,473 --> 00:04:55,032 Then, it's going to go into decode stage, then it's going to go into the execute 66 00:04:55,032 --> 00:04:59,491 stage, then it's going to go into the memory stage, and finally, write back. 67 00:04:59,491 --> 00:05:04,443 The first add comes down here and it's going to go into fetch. 68 00:05:04,443 --> 00:05:09,263 So, you go into decode, it's going to go into execute, it's going in the memory 69 00:05:09,263 --> 00:05:12,055 stage, and finally, go into here write back. 70 00:05:12,055 --> 00:05:17,047 The third add's going to come down the pipe and go into the fetch stage, decode, 71 00:05:17,047 --> 00:05:21,073 execute, memory, write back. So far, it looks like a pretty idealized 72 00:05:21,073 --> 00:05:27,323 pipeline. This next add, maybe we should just put an 73 00:05:27,323 --> 00:05:31,083 F here. Let's think about this, is, is this right? 74 00:05:31,083 --> 00:05:38,000 Can we have an add fetching from an instruction memory at the same time as a 75 00:05:38,000 --> 00:05:42,995 load is accessing the memory, this unified memory that we have here. 76 00:05:42,995 --> 00:05:48,524 And this is, this is the question. We have this unifying memory and we're 77 00:05:48,524 --> 00:05:52,052 trying to have two things, accessing it at the same time. 78 00:05:52,052 --> 00:05:56,032 And this is a structural hazard, we can't, we can't do this. 79 00:05:56,032 --> 00:05:59,400 So, instead, we are going to push a dash here. 80 00:05:59,400 --> 00:06:05,075 And we will somehow install, or bubble, or no opt, this add for cycle and we're gonna 81 00:06:05,075 --> 00:06:10,630 use this fetch, we're going to use the instruction memory on the subsequent 82 00:06:10,630 --> 00:06:13,324 cycle. And the reason we stall the add and we 83 00:06:13,324 --> 00:06:18,637 don't stall the load is because this is an earlier instruction than this, this is a 84 00:06:18,637 --> 00:06:22,777 later instruction. We want the earlier instructions to finish 85 00:06:22,777 --> 00:06:27,479 first.Otherwise, we might have some deadlock concerns or deadlock problems. 86 00:06:27,479 --> 00:06:31,605 So now, we fetch, we decode, we execute, we use the memory, and we write back. 87 00:06:31,605 --> 00:06:35,618 And you'll note here, this just gets pushed out one cycle because we had to 88 00:06:35,618 --> 00:06:46,010 stall here at the beginning one cycle. And, this memory and this point here is a 89 00:06:46,010 --> 00:06:50,033 structural hazard that we saw, that we had to resolve. 90 00:06:50,033 --> 00:06:56,001 And, in this case, let's say, we stalled one cycle to resolve that hazard. 91 00:06:56,001 --> 00:07:01,077 So, now that we've seen how to do a unified memory and what the pipeline 92 00:07:01,077 --> 00:07:08,057 should look like for that, let's go on to a different example here where we have a 93 00:07:08,057 --> 00:07:13,025 two cycle memory. And this two cycle memory, we're going to 94 00:07:13,025 --> 00:07:18,016 have stage M0 and M1. We put a pipeline register down the middle 95 00:07:18,016 --> 00:07:23,960 of our memory here, but only one thing is able to use that memory at a time. 96 00:07:23,960 --> 00:07:37,095 So let's, let's briefly draw the pipeline diagram for something like, like this. 97 00:07:39,047 --> 00:07:46,555 Okay. So, the second add is going to start 98 00:07:46,555 --> 00:08:00,994 flowing down the pipe and it's going to be in the fetch stage, decode, execute, M0, 99 00:08:00,994 --> 00:08:10,678 M1, write back. Then, we're going to have the load so we 100 00:08:10,678 --> 00:08:17,938 go fetch, decode, execute M0, M1, write back. 101 00:08:17,938 --> 00:08:25,031 And now, we're going to see a structural hazard. 102 00:08:25,031 --> 00:08:32,768 We're going to have, this second load here is going to fetch. 103 00:08:32,768 --> 00:08:41,127 So, I'm going to go into decode, this thing going into execute. 104 00:08:41,127 --> 00:08:49,006 Now, here is the problem. If we were to put M0 here, what we see is 105 00:08:49,006 --> 00:08:56,015 we actually have two different instructions in time waiting to use one 106 00:08:56,015 --> 00:08:59,696 resource, the memory. So, we need to solve this somehow. 107 00:08:59,696 --> 00:09:03,607 Now, how do you go about doing this? Well, there's different approaches and 108 00:09:03,607 --> 00:09:07,888 we'll talk about that in a minute. One approach let's say, is you could 109 00:09:07,888 --> 00:09:12,342 actually stall the pipeline here. So, that was one of our solutions. 110 00:09:12,342 --> 00:09:17,280 You stall a pipeline, so we put a dash here to mean we stalled for a cycle. 111 00:09:17,280 --> 00:09:20,656 And then, we're going to have M0, M1, and then write back. 112 00:09:20,656 --> 00:09:26,124 And you can see that it's basically pushed this instruction back one cycle, but this 113 00:09:26,124 --> 00:09:31,435 doesn't happen with other instructions. And the other thing to note, is that it 114 00:09:31,435 --> 00:09:37,534 doesn't happen if you have something like ad add after a load here, cuz that's going 115 00:09:37,534 --> 00:09:43,302 to go fetch, decode, execute, oh sorry, it stalls here too execute M0, M1. 116 00:09:43,302 --> 00:09:50,433 And these can be overlapped because we're not, we don't actually have any hazard in 117 00:09:50,433 --> 00:09:57,544 this case because there's not load loads or two things that are not trying to use 118 00:09:57,544 --> 00:10:21,001 this memory at the same time. So, you won't end up with a hazard there.