1
00:00:03,900 --> 00:00:08,842
Okay. So, we've talked about structural
hazard, or we talked about pipe lining

2
00:00:08,842 --> 00:00:13,200
basics. And now, we're going to go into
the three main types of hazards.

3
00:00:14,380 --> 00:00:19,137
Structural hazard, data hazards, and
control hazards. Let's start off by

4
00:00:19,137 --> 00:00:24,913
talking about structural hazards. Okay.
So,, let's we'll review structural hazards

5
00:00:24,913 --> 00:00:29,820
here. So, structural hazards, as I said
before, occurs when two instructions need

6
00:00:29,820 --> 00:00:34,664
to use the same hardware resource at the
same time. And there's a couple of

7
00:00:34,664 --> 00:00:39,823
approaches on how to resolve this problem.
I mean, we can't just throw up our hands

8
00:00:39,823 --> 00:00:44,981
and just stop the pipeline, or maybe that
is actually kind of one of the solutions.

9
00:00:44,981 --> 00:00:50,328
But, you need to somehow think really hard
about how to deal with structural hazard.

10
00:00:50,517 --> 00:00:56,220
one thing you can do is you can explicitly
avoid having different instructions that

11
00:00:56,220 --> 00:01:00,712
would be in the pipeline at the same time,
use one structure at the same time. And

12
00:01:00,712 --> 00:01:04,981
you can do this by the programmer, or
maybe the compiler can do this. Next way

13
00:01:04,981 --> 00:01:09,418
to go about doing this is you actually
have the hardware take care of, basically

14
00:01:09,418 --> 00:01:13,632
all of the problems. And, there's some
complexities in actually building this.

15
00:01:13,632 --> 00:01:18,012
But you want to stall the processor, or
stall a portion of the processor, or stall

16
00:01:18,012 --> 00:01:22,842
the dependent instructions. or just going
to, you, you stall let's say, the earlier

17
00:01:22,842 --> 00:01:27,483
one when you go for the contended
resource. So a good example of this is if

18
00:01:27,483 --> 00:01:31,827
you have one resource two things are
trying to use it, you have a priority

19
00:01:32,005 --> 00:01:36,706
encoder in there it's, and the priority
encoder says, the early instruction gets

20
00:01:36,706 --> 00:01:41,644
to use that because if you sort of invert
the priority order, you might end up with

21
00:01:41,644 --> 00:01:46,642
deadlocks. And another good way to do this
is you can actually duplicate the hardware

22
00:01:46,642 --> 00:01:50,315
resource or you can add more ports to a
memory structure which is sort of

23
00:01:50,315 --> 00:01:54,136
equivalent of duplicating the hardware
resource. And this is to some extent a

24
00:01:54,136 --> 00:01:58,256
solution that is used pretty widely in
something like the, the Mips pipeline, the

25
00:01:58,256 --> 00:02:02,127
basic five stage Mips pipeline is we
actually duplicate certain resources. For

26
00:02:02,127 --> 00:02:05,850
instance, there's two memory arrays. The
re's an instruction memory array and

27
00:02:05,850 --> 00:02:10,421
there's a data memory array. And we'll
look at an example where those two things

28
00:02:10,421 --> 00:02:15,314
are together. But, the simple five stage
mips pipeline was really designed not to

29
00:02:15,314 --> 00:02:20,086
have any structural hazards. The ISA was
basically designed for that to be the

30
00:02:20,086 --> 00:02:25,347
case. But more complex instruction sets in
pipeline designs, you know, you might have

31
00:02:25,347 --> 00:02:30,486
to deal with something like a structural
hazard. And even if with the Mips ISA, if

32
00:02:30,486 --> 00:02:35,135
you go to deeper pipelines, you might end
up with structural hazards and, and,

33
00:02:35,135 --> 00:02:40,422
we'll, we're going to talk about that now.
Okay. So the first thing we're going to

34
00:02:40,855 --> 00:02:46,622
talk about here is structural hazards if
we want to unify the memory. So, as I said

