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.