1 00:00:03,900 --> 00:00:06,826 Okay. So, we've talked about structural hazard, 2 00:00:06,826 --> 00:00:11,769 or we talked about pipe lining basics. And now, we're going to go into the three 3 00:00:11,769 --> 00:00:16,758 main types of hazards. Structural hazard, data hazards, and 4 00:00:16,758 --> 00:00:20,088 control hazards. Let's start off by talking about 5 00:00:20,088 --> 00:00:24,410 structural hazards. Okay. So,, let's we'll review structural 6 00:00:24,410 --> 00:00:27,681 hazards here. So, structural hazards, as I said before, 7 00:00:27,681 --> 00:00:32,714 occurs when two instructions need to use the same hardware resource at the same 8 00:00:32,714 --> 00:00:35,796 time. And there's a couple of approaches on how 9 00:00:35,796 --> 00:00:39,823 to resolve this problem. I mean, we can't just throw up our hands 10 00:00:39,823 --> 00:00:44,100 and just stop the pipeline, or maybe that is actually kind of one of 11 00:00:44,100 --> 00:00:47,309 the solutions. But, you need to somehow think really 12 00:00:47,309 --> 00:00:50,328 hard about how to deal with structural hazard. 13 00:00:50,328 --> 00:00:55,222 one thing you can do is you can explicitly avoid having different 14 00:00:55,222 --> 00:00:58,993 instructions that would be in the pipeline at the same time, use one 15 00:00:58,993 --> 00:01:02,763 structure at the same time. And you can do this by the programmer, or 16 00:01:02,763 --> 00:01:06,645 maybe the compiler can do this. Next way to go about doing this is you 17 00:01:06,645 --> 00:01:10,527 actually have the hardware take care of, basically all of the problems. 18 00:01:10,527 --> 00:01:13,632 And, there's some complexities in actually building this. 19 00:01:13,632 --> 00:01:17,680 But you want to stall the processor, or stall a portion of the processor, or 20 00:01:17,680 --> 00:01:21,890 stall the dependent instructions. or just going to, you, you stall let's 21 00:01:21,890 --> 00:01:25,400 say, the earlier one when you go for the contended resource. 22 00:01:25,400 --> 00:01:30,458 So a good example of this is if you have one resource two things are trying to use 23 00:01:30,458 --> 00:01:35,337 it, you have a priority encoder in there it's, and the priority encoder says, the 24 00:01:35,337 --> 00:01:39,443 early instruction gets to use that because if you sort of invert the 25 00:01:39,443 --> 00:01:42,920 priority order, you might end up with deadlocks. 26 00:01:42,920 --> 00:01:46,642 And another good way to do this is you can actually duplicate the hardware 27 00:01:46,642 --> 00:01:50,315 resource or you can add more ports to a memory structure which is sort of 28 00:01:50,315 --> 00:01:52,697 equivalent of duplicating the hardware resource. 29 00:01:52,697 --> 00:01:56,717 And this is to some extent a solution that is used pretty widely in something 30 00:01:56,717 --> 00:02:00,539 like the, the Mips pipeline, the basic five stage Mips pipeline is we actually 31 00:02:00,539 --> 00:02:03,864 duplicate certain resources. For instance, there's two memory arrays. 32 00:02:03,864 --> 00:02:07,240 There's an instruction memory array and there's a data memory array. 33 00:02:07,240 --> 00:02:11,216 And we'll look at an example where those two things are together. 34 00:02:11,216 --> 00:02:15,865 But, the simple five stage mips pipeline was really designed not to have any 35 00:02:15,865 --> 00:02:19,474 structural hazards. The ISA was basically designed for that 36 00:02:19,474 --> 00:02:22,839 to be the case. But more complex instruction sets in 37 00:02:22,839 --> 00:02:27,182 pipeline designs, you know, you might have to deal with something like a 38 00:02:27,182 --> 00:02:30,914 structural hazard. And even if with the Mips ISA, if you go 39 00:02:30,914 --> 00:02:35,502 to deeper pipelines, you might end up with structural hazards and, and, we'll, 40 00:02:35,502 --> 00:02:38,620 we're going to talk about that now. Okay. 41 00:02:38,620 --> 00:02:44,027 So the first thing we're going to talk about here is structural hazards if we 42 00:02:44,027 --> 00:02:48,280 want to unify the memory. So, as I said in the five stage Mips 43 00:02:48,280 --> 00:02:51,740 pipeline, you have all the hardware you need for 44 00:02:51,740 --> 00:02:55,849 every stage and all the stages are basically independent. 45 00:02:55,849 --> 00:03:01,500 But, let's say we were to modify this. And instead have one memory here. 46 00:03:01,500 --> 00:03:06,268 And we wire out, and, and, we only have one port into this 47 00:03:06,268 --> 00:03:08,933 memory. So, only one thing can access the memory 48 00:03:08,933 --> 00:03:11,881 at a time. And we wire the program counter into here 49 00:03:11,881 --> 00:03:15,681 to go fetch our instructions. We wire the data out up here into the 50 00:03:15,681 --> 00:03:19,140 instruction register. So, it's just wired in the same place as 51 00:03:19,140 --> 00:03:23,222 the instruction memory was before. And we take the, where we had the data 52 00:03:23,222 --> 00:03:25,831 memory access when we want to do a load restore. 53 00:03:25,831 --> 00:03:30,140 And we run those wires down here and we put a multiplexer here to share the 54 00:03:30,140 --> 00:03:34,700 address [COUGH] and only one of these resources can use it as time. 55 00:03:34,700 --> 00:03:40,353 Hm. Okay, well let's draw the pipeline 56 00:03:40,353 --> 00:03:47,001 diagram for what happens with something, something like this 57 00:03:47,001 --> 00:03:54,499 when you go to execute a load instruction we'll say, on a unified memory 58 00:03:54,499 --> 00:03:59,546 architecture. So, if we take a look at this structural 59 00:03:59,546 --> 00:04:06,849 hazard example where we have a unified memory, where we have the one memory here 60 00:04:06,849 --> 00:04:12,214 which is replacing both our instruction memory, and our, our data memory. 61 00:04:12,214 --> 00:04:17,051 We need to walk through let's use this as an example to walk 62 00:04:17,051 --> 00:04:22,945 through the pipeline diagram of how instructions would flow down this, this, 63 00:04:22,945 --> 00:04:26,724 this example here. So, let's start off by executing 64 00:04:26,724 --> 00:04:34,600 something like a load first. [COUGH] Then, let's say we have an add, 65 00:04:34,600 --> 00:04:41,170 followed by an add, followed by an add. Okay. 66 00:04:41,170 --> 00:04:43,497 So, this is our first pipeline diagram here. 67 00:04:43,497 --> 00:04:46,940 We're going to have the load coming down the pipe. 68 00:04:46,940 --> 00:04:51,309 And it's going to execute, or it's going to enter the fetch stage. Then, it's 69 00:04:51,309 --> 00:04:55,853 going to go in to the decode stage, then it's going to go in to the execute stage, 70 00:04:55,853 --> 00:04:59,640 then it's going to go in to the memory stage and finally write back. 71 00:05:00,700 --> 00:05:05,294 The first add comes down here and it's going to go into fetch, so you're going 72 00:05:05,294 --> 00:05:10,901 to decode, it's going to go into execute, it's going in the memory stage, follow 73 00:05:10,901 --> 00:05:14,482 here write back. The third add is going to come down the 74 00:05:14,482 --> 00:05:19,009 pike and then go into fetch stage, decode, execute, memory, write back. 75 00:05:19,009 --> 00:05:22,820 So far, it looks like a pretty idealized pipeline. 76 00:05:22,820 --> 00:05:28,690 This next add, maybe we should just put an F here. 77 00:05:28,690 --> 00:05:31,947 Let's think about this. Is, is this right? 78 00:05:31,947 --> 00:05:37,974 Can we have an add fetching from instruction memory at the same time as a 79 00:05:37,974 --> 00:05:43,420 load is accessing the memory, this unified memory that we have here? 80 00:05:44,440 --> 00:05:48,752 And this is, this is the question. We have this unified memory and we are 81 00:05:48,752 --> 00:05:52,286 trying to have two things accessing it at the same time. 82 00:05:52,286 --> 00:05:56,720 And this is a structural hazard. We can't, we can't do this. 83 00:05:56,720 --> 00:06:01,770 So instead, we're going to put a dash here and we're somehow going to install 84 00:06:01,770 --> 00:06:07,564 or bubble or no op this add for a cycle. And then, we're going to use the fetch we 85 00:06:07,564 --> 00:06:11,636 are going to use the instruction on memory on the subsequent cycle. 86 00:06:11,636 --> 00:06:16,498 And the reason we stall the add and we don't stall the load is because this is a 87 00:06:16,498 --> 00:06:20,023 earlier instruction than this. This is a later instruction. 88 00:06:20,023 --> 00:06:23,001 We want the earlier instructions to finish first. 89 00:06:23,001 --> 00:06:27,437 Otherwise, we might have some deadlock concerns or some deadlock problems. 90 00:06:27,437 --> 00:06:31,874 So now, we fetch, we decode, we execute, we use the memory and we write back. 91 00:06:31,874 --> 00:06:36,310 And you'll note here this just gets pushed out one cycle because we had to 92 00:06:36,310 --> 00:06:45,102 stall here at the beginning, one cycle. [COUGH] And, this memory and this point 93 00:06:45,102 --> 00:06:50,211 here is the structural hazard that we saw, that we had to resolve. 94 00:06:50,211 --> 00:06:55,791 And in this case, let's say, we stalled one cycle to resolve that hazard. 95 00:06:55,791 --> 00:07:01,922 Let's, so now that we've seen how to do a unified memory and what the pipeline 96 00:07:01,922 --> 00:07:08,603 should look like for that let's go on to a different example here where we have a 97 00:07:08,603 --> 00:07:13,341 two cycle memory. In this two cycle memory, we're going to 98 00:07:13,341 --> 00:07:17,767 have stage M0 and M1. We put a pipeline register down the 99 00:07:17,767 --> 00:07:22,644 middle of our memory here. But only one thing is able to use that 100 00:07:22,644 --> 00:07:30,291 memory at a time. So let's, let's briefly draw the pipeline 101 00:07:30,291 --> 00:07:40,039 diagram for something like like this. [SOUND] Okay. 102 00:07:40,039 --> 00:07:53,833 So, the second add is going to start flowing down the pipe and it's going to 103 00:07:53,833 --> 00:08:02,119 be in the fetch stage, decode, execute, M0, M1, 104 00:08:02,119 --> 00:08:09,472 write back. Then, we're going to have the load. 105 00:08:09,472 --> 00:08:18,562 So, you're going to go fetch, decode, execute, M0, M1, write back. 106 00:08:18,562 --> 00:08:25,451 And now we're going to see a structural hazard. 107 00:08:25,451 --> 00:08:34,600 We're going to have this second load here is going to fetch. 108 00:08:34,600 --> 00:08:40,517 So, I'm going on to decode. [COUGH] It's then going to go into 109 00:08:40,517 --> 00:08:45,021 execute. Now, here's the problem. 110 00:08:45,021 --> 00:08:51,541 If we were to put M0 here, what we see is we actually have two 111 00:08:51,541 --> 00:08:58,460 different instructions in time wanting to use one resource, the memory. 112 00:08:58,460 --> 00:09:02,247 So we need to solve this somehow. Now, how do you go about doing this. 113 00:09:02,247 --> 00:09:06,535 Well, there is different approaches and we'll talk about that in a minute. One 114 00:09:06,535 --> 00:09:10,100 approach let's say, is you could actually stall the pipline here. 115 00:09:10,100 --> 00:09:13,673 So, that was one of our solutions. You stall a pipeline, 116 00:09:13,673 --> 00:09:17,180 so we're going to put a dash here to mean we stalled for a cycle. 117 00:09:17,180 --> 00:09:20,819 And then, we're going to have M0, m1, and then write back. 118 00:09:20,819 --> 00:09:25,782 And you can see that it's basically pushed this instruction back one cycle. 119 00:09:25,782 --> 00:09:28,958 But this doesn't happen with other instructions. 120 00:09:28,958 --> 00:09:35,260 And the other thing to note is it doesn't happen if you have something like an add 121 00:09:35,260 --> 00:09:40,498 after a load here because that's going to go fetch, [SOUND] decode, execute, 122 00:09:40,498 --> 00:09:43,193 [SOUND] oh, sorry. It stalls here, too. 123 00:09:43,193 --> 00:09:49,479 execute, [SOUND] M0, M1,. And these can be overlapped because we're not, we don't 124 00:09:49,479 --> 00:09:54,718 actually have any hazard, in this case. Because there's, there's not a load, 125 00:09:54,718 --> 00:10:00,406 loads, or two things are not trying to use this memory at the same time. 126 00:10:00,406 --> 00:10:03,400 So, you won't end up with a hazard there.