[CS61C FA20] Lecture 21.4 - Pipelining I: Introduction to Pipelining — Transcript

Full transcript

1. 0:01[Music]
2. 0:10hi
3. 0:11welcome back it's time to introduce the
4. 0:14concept of pipelining which will
5. 0:16increase the compute throughput
6. 0:20but we're not going to start with
7. 0:21computers and compute us
8. 0:23for now let's start with a real life
9. 0:24example or
10. 0:26almost real life example let's suppose
11. 0:29that tan and bora go back to
12. 0:33college and they're in the same dorm
13. 0:36with some of your favorite
14. 0:38tas avi and caroline
15. 0:41and now on say a sunday night
16. 0:45abby borah caroline and dan all need to
17. 0:48do the laundry
18. 0:50in the basement of the la of the dorm
19. 0:53there is
20. 0:54a laundry room and the laundry room has
21. 0:57a washer
22. 0:58a dryer a place to
23. 1:01fold the laundry and then a means to
24. 1:04stash the laundry
25. 1:05to take it back to the tower
26. 1:10so the washer takes 30 minutes the dryer
27. 1:12takes 30 minutes
28. 1:13folding takes 30 minutes because it's
29. 1:15kind of tight space
30. 1:16in there and then stashing takes 30
31. 1:18minutes because we need to walk our
32. 1:20laundry back to our rooms
33. 1:24so since there is four of us that need
34. 1:26to do
35. 1:27our laundry um we have four tasks
36. 1:30a ferrari b for bora c for caroline
37. 1:34and d for dan
38. 1:37so let's see how we could do that so if
39. 1:39you have a kind of a
40. 1:41strange ra they may decide that we have
41. 1:44to do it sequentially
42. 1:46meaning that only one person can do the
43. 1:48laundry at a time
44. 1:50so first would go
45. 1:52[Music]
46. 1:53at uh 6 pm he would start his
47. 1:56laundry and he would go through his four
48. 1:59cycles or four
49. 2:00four four phases of processing the
50. 2:02laundry he would first go
51. 2:04wash it for 30 minutes then dry it fold
52. 2:07it
53. 2:07and stash it and we'll be done at eight
54. 2:10then borax okay go at eight and
55. 2:15wash it dry it fold it and stash it
56. 2:18it'll be done
57. 2:19by 10 pm then carolyn can start
58. 2:23she would wash it dry it
59. 2:28fold it and stash it will be done by
60. 2:30midnight
61. 2:31and then would have to start at midnight
62. 2:35and finish these four
63. 2:37phases of laundry execution
64. 2:41by 2 am
65. 2:44is there a better way to do this yeah
66. 2:47i mean if you look at this scenario we
67. 2:50had
68. 2:52three quarters of a time our resources
69. 2:55were not utilized
70. 2:58washer was used for 30 minutes every two
71. 3:00hours
72. 3:01dryer was used for 30 minutes for
73. 3:06every two hours and the folding area was
74. 3:09utilized only for 30 minutes every two
75. 3:11hours
76. 3:12we used the say the the
77. 3:15stairs for stashing our laundry only 30
78. 3:19minutes
79. 3:21every two hours into ours
80. 3:25so we certainly can try to do
81. 3:28multiples of these things concurrently
82. 3:31multiples of these
83. 3:32phases of laundry concurrently
84. 3:35so instead of having sequential laundry
85. 3:38that takes
86. 3:39eight hours for four loads perhaps we
87. 3:41can do better
88. 3:43so here is an approach of pipelining
89. 3:46laundry processing we still have four
90. 3:48tasks
91. 3:49avis boras caroline's and dance
92. 3:53and we are still going to start at 6 pm
93. 3:57but we should be able to take less time
94. 3:59if we
95. 4:00overlap our tasks so ivy still
96. 4:04has to start at six and he's going to go
97. 4:06through his cycle of
98. 4:07washing drying folding and stashing and
99. 4:10he will be
100. 4:11done at eight but pora doesn't have to
101. 4:13wait to start
102. 4:14at
103. 4:18eight borah can just start
104. 4:22at 6 30
105. 4:25and go through the four phases of
106. 4:28laundry processing
107. 4:31carolyn can start at seven wash dry fold
108. 4:34and stash and then
109. 4:36can start at 7 30 and be done by 9 30
110. 4:39just in time to record his next lecture
111. 4:44all right so that there was a dramatic
112. 4:48speed up
113. 4:48that happened here but notice what
114. 4:51happened
115. 4:52you know let's just make sure that we
116. 4:53understand exactly what happened
117. 4:56the speed up was
118. 5:00instead of eight hours it took us three
119. 5:02and a half hours
120. 5:04for four loads so that's pretty good
121. 5:08there's still things that happen
122. 5:09sequentially
123. 5:11so phases of laundry processing still
124. 5:14happen sequentially
125. 5:15so each one of us took
126. 5:18two hours like before
127. 5:22but multiple phases
128. 5:25or multiple stages of laundry processing
129. 5:28happen simultaneously
130. 5:32and in particular take a look at what
131. 5:35happened at 7 30
132. 5:37while avi was stashing his laundry
133. 5:40carol borah was folding his laundry
134. 5:43caroline was drying her laundry and dan
135. 5:45was washing
136. 5:46his laundry which
137. 5:49fully utilized all the resources but
138. 5:53while we were starting up the
139. 5:56resources are not fully utilized it took
140. 5:58us
141. 6:00three cycles so to fill up the pipeline
142. 6:05such that we had the full utilization
143. 6:08and then it took us three
144. 6:10cycles to drain the pipeline so if that
145. 6:12is not obvious at 6 pm only the washer
146. 6:15was used
147. 6:18at the 6 30 pm washer and dryer were
148. 6:22used
149. 6:24and so on now if there are a thousand
150. 6:27people trying to use
151. 6:29this laundry system
152. 6:33it wouldn't have taken 2 000 hours if we
153. 6:36were to pipeline it it would have taken
154. 6:39503 hours because
155. 6:42it would take us still three cycles
156. 6:46to fill the pipeline then everybody
157. 6:49would be
158. 6:50running four tasks four
159. 6:53tasks in four phases concurrently and
160. 6:56finally
161. 6:57in the final three cycles
162. 7:00we would drain that pipeline and all
163. 7:03thousand
164. 7:04loads would be
165. 7:08processed in roughly
166. 7:12500 hours okay
167. 7:17so here are some of the key points to
168. 7:19take away about pipelining
169. 7:21laundry processing pipeline link doesn't
170. 7:25help the latency
171. 7:26of a single task because a single task
172. 7:30still takes two hours no matter what but
173. 7:33it
174. 7:33helps with the throughput of the entire
175. 7:35workload
176. 7:36the entire workload got done
177. 7:39significantly faster
178. 7:41in this case 2.3 times faster
179. 7:45there are multiple tasks that are
180. 7:47operating simultaneously or concurrently
181. 7:50using different resources now the
182. 7:53potential
183. 7:54speed up equals to the number of pipe
184. 7:57stages
185. 7:58that can be simultaneously used in this
186. 8:00case there are four of them so
187. 8:02the theoretical speed up that we can
188. 8:05have
189. 8:06is four but we did not achieve the speed
190. 8:09up of four we achieved the speed up of
191. 8:112.3
192. 8:12because we needed some time to
193. 8:17fill the pipe and then drain the pipe
194. 8:21if there were
195. 8:24a thousand tasks that were using the
196. 8:27same pipeline
197. 8:28then we would have gotten much closer to
198. 8:31the
199. 8:32forex of theoretical speedup so that's
200. 8:36one of the key ideas
201. 8:41a few other takeaways here now somebody
202. 8:44decides to
203. 8:45invest in in improving the laundry
204. 8:49system
205. 8:50so supposedly they get a new washer
206. 8:54that takes 20 minutes instead of 30
207. 8:56minutes
208. 8:58and then new stasher new stashing system
209. 9:01perhaps uses an elevator and
210. 9:02i'll take 20 instead of 30 minutes
211. 9:05how much would that improve the whole
212. 9:08operation of the laundry in that dorm
213. 9:11so it you know for example if you had
214. 9:14thousand
215. 9:15people using that laundry uh would it
216. 9:18dramatically shape it
217. 9:19instead of 500 hours would it take about
218. 9:22two-thirds of 500 hours
219. 9:24no because
220. 9:28the trumpet of this whole system is set
221. 9:32by the slowest
222. 9:34slowest tasks or the slowest resources
223. 9:37that we have in the pipeline
224. 9:39this would shave off 10 minutes of the
225. 9:41beginning
226. 9:42and 10 minutes of the end the washer is
227. 9:44going to take
228. 9:4610 minutes less will be done in 20
229. 9:48minutes
230. 9:50instead of 30 and stashing will be done
231. 9:52in 20 minutes instead of 30.
232. 9:54so for four of us instead of three and a
233. 9:56half hours it would take three hours and
234. 9:58ten minutes
235. 9:59but it would not change
236. 10:02the the the time that it takes
237. 10:07a thousand people process their laundry
238. 10:09it would still be about
239. 10:10500 hours why is that because
240. 10:14even if these tasks tasks
241. 10:17take 20 minutes in the beginning in the
242. 10:20end
243. 10:21the time is set by the slowest
244. 10:25resources that we have in here which
245. 10:27will be the washer
246. 10:29and the folding station
247. 10:36that's about it so what we're going to
248. 10:37do in the next segment
249. 10:39we are going to translate this to a risk
250. 10:415
251. 10:42pipeline see you then