35
00:02:46,622 --> 00:02:52,605
in the five stage Mips pipeline, you have
all the hardware you need for every stage

36
00:02:52,605 --> 00:02:57,796
and all the stages are basically
independent. But, let's say we were to

37
00:02:57,796 --> 00:03:04,907
modify this. And instead have one memory
here. And we wire out, and, and, we only

38
00:03:04,907 --> 00:03:09,500
have one port into this memory. So, only
one thing can access the memory at a time.

39
00:03:09,500 --> 00:03:14,206
And we wire the program counter into here
to go fetch our instructions. We wire the

40
00:03:14,206 --> 00:03:18,629
data out up here into the instruction
register. So, it's just wired in the same

41
00:03:18,629 --> 00:03:22,939
place as the instruction memory was
before. And we take the, where we had the

42
00:03:22,939 --> 00:03:27,418
data memory access when we want to do a
load restore. And we run those wires down

43
00:03:27,418 --> 00:03:32,295
here and we put a multiplexer here to
share the address and only one of these

44
00:03:32,295 --> 00:03:41,562
resources can use it as time. Hm. Okay,
well let's draw the pipeline diagram for

45
00:03:41,562 --> 00:03:50,596
what happens with something, something
like this when you go to execute a load

46
00:03:50,596 --> 00:03:58,022
instruction we'll say, on a unified memory
architecture. So, if we take a look at

47
00:03:58,022 --> 00:04:05,640
this structural hazard example where we
have a unified memory, where we have the

48
00:04:05,640 --> 00:04:11,685
one memory here which is replacing both
our instruction memory, and our, our data

49
00:04:11,685 --> 00:04:17,957
memory. We need to walk through let's use
this as an example to walk through the

50
00:04:17,957 --> 00:04:24,305
pipeline diagram of how instructions would
flow down this, this, this example here.

51
00:04:24,305 --> 00:04:30,850
So, let's start off by executing something
like a load firs t.

52
00:04:30,851 --> 00:04:41,332
Then, let's say we have an add, followed
by an add, followed by an add. Okay. So,

53
00:04:41,332 --> 00:04:45,553
this is our first pipeline diagram here.
We're going to have the load coming down

54
00:04:45,553 --> 00:04:51,017
the pipe. And it's going to execute, or
it's going to enter the fetch stage. Then,

55
00:04:51,017 --> 00:04:55,503
it's going to go in to the decode stage,
then it's going to go in to the execute

56
00:04:55,503 --> 00:05:00,970
stage, then it's going to go in to the
memory stage and finally write back. The

57
00:05:00,970 --> 00:05:05,294
first add comes down here and it's going
to go into fetch, so you're going to

58
00:05:05,496 --> 00:05:10,901
decode, it's going to go into execute,
it's going in the memory stage, follow

59
00:05:10,901 --> 00:05:16,374
here write back. The third add is going to
come down the pike and then go into fetch

60
00:05:16,374 --> 00:05:21,036
stage, decode, execute, memory, write
back. So far, it looks like a pretty

61
00:05:21,036 --> 00:05:29,667
idealized pipeline. This next add, maybe
we should just put an F here. Let's think

62
00:05:29,667 --> 00:05:36,426
about this. Is, is this right? Can we have
an add fetching from instruction memory at

63
00:05:36,426 --> 00:05:43,071
the same time as a load is accessing the
memory, this unified memory that we have

64
00:05:43,071 --> 00:05:48,752
here? And this is, this is the question.
We have this unified memory and we are

65
00:05:48,752 --> 00:05:53,783
trying to have two things accessing it at
the same time. And this is a structural

66
00:05:53,783 --> 00:05:59,474
hazard. We can't, we can't do this. So
instead, we're going to put a dash here

67
00:05:59,474 --> 00:06:04,590
and we're somehow going to install or
bubble or no op this add for a cycle. And

68
00:06:04,590 --> 00:06:10,360
then, we're going to use the fetch we are
going to use the instruction on memory on

