[CS61C FA20] Lecture 22.2 - Pipelining II: Pipeline Hazards — Transcript

Full transcript

1. 0:01[Music]
2. 0:11hello
3. 0:12welcome back to the module that deals
4. 0:15with the pipeline processor design
5. 0:17so far we took our single cycle cpu and
6. 0:21modified it to make it a pipeline
7. 0:24processor
8. 0:25in that process we added some pipeline
9. 0:27registers and moved some resources
10. 0:29around
11. 0:30so the things look a little bit easier
12. 0:33to design
13. 0:36but we didn't quite design a good
14. 0:38pipeline processor
15. 0:40it you know really badly suffers
16. 0:43from some common issues that are
17. 0:47associated with pipeline hazards
18. 0:50now pipeline hazards
19. 0:53stands for a collection of issues that
20. 0:55pipeline processors
21. 0:57encounter when we talk about
22. 1:01pipelined processors the basic thing
23. 1:04that differs
24. 1:05between a pipeline processor and a
25. 1:08single cycle processor
26. 1:09is that we have multiple instructions in
27. 1:11flight in a single cycle processor
28. 1:16our instructions will really depend
29. 1:19only on themselves every instruction
30. 1:21completes and then the next instruction
31. 1:25starts to execute and there is no really
32. 1:28dependency between
33. 1:30them in pipeline processors there are
34. 1:33multiple instructions that are
35. 1:35simultaneously being executed
36. 1:37and if the results of one instruction
37. 1:40affect the following instruction then
38. 1:44we have an issue the following
39. 1:46instruction
40. 1:47cannot proceed there are generally three
41. 1:51types of hazards
42. 1:53so it is important to understand them
43. 1:55because they have different
44. 1:57solutions that will
45. 2:01avoid running into those hazards
46. 2:05in general why their whole called
47. 2:07hazards because
48. 2:09especially earlier on it was not clear
49. 2:12who
50. 2:13was going to take care of these issues
51. 2:16they can be addressed by either a
52. 2:18compiler
53. 2:19or the pipeline pipeline processor
54. 2:22designer
55. 2:23but somebody has to take care of these
56. 2:25hazards if nobody does the processor
57. 2:27doesn't work
58. 2:29or even worse works most of the time but
59. 2:32pay
60. 2:32fails from time to time and it's really
61. 2:35difficult to find
62. 2:36out when and why it fails
63. 2:40so as i said there are three types of
64. 2:42hazards that we can
65. 2:43encounter and those are structural
66. 2:45hazards data hazards and control hazards
67. 2:49it is always a situation that prevents
68. 2:52starting a new instruction while there
69. 2:54is another instruction
70. 2:55that is in flight structural hazards
71. 3:01appear because of contention over a
72. 3:04resource
73. 3:05in most modern processors at least these
74. 3:09that are not
75. 3:10that complicated like the ones that we
76. 3:12are designing in this class
77. 3:14we are really going to run into
78. 3:15structural hazards
79. 3:18and the pipeline is designed to match
80. 3:21the isa
81. 3:22and isa prevents the existence of these
82. 3:24hazards
83. 3:25then the second type are data hazards
84. 3:28data hazards
85. 3:30essentially exists because of the
86. 3:32dependency
87. 3:33between the instructions so if there is
88. 3:37one instruction that is in flight that
89. 3:39is going to write
90. 3:41the result into the register file the
91. 3:43result
92. 3:44that the following instruction cannot
93. 3:48really depend
94. 3:51cannot work with the same operand that
95. 3:54is
96. 3:54before it gets written back into the
97. 3:56register file
98. 3:59otherwise we will be working with an
99. 4:01incorrect value
100. 4:02we're going to talk a little bit more
101. 4:04about that
102. 4:05just in a bit and finally there is a
103. 4:07control
104. 4:08hazard the control hazards happen when
105. 4:10we have branches
106. 4:12if the following instruction that is
107. 4:13being executed in the pipeline
108. 4:15is following a branch
109. 4:20so if there is a branch in the pipeline
110. 4:21and there is another instruction after
111. 4:23that that
112. 4:23next instruction may be invalid if
113. 4:26the branch ends up being taken
114. 4:30so let's talk about structural hazards
115. 4:33in a bit
116. 4:34more of a detail the simplest
117. 4:37type of structural hazard that we
118. 4:39already addressed
119. 4:40in our design even of a single cycle cpu
120. 4:44is the contention between
121. 4:48incrementing the program counter and
122. 4:50performing arithmetic
123. 4:52operations and when addressing
124. 4:56the memory
125. 4:59for example we could have made a mistake
126. 5:03and left out the pc plus four adder and
127. 5:06said
128. 5:07let's use the lanes alu instead so every
129. 5:10time we would have to
130. 5:11add pc 4 to our instruction
131. 5:14we would use the alu
132. 5:18well we have an issue there right
133. 5:22every time we
134. 5:25need to add four to a prior encounter
135. 5:28our alu would not be available
136. 5:31so our processor would not work very
137. 5:34well it would first
138. 5:35you know in one cycle would add pc plus
139. 5:38four
140. 5:39and then in the next cycle would have to
141. 5:41execute things so it was a very natural
142. 5:43decision
143. 5:44and we we just went through that to have
144. 5:47a dedicated adder that
145. 5:48increments the program counter um
146. 5:52so in general structural hazards
147. 5:56appear because two instructions
148. 5:59in the pipeline compete for the same
149. 6:02resource
150. 6:03there are two ways to address structural
151. 6:05hazards one
152. 6:06is to stall and that's what i've just
153. 6:09described as a possible outcome for not
154. 6:12having a pc plus 4 either
155. 6:14essentially the next instruction would
156. 6:17stall
157. 6:18until the previous instruction is not
158. 6:21is is done is finished using that
159. 6:24resource
160. 6:26stall often means introducing
161. 6:30knobs i'll see that in a bit then
162. 6:34more a more more common solution is to
163. 6:36add more hardware to our pipeline
164. 6:39such that all instructions can execute
165. 6:42concurrently
166. 6:46so um let's take a look at the
167. 6:50fairly straightforward structural hazard
168. 6:52that can exist
169. 6:53because of the register file so in
170. 6:57risk five isa our instructions
171. 7:01can access the register file three times
172. 7:04there are two
173. 7:05operands to be read and one to be
174. 7:07written so
175. 7:08our register file has to be able to
176. 7:11support that
177. 7:12otherwise we would have an a shortage of
178. 7:15resources
179. 7:16so our register file is designed to have
180. 7:19two read ports
181. 7:20and a right port there are remember
182. 7:24three addresses that go into the input
183. 7:26of the register file
184. 7:28here's another subtlety in there
185. 7:32in order to be able to complete all of
186. 7:34this all of the
187. 7:36operations in a single cycle or in a
188. 7:38pipeline processor
189. 7:39we made one assumption that the razer
190. 7:42file is fairly fast
191. 7:44so it is faster than many of the other
192. 7:47units that we have in a processor
193. 7:49we can read the register file in a 100
194. 7:51picoseconds and we can also write to a
195. 7:53register
196. 7:53file in 100 picoseconds we'll see that
197. 7:56that's a convenient thing that allows us
198. 7:58to both read and write a register file
199. 8:01in
200. 8:01a single cycle
201. 8:05but the key thing here is register file
202. 8:07has to be designed
203. 8:08to support three accesses per cycle
204. 8:12simultaneously let's take a look at
205. 8:16another type of a structural hazard that
206. 8:18we may have
207. 8:20it may be there may be a memory
208. 8:21contention
209. 8:23so in pretty much every instruction
210. 8:26needs to
211. 8:27access the instruction memory but some
212. 8:31instructions
213. 8:32need to work
214. 8:35you know read or write the data to the
215. 8:38memory
216. 8:40and we said that we have this unified
217. 8:42concept of a memory
218. 8:43that we are working with the store
219. 8:44program computer so there should be just
220. 8:46one memory
221. 8:47so every time there is a load or store
222. 8:50it is going to contend with every other
223. 8:53instruction for the memory access
224. 8:55in this case it is shown
225. 8:58that if you have a load word during
226. 9:02the memory access phase another
227. 9:04instruction that would perhaps
228. 9:06be trying to read an instruction if you
229. 9:08just said one memory
230. 9:09this ad immediate would have to stall
231. 9:12and would have to wait until the load
232. 9:15word
233. 9:15is done if we just had one memory
234. 9:19so a solution to this is to have two
235. 9:23memories
236. 9:24but then you just contradict yourself or
237. 9:27then don't we have
238. 9:28just one memory and what's the story
239. 9:32about two memories
240. 9:33well we do have one main memory that
241. 9:36lives in dram
242. 9:37but we generally have cache that is on
243. 9:40our processor die on our processor chip
244. 9:44and we're going to see that in just next
245. 9:46module in a couple of lectures
246. 9:49essentially there are pieces of
247. 9:53of their chunks of memory on our
248. 9:56processor chip
249. 9:57that have copies of the instructions
250. 10:00that are have been copied from the main
251. 10:02memory
252. 10:03and copies of the data that has been
253. 10:05copied from the main memory
254. 10:06with two separate ways to access it so
255. 10:09we don't have to contend
256. 10:10for the main memory when we are fetching
257. 10:14an instruction
258. 10:15while another instruction is completing
259. 10:18a read
260. 10:19or a write
261. 10:22all right so in summary
262. 10:25structural hazards can exist but they
263. 10:28are
264. 10:28avoided by
265. 10:32typically by the by the hardware design
266. 10:36that matches the ic so we look through
267. 10:39all the instructions that are
268. 10:40in the isa and we make sure that our
269. 10:43hardware is
270. 10:44provisioned to support all all of these
271. 10:47instructions
272. 10:49during the depth of the pipeline that
273. 10:51can exist concurrently
274. 10:52during the depth of a pipeline
275. 10:55so what we have seen is that our
276. 11:00register file has to support whatever
277. 11:03the isa requires us to have
278. 11:07for it and that we need to have separate
279. 11:11instruction and data memories or at
280. 11:13least copies of instruction and data
281. 11:15memory
282. 11:16so we can access them separately
283. 11:19that's it for structural hazards they're
284. 11:21relatively straightforward to understand
285. 11:24the next ones are data hazards which are
286. 11:26a little bit trickier
287. 11:29see you in a bit