[CS61C FA20] Lecture 23.2 - Pipelining III: Control Hazards — Transcript

Full transcript

1. 0:01[Music]
2. 0:12hi
3. 0:12welcome back to pipelining so we have
4. 0:15looked at structural hazards
5. 0:17and data hazards so far
6. 0:20and we have seen that we deal with
7. 0:21structural hazards by
8. 0:23provisioning enough hardware in our
9. 0:25pipeline such that
10. 0:26multiple instructions that are in
11. 0:28different phases of execution
12. 0:30can be executed concurrently on the
13. 0:32other hand
14. 0:34those data hazards that are associated
15. 0:37with consecutive instructions of r type
16. 0:40or i type that uh use the
17. 0:44in the subsequent instruction in the
18. 0:46following instruction use the
19. 0:48um the
20. 0:51value in the source register it was just
21. 0:53written in
22. 0:54to the destination register or supposed
23. 0:56to be written in the destination
24. 0:58register with the preceding instruction
25. 1:02in order for them to execute correctly
26. 1:04we need to use
27. 1:05data forwarding or data bypassing so
28. 1:08those are those added multiplexers
29. 1:12in our pipeline
30. 1:15so let's take a look at the third type
31. 1:17of hazards that we can encounter
32. 1:20in our code that is running
33. 1:23through the pipeline those are the
34. 1:25control hazards that are associated with
35. 1:27branches and jumps
36. 1:29and we're going to focus on branches
37. 1:31because jumps are
38. 1:32a more straightforward condition
39. 1:35of a control hazard branches are
40. 1:38conditional
41. 1:38and we actually don't know um until
42. 1:41later
43. 1:42whether the branch is going to be taken
44. 1:45or not so let's take a look at the
45. 1:47branch execution
46. 1:50so we
47. 1:50[Music]
48. 1:53fetch the the instruction and after the
49. 1:56instruction decode phase we find out
50. 1:58that it's a branch
51. 2:00at that time we also fetch the
52. 2:04values of t1 and t0 from the register
53. 2:06file
54. 2:07in the earliest time when we can figure
55. 2:10out whether a branch is taken or not
56. 2:12whether the values of t 0 and 2 1 are
57. 2:15equal to each other
58. 2:16is at the end of the execution phase
59. 2:20that is the earliest time by that if we
60. 2:23have
61. 2:23appropriate hardware that we can update
62. 2:25the program counter
63. 2:27to the address that points to the label
64. 2:32or um that we should be executing the
65. 2:35next instruction
66. 2:36in the stream
67. 2:40so our next instruction is a sub
68. 2:44in this case and this sub instruction
69. 2:47will enter the pipeline
70. 2:49before we actually know whether the
71. 2:51previous instruction is a branch or not
72. 2:54so it is going to be executed regardless
73. 2:56of the outcome of the branch
74. 2:58and the same thing holds for the the
75. 3:01next instruction which is an or
76. 3:03so these two instructions are going to
77. 3:05be executed regardless of the branch
78. 3:08outcome
79. 3:10but what can happen if the
80. 3:13branch is supposed to be taken
81. 3:16we are supposed to update the program
82. 3:19counter to a label that is somewhere
83. 3:21else
84. 3:21and these two instructions should not
85. 3:24have been executed
86. 3:26the subsequent instructions the sexor
87. 3:30is okay um the
88. 3:33the pc will be updated by that point and
89. 3:36we'll know
90. 3:37um whether the branch was taken or not
91. 3:41so that one is okay
92. 3:44and all the other instructions that
93. 3:46follow that
94. 3:48so uh in order to have correct execution
95. 3:52um because we won't know what whether a
96. 3:55branch is taken or not for two cycles
97. 3:58after we fetch it we
98. 4:01should not be executing the two
99. 4:03following instructions
100. 4:04so um we should have um
101. 4:07two stall cycles after every single
102. 4:10branch in a pipeline
103. 4:13right we have no other option because we
104. 4:15don't
105. 4:17know what is going to be what is going
106. 4:19to happen to the branch so we better not
107. 4:20start executing something
108. 4:24not quite let's take a look at how do
109. 4:27can we minimize this fairly severe
110. 4:29penalty of
111. 4:30two clock cycles that are associated
112. 4:32with two stalls
113. 4:34so first a quick observation here
114. 4:39if the branch is not taken then
115. 4:40instructions fetched
116. 4:43sequentially after the branch are
117. 4:46correct
118. 4:47we didn't have to cancel them so we
119. 4:49could have just
120. 4:50gone ahead and executed them but on the
121. 4:52other hand
122. 4:54if the branch is taken then we need to
123. 4:57flush the pipeline so we can actually if
124. 5:00the
125. 5:00branches turns out to be taken 50 of a
126. 5:03time
127. 5:04we can reduce this penalty
128. 5:08on the other hand the branch is somehow
129. 5:10taken 99
130. 5:11percent of a time that's not going to
131. 5:13help us because 99 percent of the time
132. 5:15would have to
133. 5:17cancel these two instructions that are
134. 5:18already in
135. 5:20the in the pipeline let's recap how do
136. 5:23we cancel them
137. 5:24all we basically in flight convert them
138. 5:26to knobs
139. 5:27how do we do that well um the same way
140. 5:31how we did that with
141. 5:32the load instruction we alter
142. 5:36the control bits for the instructions
143. 5:38that are in flight
144. 5:40such that they don't change the state of
145. 5:43the processor
146. 5:44so if the branch when we find out the
147. 5:47branch is taken
148. 5:48during the alu phase we go ahead
149. 5:52and change this instruction sub
150. 5:55to an off and we have to do the same
151. 5:58thing
152. 5:58with the or that follows that both of
153. 6:01those instructions are
154. 6:02essentially converted to knobs they do
155. 6:05not alter the processor state
156. 6:08now keep in mind what is different here
157. 6:11is that we are not
158. 6:12unlike what we have seen in low delayed
159. 6:15hazards
160. 6:16we are not going to go ahead and repeat
161. 6:18these instructions because they
162. 6:19shouldn't be taken
163. 6:20after this branch so after we convert
164. 6:24these two to knobs we can update our
165. 6:27program counter is updated and we can
166. 6:28execute
167. 6:29the next instruction that may be in a
168. 6:32different part of a code that is sitting
169. 6:33at a label and
170. 6:34there we may find an xor
171. 6:38and all the other instructions are going
172. 6:40to follow
173. 6:42so the branch penalty here
174. 6:46is reduced to the penalty
175. 6:49that is that only applies when the
176. 6:52branch is taken so when the branch is
177. 6:54taken
178. 6:54you have to insert these two knobs
179. 6:58um in the in the pipeline
180. 7:01so let's take a look at is there a way
181. 7:03to try to reduce these branch penalties
182. 7:06so every taken branch is the one that
183. 7:07costs us and it costs us exactly
184. 7:10two dead cycles of execution there is a
185. 7:13way to do that
186. 7:15we can observe that
187. 7:19branches are either mostly taken or
188. 7:21mostly not taken
189. 7:23and we can predict whether they're going
190. 7:25to be taken or not
191. 7:27how do we do that i mean isn't that
192. 7:29going to take us a lot of hardware and a
193. 7:31lot of effort
194. 7:32will turn out not to be the nature of
195. 7:35the branches is
196. 7:36that we generally use them for some kind
197. 7:39of loopy code
198. 7:41we have seen that we generally loop
199. 7:43around some piece of a code
200. 7:45in some say a while or a or a for loop
201. 7:52so if our for loop is supposed to
202. 7:55execute 100 times
203. 7:57our branch is going to be taken only
204. 7:59once
205. 8:00and 99 times is not going to be taken
206. 8:04so if we correct
207. 8:09if we predict correctly that this is a
208. 8:11branch
209. 8:12that is very rarely one percent of a
210. 8:14time
211. 8:15being taken then we can
212. 8:20save all you know we can eliminate most
213. 8:22of its penalty we can reduce this
214. 8:24um branch penalty to one percent
215. 8:28of two stall cycles
216. 8:32so we would go ahead and execute
217. 8:35that code that is inside the loop
218. 8:39all of the time and only occasionally
219. 8:41cancel it if our prediction didn't turn
220. 8:43out to be
221. 8:44correct now how do we predict if a
222. 8:47branch
223. 8:48has been taken or not should be taken or
224. 8:50not
225. 8:53there are fairly sophisticated um
226. 8:57predictors out there but the simplest
227. 8:59one is just a single bit
228. 9:01predictor that keeps track whether the
229. 9:04branch
230. 9:04was taken last time or not that's a
231. 9:07pretty good indication if it is going to
232. 9:08be
233. 9:09taken the next time so
234. 9:13you just keep one bit that says this
235. 9:15branch was taken
236. 9:17it's gonna be correct most of the time
237. 9:21and that's
238. 9:22what we essentially do there are much
239. 9:25more sophisticated
240. 9:27branch predictors as i mentioned if you
241. 9:29take say cs152
242. 9:31you will learn about some of them
243. 9:34these branch predictors have been quite
244. 9:36well tuned
245. 9:37and they are accurate in
246. 9:40high nineties of percent of a time
247. 9:44regardless of a code it doesn't have to
248. 9:46be a loop to a hundred
249. 9:49so let's take a look at what does the
250. 9:51branch prediction do for us
251. 9:52we're still executing this branch of
252. 9:55equal instruction
253. 9:57and if the branch is taken
254. 10:00we are going to you know
255. 10:03predict that it is going to be taken and
256. 10:05start executing code
257. 10:07from the label we are immediately just
258. 10:10loading that label into the program
259. 10:11counter
260. 10:14we are going to go ahead with that guest
261. 10:17program counter execute the next few
262. 10:19instructions but after two instructions
263. 10:20we have an opportunity
264. 10:22to check the our guests and correct
265. 10:24ourselves if we are not
266. 10:27if we did predict it right so if our
267. 10:31guess was right everything is good if
268. 10:33the guess was
269. 10:34not right then we have to go ahead and
270. 10:37convert those two instructions that have
271. 10:39been executed into knobs
272. 10:42and that is it this essentially wraps
273. 10:45all of the hazards that we have been
274. 10:47dealing with
275. 10:48structural data and control hazards
276. 10:52to the level that is good enough to
277. 10:55enable us to build a functional pipeline
278. 10:59and it's already fairly
279. 11:02um high performance
280. 11:06of course you can get much higher
281. 11:07performance but for that you will have
282. 11:09to take
283. 11:10some other classes we're going to go
284. 11:13cover one more topic
285. 11:14but that will happen after a quick break