69
00:06:10,360 --> 00:06:15,222
the subsequent cycle. And the reason we
stall the add and we don't stall the load

70
00:06:15,222 --> 00:06:20,205
is because this is a earlier instruction
than this. This is a later instruction. We

71
00:06:20,205 --> 00:06:24,763
want the earlier instructions to finish
first. Otherwise, we might have some

72
00:06:24,763 --> 00:06:29,200
deadlock concerns or some deadlock
problems. So now, we fetch, we decode, we

73
00:06:29,200 --> 00:06:33,940
execute, we use the memory and we write
back. And you'll note here this just gets

74
00:06:33,940 --> 00:06:38,620
pushed out one cycle because we had to
stall here at the beginning, one cycle.

75
00:06:40,553 --> 00:06:49,032
And, this memory and this point here is
the structural hazard that we saw, that we

76
00:06:49,032 --> 00:06:55,241
had to resolve. And in this case, let's
say, we stalled one cycle to resolve that

77
00:06:55,241 --> 00:07:01,215
hazard. Let's, so now that we've seen how
to do a unified memory and what the

78
00:07:01,215 --> 00:07:08,053
pipeline should look like for that let's
go on to a different example here where we

79
00:07:08,053 --> 00:07:14,691
have a two cycle memory. In this two cycle
memory, we're going to have stage M0 and

80
00:07:14,691 --> 00:07:20,693
M1. We put a pipeline register down the
middle of our memory here. But only one

81
00:07:20,693 --> 00:07:28,635
thing is able to use that memory at a
time. So let's, let's briefly draw the

82
00:07:28,635 --> 00:07:45,373
pipeline diagram for something like, like
this. Okay. So, the second add is going to

83
00:07:45,373 --> 00:08:00,908
start flowing down the pipe and it's going
to be in the fetch stage, decode, execute,

84
00:08:00,908 --> 00:08:11,240
M0, M1, write back. Then, we're going to
have the load. So, you're going to go

85
00:08:11,820 --> 00:08:22,813
fetch, decode, execute, M0, M1, write
back. And now we're going to see a

86
00:08:22,813 --> 00:08:33,660
structural hazard. We're going to have
this second load here is going to fetch.

87
00:08:34,600 --> 00:08:44,123
So, I'm going on to decode. It's then
going to go into execute. Now, here's the

88
00:08:44,123 --> 00:08:52,464
problem. If we were to put M0 here, what
we see is we actually have two different

89
00:08:52,464 --> 00:08:59,573
instructions in time wanting to use one
resource, the memory. So we need to solve

90
00:08:59,573 --> 00:09:03,583
this somehow. Now, how do you go about
doing this. Well, there is different

91
00:09:03,583 --> 00:09:07,983
approaches and we'll talk about that in a
minute. One approach let's say, is you

92
00:09:07,983 --> 00:09:13,077
could actually stall the pipline here. So,
that was one of our solutions. You stall a

93
00:09:13,077 --> 00:09:17,444
pipeline, so we're going to put a dash
here to mean we stalled for a cycle. And

94
00:09:17,444 --> 00:09:22,540
then, we're going to have M0, m1, and then
write back. And you can see that it's

95
00:09:22,540 --> 00:09:28,098
basically pushed this instruction back one
cycle. But this doesn't happen with other

96
00:09:28,098 --> 00:09:33,656
instructions. And the other thing to note
is it doesn't happen if you have something

97
00:09:33,656 --> 00:09:41,322
like an add after a load here cuz that's
going to go fetch, decode, execute, oh,

98
00:09:41,322 --> 00:09:48,057
sorry. It stalls here, too. execute, M0,
M1,. And these can be overlapped because

99
00:09:48,057 --> 00:09:53,521
we're not, we don't actually have any
hazard, in this case. Because there's,

100
00:09:53,521 --> 00:09:59,657
there's not a load, loads, or two things
are not trying to use this memory at the

101
00:09:59,657 --> 00:10:03,400
same time. So, you won't end up with a
hazard there.