[CS61C FA20] Lecture 34.2 - Thread-Level Parallelism II: OpenMP — Transcript

Full transcript

1. 0:01and welcome back now let's see a
2. 0:03wonderful abstraction called
3. 0:04openmp that can allow us work with those
4. 0:06multiple cores very efficiently
5. 0:09and in an easy way without having to add
6. 0:11a lot of time a lot of code in c
7. 0:13so if you had a parallel loop here's a
8. 0:15very simple
9. 0:16loop has a hundred iterations is going
10. 0:18to have the value 0 through 99
11. 0:20inclusive and you just have one thread
12. 0:23just doing all of that
13. 0:25if you had four helpers how would you do
14. 0:26it in parallel well the smart way to do
15. 0:28it if you know about caches
16. 0:30in which you know that it makes sense to
17. 0:33have maybe one worker work with one
18. 0:35particular cache block and have
19. 0:37if you have at least a wider cache block
20. 0:39when you bring the block in
21. 0:40you can work with all your neighbors uh
22. 0:43again
23. 0:44we don't want to have four different
24. 0:45workers all working on the same
25. 0:47particular word or
26. 0:48the same particular block it'd be nice
27. 0:49to kind of separate them out divide it
28. 0:51up
29. 0:52so we break them up into zero through
30. 0:53twenty five seven
31. 0:55twenty four twenty five through forty
32. 0:56nine 50 through 74
33. 0:58and 75 through 99 and so now you have
34. 1:00four different workers
35. 1:01all working on one part of the of the
36. 1:03loop so i'm going to work on this part
37. 1:04of the array you go away from me
38. 1:05i'm going to work on this part of the
39. 1:06array and you do the same thing so there
40. 1:08are four of us all
41. 1:09kind of owning a space of the array
42. 1:11that's the cleanest way to do this
43. 1:12you could also have slices up a
44. 1:14different way which would have been
45. 1:14really bad for the cache in which
46. 1:17each one of them is going to work on i
47. 1:20mod 4 and i'll be imod 4 equals 0.
48. 1:23so 0 4 8c 12 16
49. 1:27and you want you work on i mod 4
50. 1:31equals 1 so 1 5 9. you know you could do
51. 1:35it that way like kind of like how the
52. 1:36way direct map cache maps every other
53. 1:38color to that
54. 1:39but that's not the way we want to do
55. 1:40this in terms of parallel execution you
56. 1:41want to own a space of it
57. 1:43i'll load the whole cache block in i
58. 1:44work on this and i don't bother me i'm
59. 1:46going to break this whole part of the
60. 1:47array so you want to kind of separate
61. 1:48them out in memory so they're not
62. 1:50stepping into those toes if that makes
63. 1:51sense so this is how we divide it up
64. 1:52this a smart way to divide it up
65. 1:55how to do this in openmp it's not that
66. 1:57bad i first have to include the header
67. 1:59file the omp
68. 2:00then i just have to say a pragma pragma
69. 2:02is a way kind of a directive to see to
70. 2:04say i want to do something special
71. 2:05that's above and beyond
72. 2:06pragma omp parallel 4 and it's done
73. 2:10that loop will be paralyzed that's all
74. 2:13you got to do that's amazing and
75. 2:14loops are so common this is a very
76. 2:17effective way to do this so here's an
77. 2:18example
78. 2:19i grab a pen i'll walk you through how
79. 2:21this entire thing works
80. 2:22um there are different compilers that'll
81. 2:24support this
82. 2:25you've got clang here's an example you
83. 2:27got gcc you've got your cc
84. 2:30dash five and i would recommend the top
85. 2:31one gcc-5 because
86. 2:33it lets you only have a very simple line
87. 2:36look dash f openmp that's all you need
88. 2:38to say is dash f openmp
89. 2:40and here's your here's your source code
90. 2:42and you get it out and the a dot works
91. 2:44if you want to use gcc you have to add
92. 2:46dash l openmp
93. 2:48and then you could also name it but i
94. 2:49plan with the x preprocessor much
95. 2:51cleaner just to say
96. 2:52use gcc five which is really nice all
97. 2:55right how does this code what is this
98. 2:56code doing all this code essentially
99. 2:57doing is it has an array of ten elements
100. 3:01whose value is the same as the index so
101. 3:03array element one is the
102. 3:05index one every element nine is index
103. 3:07nine really easy okay
104. 3:09i'm going to tell omp openmp that i want
105. 3:11to use four
106. 3:12different software threads i don't know
107. 3:14how many i have no idea how many
108. 3:16hardware threads i'm allowed how many
109. 3:18cores i have whether i'm hyper 30 on
110. 3:20hyper threading on or off i don't know
111. 3:21that i'm just going to say i want to use
112. 3:22four software threads let's work with
113. 3:24that
114. 3:25this says n is going to be size of a
115. 3:27over size of int
116. 3:29essentially that's just 10 so n is 10
117. 3:31elements
118. 3:32here's my pragma i talked about a second
119. 3:34ago omp
120. 3:35parallel 4 that means this for loop is
121. 3:37going to be paralyzed here we go
122. 3:39so let's take a look at that what
123. 3:40happens here well
124. 3:42for i o 0 i is less than 10 what happens
125. 3:46i'm going to print
126. 3:46the following i'm going to print the
127. 3:48thread number and here's get thread
128. 3:50number
129. 3:51and i'm going to print the value of i so
130. 3:53what i'm essentially doing is saying
131. 3:55which of the three there are four
132. 3:56threads zero one two and three they're
133. 3:58numbered zero through three for four
134. 4:00threads and i'm going to then assign the
135. 4:03value of a of i'm going to overwrite it
136. 4:05before
137. 4:05a of i was just zero through nine i'm
138. 4:06going to replace it and add it
139. 4:09zero through nine obviously has only uh
140. 4:11single digits so
141. 4:12that's only one's values i'm going to
142. 4:14add a tens column and the tens column is
143. 4:16going to be
144. 4:17the thread number that's what this is
145. 4:18basically put the thread stop the thread
146. 4:20number clobber the thread the tens
147. 4:22column with the thread number what
148. 4:24that's going to give me then at the end
149. 4:25when i'm all done
150. 4:26so only this part is paralyzed then at
151. 4:28the end it says we'll go through
152. 4:30all the array and print the values of
153. 4:31the array that's all this is doing
154. 4:32nothing really magical here
155. 4:34but here's what's really i'm gonna show
156. 4:35you a demo in a second it's gonna be fun
157. 4:37just like we predicted the i've color
158. 4:40color-coded this if this helps a little
159. 4:42bit so i'm going to
160. 4:43show you this here so this
161. 4:46single digit the tens digit says all of
162. 4:48these were owned by thread zero
163. 4:50zero one and two the le the first three
164. 4:52this is like zero to twenty four
165. 4:54here it's only ten elements and by the
166. 4:55way this automatically happens
167. 4:57works even though ten isn't uh a
168. 5:00multiple of four
169. 5:01it works beautifully and just you know
170. 5:02all that details of well it's not a
171. 5:04multiple of four
172. 5:05so you can't it just it just handles it
173. 5:07dynamically
174. 5:08beautiful thread number one
175. 5:12handles the values three through five so
176. 5:15this is zero through two is thread zero
177. 5:17uh thread number two handles six and
178. 5:20seven
179. 5:21and thread number three handles eight
180. 5:23and nine so it's
181. 5:24neat look at this three of them three of
182. 5:26them two of them and two of them it did
183. 5:28as well as it could in terms of dividing
184. 5:29them up into
185. 5:30four equal parts amazing the interesting
186. 5:33part
187. 5:34is when you look at what gets printed
188. 5:36out part of what you know professor lee
189. 5:38was talking about in that quote
190. 5:40was that it's unpredictable when things
191. 5:43will return when those
192. 5:44software threads get mapped to hardware
193. 5:45threads and run and then how fast
194. 5:47they finish and complete let's look at
195. 5:50this this happens to be a very
196. 5:52pretty thing look zero one two zero one
197. 5:55sorry zero one two three and then oh
198. 5:57look
199. 5:57zero one two three and then zero
200. 6:00and one so it looks like they did it in
201. 6:03order
202. 6:04now let's run it twice i have this
203. 6:05queued up this is the same code nothing
204. 6:07different this code is available to you
205. 6:09i'm going to run this code now let's run
206. 6:10the for loop
207. 6:12oh look how nice it is all the zeros hit
208. 6:15first zero and two then all the ones
209. 6:16three four five
210. 6:17then look at this then the threes hit
211. 6:20look at this
212. 6:21then the threes the threes came in and
213. 6:23then they finished
214. 6:24and then you got a two and the twos now
215. 6:27let's run it one more time
216. 6:28watch what happens the twos
217. 6:31the ones the threes the zeros zero
218. 6:34three two one look at this zero one two
219. 6:38three zero one two three zero one two
220. 6:41look at this okay
221. 6:45zero one this is uh oh oh look at this
222. 6:48one
223. 6:49the three zeros finished then the one
224. 6:51started then two twos finished
225. 6:54then two more ones finished and then the
226. 6:56threes got in the game
227. 6:58so this is really interesting you have
228. 7:00no idea as i'm running this
229. 7:03who's going to be divided up the three
230. 7:05now they're all together we can just
231. 7:06keep trying this
232. 7:06now the one look there's a first one
233. 7:08came in there then the three then
234. 7:09another zero
235. 7:11i'm just showing you this is a this is
236. 7:12what the realities of this are so
237. 7:14as you're thinking about writing code
238. 7:16you have to write code that's
239. 7:17impervious to how long it takes these
240. 7:20workers to finish that's the hardest
241. 7:22thing to do
242. 7:23as you're stepping back and point how do
243. 7:24i divide this up and also
244. 7:26i don't care how long i have to have
245. 7:28code
246. 7:29that is able to handle naturally just
247. 7:32resilient in terms of handling this and
248. 7:35this particular thing
249. 7:36doesn't if i care about the order of
250. 7:38printing out that doesn't any side
251. 7:39effect like this is going to affect
252. 7:40be affected by the order so you have to
253. 7:42have your computation
254. 7:44be again impervious to how those threads
255. 7:47get
256. 7:48loaded into hardware threads and return
257. 7:49and finish
258. 7:52in summary let's do just two slides for
259. 7:53summary it's a c extension no new
260. 7:55language to learn
261. 7:56well let's learn go and make you do a
262. 7:58project and go people have thought about
263. 8:00doing that and that's a lot harder than
264. 8:01just
265. 8:02living in c getting better at c but
266. 8:04using all the what you know how to see
267. 8:06all that you know about c to make c
268. 8:09parallel
269. 8:10so it's a wonderful extension we're
270. 8:11really really a fan of multi-threaded
271. 8:13shared memory parallelism
272. 8:14you add a compile directory with the
273. 8:16pragma you've got this runtime library
274. 8:17with without h files that includes all
275. 8:19the
276. 8:19headers that you need here's the nice
277. 8:22thing the pragma
278. 8:24any pragma you have is ignored by
279. 8:26compilers who don't know about openmp
280. 8:28um so it's wonderful and it's the same
281. 8:31source code for
282. 8:32multiple architectures one core 16 cores
283. 8:35hyper threading on or off 28 cores
284. 8:38doesn't matter same source code will
285. 8:40just work you gotta
286. 8:41it's just it's just beautiful that way
287. 8:42um it uh it also
288. 8:44only works with shared memory so here's
289. 8:46the programming model
290. 8:49you've got a main thread we call the
291. 8:50main thread or master i prefer the word
292. 8:52main thread you've got and then it's
293. 8:53going to fork
294. 8:54it's going to fork its way and you have
295. 8:56then multiple streams in the parallel
296. 8:58region so all these are multiple streams
297. 9:00all working together this parallel for
298. 9:02this fork is a way
299. 9:04one of these this these are called
300. 9:05patterns this is one of the software
301. 9:07patterns for parallel programming
302. 9:09the idea you fork into these multiple
303. 9:11threads and they go through and then
304. 9:12there's some join at the end and that's
305. 9:14impli all this isn't you used to be able
306. 9:16to have you used to have to
307. 9:18explicitly call a fork and explicitly
308. 9:20call to join this parallel four does all
309. 9:23that for you which is we
310. 9:24which we really like but if you wanted
311. 9:25to have this explicitness you can get to
312. 9:27that
313. 9:28but four conjoint is another option you
314. 9:30know that's another model to think about
315. 9:31this so
316. 9:32there's a parallel region and then you
317. 9:34have some serial region
318. 9:36then a parallel region and this might be
319. 9:37this then another one it might only have
320. 9:40three
321. 9:40and you divide this up and so you have
322. 9:42these serial regions
323. 9:43and you have these parallel regions we
324. 9:46love that
325. 9:47so they begin they begin in a single
326. 9:49process i call it the main thread
327. 9:51this is the sequential execution then
328. 9:53when a parallel region is encountered
329. 9:55it forks it into parallel threads they
330. 9:58execute simultaneously as much as you
331. 9:59can as much as the hardware will allow
332. 10:01and at the end of that there's a join
333. 10:02which brings it back to the serial
334. 10:04portion again
335. 10:05um we're going to see amdahl's law keep
336. 10:07talking about amdahl's law we're not we
337. 10:08didn't talk to amdahl's law yet when we
338. 10:10teach you realize
339. 10:11the point of amble's law is it's really
340. 10:12painful being these serial portions as
341. 10:14much as you try to speed up the code
342. 10:16the longer you spend on these serial
343. 10:17portions the harder it is to speed that
344. 10:19whole thing up uh because that's that's
345. 10:20that's what dominates over time so what
346. 10:23kind of threads are we talking about
347. 10:25remember i mentioned before these are
348. 10:26all software threads i general
349. 10:28thank you so much i generate these
350. 10:30software threads
351. 10:33the os is job it's not my job don't
352. 10:35worry about it not my job man
353. 10:36to multiplex these onto the hardware
354. 10:39thread so
355. 10:40this oh the operating system does that
356. 10:42hard work to figure out who's idle
357. 10:44who's stalled who's blocked or who's
358. 10:46making memory access to go to sacramento
359. 10:48okay get this guy out
360. 10:49and get the next one in all that's
361. 10:51handled by by the os it's wonderful
362. 10:56let me look at other things i want to
363. 10:58say here um
364. 11:01you're certainly competing for hardware
365. 11:03threads you certainly have a fixed
366. 11:04amount of hardware and all those
367. 11:05softwares are competing for that space
368. 11:07there um the key the key thing that's
369. 11:10actually
370. 11:10really hard is that be careful when
371. 11:12you're doing timing
372. 11:14um timing is a complicated thing we
373. 11:16encouraged
374. 11:17people all in 621a 621b cs10 not to use
375. 11:20clock timing don't use clock timing
376. 11:22figure out what this is so we have to be
377. 11:24able to share with you some of the
378. 11:26hardware support some of the software
379. 11:27support to do timing because i i almost
380. 11:29feel like i need to do timing on this
381. 11:31well let me just have a stopwatch and
382. 11:33start do it
383. 11:34have a single thread and time that and
384. 11:36then compare that with a hundred threads
385. 11:38and then stopwatch we kept telling
386. 11:40people don't use a stopwatch in timing
387. 11:41but in some sense we know we need to
388. 11:43think about
389. 11:43uh what support we have so that i don't
390. 11:45have to rely on my my broken stopwatch
391. 11:47for measuring that
392. 11:48we'll learn more about openmp and lots
393. 11:50more examples in the next couple of
394. 11:51lectures we'll see you there