[CS61C FA20] Lecture 36.1 - MapReduce, Spark: Amdahl's Law — Transcript

Full transcript

1. 0:00and welcome back in this series of
2. 0:03lectures we're going to teach you a new
3. 0:05abstraction called mapreduce and an
4. 0:07implementation of it in many languages
5. 0:09but in particular python
6. 0:11called spark very exciting but first
7. 0:14what we're going to do is teach you this
8. 0:15fundamental principle that
9. 0:16actually we should have taught you a
10. 0:17couple of lecture lectures ago called
11. 0:20amdahl's law and actually it's called
12. 0:22amdahl's heartbreaking law
13. 0:25and part of it is as much as you try you
14. 0:27can't get past this law so that's
15. 0:29heartbreaking that you can't get above
16. 0:30that but let's even tell you what it is
17. 0:32so the model is the following you have
18. 0:34some enhancement you want to
19. 0:36upgrade your gpu upgrade your memory
20. 0:38upgrade some part of your computer
21. 0:40upgrade some part of some system it
22. 0:41actually isn't even
23. 0:42this law applies to anything that's
24. 0:44actually even limited to computers
25. 0:47so the model is the following you have
26. 0:49some enhancement let's call it e
27. 0:51and you want to measure how much your
28. 0:53speed up is is it two times faster
29. 0:55overall overall three 5 10 times faster
30. 0:58100 times faster
31. 0:59based on this enhancement and there's a
32. 1:01very simple equation
33. 1:02that we highlight how to calculate that
34. 1:05so the speed up with e is the execution
35. 1:08time
36. 1:09without e divided by the execution time
37. 1:12with e and you can imagine that right if
38. 1:14the time is halved
39. 1:16then the speed up would be a factor of
40. 1:18two imagine that right the time with the
41. 1:19expansion oh my gosh it's half time to
42. 1:21do this thing
43. 1:22oh it's a new kind of shovel dig a hole
44. 1:24okay well it's half the time that it
45. 1:26used to take
46. 1:26so some time at the bottom half the time
47. 1:28on the top if you
48. 1:29figure that out the time will be a half
49. 1:31then that one half goes over here and
50. 1:33the two flips it
51. 1:34becomes a factor of two speed up that
52. 1:37makes sense 2x
53. 1:38so we don't we often we in fact we
54. 1:40encourage our 61c students and all
55. 1:41students
56. 1:42not to use a percentage speed up because
57. 1:44people just get that math wrong or it's
58. 1:46150
59. 1:46speed up now you want to use 1.5 x it's
60. 1:49just much easier to understand what that
61. 1:51is
62. 1:51okay let's understand how we came up
63. 1:54with that
64. 1:56so let's think about the problem the
65. 1:59every every challenge you have and this
66. 2:01is particularly true with
67. 2:03code that has maybe a part that can be
68. 2:05paralyzed like in openmp here's a
69. 2:07parallel section and a part that
70. 2:09isn't a critical section or part that's
71. 2:10the serial part maybe the setup part and
72. 2:12the gather part at the end the joint
73. 2:14part there's the forking the join but
74. 2:15the parallel parts different from that
75. 2:18so here's what we're going to say we're
76. 2:19going to say the enhancement e
77. 2:21doesn't affect a portion s
78. 2:24so a fortune s like a fraction so s is a
79. 2:26fraction these are all fractional parts
80. 2:28s of a task okay again this is this is
81. 2:31larger than just computer science and
82. 2:32computer engineering
83. 2:34but it does accelerate the remaining
84. 2:36part which is one minus s that's why s
85. 2:38is a fraction that's a percentage
86. 2:39one minus this is a percentage so one
87. 2:41minus s is the parallel paralyzable part
88. 2:44and or whatever enhancementable
89. 2:46enhancement
90. 2:47uh improvementable part that's the one
91. 2:49minus s percentage
92. 2:50a fraction and s is the fraction that
93. 2:52doesn't get changed
94. 2:53and it's going to accelerate by a factor
95. 2:55of p
96. 2:57p is bigger than one okay that's the
97. 2:59hope here so now
98. 3:00let's take a look at what that looks
99. 3:02like then so here is this you notice
100. 3:04that s doesn't change so this s
101. 3:06here is my s that doesn't change okay
102. 3:09but the one minus s part is smaller
103. 3:13by a factor of p okay
104. 3:17so what we get is the execution time
105. 3:20with
106. 3:20e is the execution time
107. 3:24without e this is kind of times s so
108. 3:27this since s didn't change since this s
109. 3:29is still here
110. 3:31that didn't change so that s this is i
111. 3:35this has kind of been distributed if you
112. 3:36multiply this out let's distribute this
113. 3:38let's distribute this into this sum
114. 3:40you get execution time without e times s
115. 3:43which is
116. 3:43that part didn't change see that part
117. 3:45didn't change
118. 3:47and then it was the the old execution
119. 3:48time
120. 3:50the paralyzable part is this fraction
121. 3:52it's the old time it's whatever this
122. 3:53time was
123. 3:54which is the execution time of there
124. 3:57times
125. 3:58the smaller fraction which is one minus
126. 4:00s
127. 4:01over p
128. 4:04this therefore the speed up with e is
129. 4:07simply
130. 4:08that fraction one divided by because
131. 4:10that's kind of the
132. 4:11novel the the normal time we normalize
133. 4:14that the one divided by
134. 4:17s plus one over s over p that's the
135. 4:20fundamental equation that drives
136. 4:22amdahl's law
137. 4:25so now let's pull that out the same same
138. 4:26equation equations ruled it a little bit
139. 4:27differently
140. 4:28and you get the speed up time is 1 over
141. 4:31s is the fraction not sped up 1 minus s
142. 4:35over p is the fraction that is sped up
143. 4:37and in the perfect world as the speed up
144. 4:40factor goes to infinity if i have a
145. 4:43million cores
146. 4:44a trillion cores a trillion helpers
147. 4:46working on this
148. 4:47that term goes to zero and you're left
149. 4:50with one over s
150. 4:51and that's it so the speed up can be no
151. 4:55bigger
152. 4:56and in fact in the perfect world is
153. 4:57equal to 1 over s
154. 5:00that's it where s remember s is the
155. 5:03fraction that's the serial part
156. 5:05all right let's do this together for
157. 5:06example the execution time of
158. 5:08four-fifths of a program can be
159. 5:10accelerated by a factor of 16.
160. 5:12that's pretty good 80 percent of 80 of
161. 5:15the code
162. 5:16is paralyzable think about that can be
163. 5:18accelerated by a factor of 16.
164. 5:20that's awesome what's the overall speed
165. 5:23up am i at 16
166. 5:24am i 50 can't be bigger than 16 am i 15
167. 5:26what's the kind of hit
168. 5:27what's the hit i took in that i didn't
169. 5:29speed up the whole program
170. 5:31so let's work it out well it's one over
171. 5:34what's the fraction that is
172. 5:35serial well that's 20
173. 5:38or 0.2 what's the vector that's parallel
174. 5:410.8
175. 5:42well that 0.8 is going to be 16 times
176. 5:44faster so that's now 0.05
177. 5:47so 0.2 plus 0.05 is 0.25 1 over 0.25 is
178. 5:514.
179. 5:52you put all this money into a 16 time
180. 5:55improvement
181. 5:56but at the end of the day you only had a
182. 5:58four times improvement
183. 6:00heartbreaking that's the reason we call
184. 6:02it amdahl's heartbreaking law
185. 6:04so as we look at this here again here's
186. 6:06a piece of code here's
187. 6:07again s is s and p
188. 6:10s and one minus s or the parallel part
189. 6:13well
190. 6:14yeah part other part is all are always
191. 6:16fractions okay
192. 6:17so here i look at this original time i
193. 6:19have a piece of code that's mostly
194. 6:21parallel
195. 6:22we're doing pretty well and every time i
196. 6:24add more
197. 6:25cores to this there's the number of
198. 6:27cores i'm going to have here
199. 6:30every time i add more cores i'm going to
200. 6:33shrink this parallel part by that factor
201. 6:35so now
202. 6:36this yellow guy is half as high and this
203. 6:39yellow guy is a third as high
204. 6:41and this is a quarter as high i try to
205. 6:42do the graphic that way but that's the
206. 6:44idea
207. 6:45so as i look into the number of
208. 6:47processors
209. 6:50what i see is depending on the parallel
210. 6:54portion
211. 6:54i have different curves for how you know
212. 6:57in the perfect world
213. 6:58how much speed up i can get so if the
214. 7:00parallel portion is
215. 7:02only 50 of the code
216. 7:05well then the serial part is a half and
217. 7:07therefore i only have
218. 7:09two times speed up so i could have an
219. 7:11infinite number of processors that only
220. 7:13have double speed up
221. 7:14that's amazing of course well how about
222. 7:1875 if 75 is parallel then a quarter
223. 7:21think about that then a quarter
224. 7:22is serial that means only a four times
225. 7:24speed up the next curve says how about
226. 7:2790
227. 7:27parallel well that means a tenth and
228. 7:29therefore 10x speed up
229. 7:31how about 95 percent well that's only
230. 7:33that's only
231. 7:34uh one 120th uh is cereal therefore it's
232. 7:38only 20 times
233. 7:40so 20 times is pretty good but you have
234. 7:42to almost get to 95
235. 7:44parallel before you can even get 20
236. 7:46times speed up much less
237. 7:48i mean look at the number of cores we
238. 7:49got 65 000 64k
239. 7:51helpers yeah it was only a factor of 20
240. 7:54faster
241. 7:54and that is amdahl's heartbreaking law
242. 7:57so moral of the story is
243. 7:59do all the work you can to have very
244. 8:02little serial code
245. 8:04a very little setup code go parallel for
246. 8:06the whole thing if you can
247. 8:08and then very little kind of gather and
248. 8:10and join at the end
249. 8:12to be able to release your results
250. 8:13that's the idea if you want to really
251. 8:15maximize it
252. 8:16that it's kind of the overhead it's
253. 8:18almost like the overhead you paid i got
254. 8:19a business and i have to pay the rent
255. 8:20that's the overhead all the profit i
256. 8:22make
257. 8:23the overhead factors in so whatever you
258. 8:25do
259. 8:26try to reduce the overhead the serial
260. 8:28overhead of your code so that you're
261. 8:30almost all
262. 8:31in a parallel stage try to get to the
263. 8:32embarrassingly parallel problem where
264. 8:34very little setup initially maybe like
265. 8:36example initialize all the
266. 8:38and all the sums remember how we were
267. 8:39adding to pi together initialize them
268. 8:41all to zero
269. 8:42that wasn't done in parallel but
270. 8:43although maybe it could be but that was
271. 8:44done in serially
272. 8:45and then compute all the pies that's the
273. 8:48big chunk of the work
274. 8:49and then some small fraction to gather
275. 8:51together and sum it together at the end
276. 8:53all right all right
277. 8:54amdahl's heartbreaking loss sorry sorry
278. 8:56to be the one to be the bearer of brad
279. 8:57bad news but
280. 8:58you got to know about you got to learn
281. 8:59about it all right and that's probably
282. 9:00in the perfect case
283. 9:01with an infinite number of processes
284. 9:03imagine the other elements of it well
285. 9:04one was slower than the other and this
286. 9:06one failed and
287. 9:07we'll talk about all that we'll get to
288. 9:08the topic of uh get the topic of cloud
289. 9:11computing and how we have to deal with
290. 9:12those failures we'll do that later
291. 9:13all right see the next video