[CS61C FA20] Lecture 33.3 - Thread-Level Parallelism I: Threads — Transcript

Full transcript

1. 0:00and welcome back now let's try to figure
2. 0:03out the solution to the problem we posed
3. 0:05last lecture which was
4. 0:06how do we make use of this incredible
5. 0:08incredibly powerful machine
6. 0:092021 we know how to deal with the wide
7. 0:12vectors
8. 0:13but i've got multiple cores how do i
9. 0:15think about from a software point of
10. 0:16view to be able to make this machine
11. 0:17screen make this machine
12. 0:19do all the you know all the performance
13. 0:21all the compute on some
14. 0:23huge data set how do i make use of
15. 0:24multiple cores attacking at the same
16. 0:26time
17. 0:27let's get started so i ran
18. 0:30i go to my unix machine i type ps minus
19. 0:33x
20. 0:33and please try find the equivalent you
21. 0:35know the equivalent command on your
22. 0:36computer usually it's ps
23. 0:38with some kind of command used to be
24. 0:39dash ef now it's x
25. 0:41here's what i see i've got 156
26. 0:45different programs running at the same
27. 0:46time right now i mean not right now but
28. 0:49at that at the time of that of that
29. 0:50slide
30. 0:51uh 156 how does my laptop do that how's
31. 0:53my laptop somehow
32. 0:54my fan's not running it's quiet how is
33. 0:57it running 156 programs all the same
34. 0:59time happily
35. 1:00the fan isn't even going you know the
36. 1:02over oh my gosh i'm being overheated
37. 1:03the fan it's not this listen to the
38. 1:05microphone no fan very quiet
39. 1:07happy how does it do this how does it
40. 1:09how are you imagine
41. 1:10this is the analogy imagine doing 156
42. 1:13different assignments at the same time
43. 1:15it's crazy so here's the idea first
44. 1:18first name new name for this lecture a
45. 1:20thread
46. 1:21a thread stands for a thread of
47. 1:23execution it is
48. 1:25a single stream of instructions think of
49. 1:28a
50. 1:29you know old-school program a single pc
51. 1:32you load in a program at out and you're
52. 1:34loaded and you're running it
53. 1:36okay you're living in that out just
54. 1:37think about that for a moment okay and
55. 1:38you don't ever
56. 1:39bring you know there's there's some
57. 1:41control there's some control
58. 1:42which is being pat you make a function
59. 1:44call now it goes here then it comes back
60. 1:45and it comes back here it's a single
61. 1:48thread of execution okay that's a thread
62. 1:52a program within it at out could
63. 1:55split or fork itself to have multiple
64. 1:58threads of execution
65. 1:59all running at the same time and then it
66. 2:01might have a way to join them back
67. 2:03together
68. 2:03to have a result so these are kind of
69. 2:05analogies here so it's an easy way to
70. 2:07think about parallelism it's a single
71. 2:08thread of execution i'm just kind of
72. 2:09following
73. 2:10as it sounds like a finger single finger
74. 2:12and say i'm on this line now i'm on this
75. 2:13line now i make a function call now i
76. 2:15return
77. 2:16single finger single thread of execution
78. 2:18okay
79. 2:19i imagine i have old school days i've
80. 2:20got a single cpu and a single core
81. 2:23how do i handle multiple threads how did
82. 2:26your computer
83. 2:27in the day in the days long gone that
84. 2:30had a single core
85. 2:31and had a had and had didn't a single
86. 2:34single cpu in a single core
87. 2:35how is it able to run multiple programs
88. 2:37the os is a program i was able to run
89. 2:39the os and anything else
90. 2:40well here's how it always did it time
91. 2:43sharing
92. 2:44the idea is the single cpu single core
93. 2:47can
94. 2:48essentially by the way i make this
95. 2:49analogy before i make this analogy again
96. 2:52if you if you're a parent with multiple
97. 2:54kids
98. 2:55and if you have more kids than parents
99. 2:56or if you're somehow your spouse
100. 2:58leaves and you're in charge of all the
101. 2:59kids and even more than one you have to
102. 3:01give a lot of love to more
103. 3:02than just a one-on-one one-on-one
104. 3:05defense doesn't work anymore
105. 3:06you should play zone defense as parents
106. 3:08a lot of kids talk about it
107. 3:09so what does that mean you give a little
108. 3:11you can put one you put the youngest to
109. 3:13bed
110. 3:13and then you hang out with the middle
111. 3:14one you put that to bed get some kisses
112. 3:16then you put the older one get that
113. 3:17right then you keep going you give a
114. 3:18little love to every single one
115. 3:20okay so it's a little like a little
116. 3:21slice of time for each particular one
117. 3:24each one thinks so you're giving all the
118. 3:25love to me
119. 3:26and then they go around they read a book
120. 3:27or something they don't realize that
121. 3:28you're actually giving love to other
122. 3:29people at the same time
123. 3:30that's what the cpu is doing cpu says
124. 3:32let me go to the first thread and give
125. 3:34it a little bit of time
126. 3:34a little bit of time it's running it's
127. 3:36processing something and then put it
128. 3:37like
129. 3:38pause it go to the next one and by the
130. 3:41way it's not
131. 3:42unlike the analogy of having children
132. 3:44where they go off read a book it's not
133. 3:45to anything when you're not giving
134. 3:46attention to it's not doing anything
135. 3:47because
136. 3:47you're the only one who can actually
137. 3:48make you know make it compute
138. 3:50so you're the next one give it a little
139. 3:52love the next one you keep rotating and
140. 3:53then you go back to the first one
141. 3:55and if you do this fast enough if you
142. 3:56time share fast enough slice through
143. 3:58time fast enough
144. 3:59you will never notice it it'll just seem
145. 4:01like your computer is a little and the
146. 4:02more you have
147. 4:03the less slice you get but you're like
148. 4:05oh my computer's a little slower
149. 4:06and now my videos maybe dropping frames
150. 4:09or something or
151. 4:10or maybe zoom isn't doing the right
152. 4:11thing if you have a really overworked
153. 4:12machine
154. 4:14maybe it's not able to to the youtube
155. 4:16sometimes can give you a very high
156. 4:19well this might be also transfer of data
157. 4:20but sometimes even the processing of
158. 4:22data
159. 4:23can't um not let's say drop pixels but
160. 4:26it can't
161. 4:26have the highest resolution oh i'm i
162. 4:28need to lower my resolution on youtube
163. 4:30not because the pipe isn't big enough in
164. 4:32the terms of data but i just don't have
165. 4:34time the compute time
166. 4:35to take all that in and do this i'm
167. 4:36going to i'm going to say i'm failing
168. 4:38right now i'm going to now
169. 4:39pinch down the pipe and say give me a
170. 4:40smaller it might actually do this you
171. 4:42might ask a system that says
172. 4:44i have a big enough pipe to handle a
173. 4:451080p or 4k stream or an 8k stream
174. 4:47but i don't have cpu cycles so i'm going
175. 4:49to pinch it down just give me 360 or 720
176. 4:51or something smaller than that
177. 4:53you know to be able to handle that okay
178. 4:55time sharing
179. 4:56slice it through okay if you have a
180. 4:57single thread single cpu multiple
181. 5:00threads you time share between them and
182. 5:01by the way i'll give you a little
183. 5:0330 second story when i was uh
184. 5:04undergraduate we worked on a time
185. 5:06sharing system it was called multix
186. 5:10uh back at about back at mit and
187. 5:13we had a system where i would we would
188. 5:16all uh
189. 5:16the week before finals we would all be
190. 5:18writing our papers so i was i was i went
191. 5:19to the lab the computer lab to write a
192. 5:21paper paper didn't have a laptop laptop
193. 5:23or a personal computer at the time
194. 5:24and i was my freshman year and i'm
195. 5:26writing a paper and
196. 5:28the slice of time that i got was so
197. 5:30small okay with all the
198. 5:32mit other undergraduates doing it i
199. 5:34would type a whole line of characters
200. 5:38and not see my cursor update imagine a
201. 5:40computer so slow
202. 5:42it doesn't even update the cursor
203. 5:44imagine right and then
204. 5:46i remember this i remember being so
205. 5:47frustrated because it would then
206. 5:49give me i was like and give me give me a
207. 5:51little slice it would type all of them
208. 5:52and i have a typo
209. 5:54then i said oh my gosh i have to like
210. 5:55i'd count how many characters to go back
211. 5:57i would
212. 5:58go back 60 change in a to an e and
213. 6:01but i wouldn't update but my cursor
214. 6:03wouldn't even update okay imagine this
215. 6:04world where time sharing was so
216. 6:06stretch thin in terms of resources it
217. 6:09couldn't even
218. 6:09update the screen in a text editor
219. 6:12that's what it was
220. 6:13writing a paper and this was incredibly
221. 6:14painful we all learned to work in the
222. 6:16middle of the night to do this because
223. 6:17you know during five o'clock six o'clock
224. 6:19middle of the afternoon you couldn't
225. 6:20even type 80 characters without having
226. 6:22it paused until it gives a whole line
227. 6:25okay so time sharing can go bad
228. 6:27if you have too many too many things
229. 6:29asking for work
230. 6:30for for one cpu how many 500 kids each
231. 6:33kid be like ah
232. 6:34all crying at the same time wouldn't we
233. 6:35be bad um
234. 6:38so in threads more detail threads are a
235. 6:40sequential flow of instructions that
236. 6:42perform some tasks
237. 6:43and we've been calling this a program
238. 6:44for now but now we're going to know that
239. 6:45we're called it's really called a thread
240. 6:46a lot of times
241. 6:47we start with an abstraction we kind of
242. 6:48reveal the abstraction later it's really
243. 6:50not
244. 6:50you know it's really called a virtual
245. 6:52address space not not just an address
246. 6:53space so
247. 6:54we're doing the same thing here with
248. 6:55with a program program was a program now
249. 6:57program really talking about a thread
250. 6:58for now
251. 7:00each thread has a dedicated program
252. 7:01counter that knows for that thread what
253. 7:03you're doing
254. 7:04separate registers ooh interesting so
255. 7:06now you're thinking how's that different
256. 7:07from
257. 7:08okay well separate registers you can
258. 7:10still access the shared memory we saw
259. 7:11that before
260. 7:13each visit now we have to talk about
261. 7:14here this is actually important the
262. 7:16distinction between a hardware thread
263. 7:18and a software thread okay
264. 7:21each physical core so each core the
265. 7:24element is
266. 7:24a core that's the unit now provides one
267. 7:27or more
268. 7:28hardware threads so a hardware thread is
269. 7:30a thread
270. 7:31running on that core okay
271. 7:34so each is executing a hardware thread
272. 7:36so when the thread
273. 7:37is kind of loaded in a way onto the core
274. 7:40it's a hardware thread now
275. 7:44the operating system supports and can
276. 7:46multiplex between
277. 7:47multiple software threads and the idea
278. 7:50is i might have a program that divides
279. 7:52itself into a hundred different
280. 7:54threads those would be software threads
281. 7:56but i only have a four
282. 7:58core machine so now what does that tell
283. 8:00me
284. 8:01only four of those hundred software
285. 8:03threads can be hardware threads if it's
286. 8:05running
287. 8:06on a core live it's kind of loaded then
288. 8:09it's mapping it onto that
289. 8:10hardware thread that's mapped into that
290. 8:12core it becomes a hardware thread
291. 8:14100 software threads four hardware
292. 8:18threads on a four core machine i might
293. 8:19be able to actually be clever
294. 8:20to get more hardware threads running on
295. 8:22these four cores but for now
296. 8:24we don't know anything about that so
297. 8:25we're going to say only four for a four
298. 8:26core machine
299. 8:27i only have four hardware threads okay
300. 8:29and by the way if you're
301. 8:30still a software thread and have been
302. 8:31mapped to a hardware thread you're
303. 8:33waiting
304. 8:34because because nobody can process you
305. 8:35just like the kid can't read if you're
306. 8:37not being actively
307. 8:38processed by our into our hardware
308. 8:40thread if you're a software thread just
309. 8:41sitting there
310. 8:42you're not processing you're just idle
311. 8:43you're waiting okay
312. 8:45that's the idea hardware threads are
313. 8:47running on the on the core software
314. 8:48threads are all the ones that you
315. 8:49created all the ones that are kind of
316. 8:50there waiting all the ones in the total
317. 8:52space are all software threads the ones
318. 8:53rating on cores
319. 8:54are hardware threats okay just some
320. 8:56names some some nomenclature
321. 8:59is professor edward lee recently
322. 9:01emeritus i believe
323. 9:03he had this wonderful quote about
324. 9:06threads
325. 9:07um i'll just read it to you normally i
326. 9:09don't read slides but it's just too good
327. 9:11although threads seem to be a small step
328. 9:13from sequential computation
329. 9:15in fact they represent a huge step they
330. 9:18discard
331. 9:18the most essential and appealing
332. 9:20properties of sequential computation
333. 9:22understandability you just you know
334. 9:24process now
335. 9:26again you could have code that's hard to
336. 9:27read but in general understandability
337. 9:30predictability and determinism
338. 9:33threads as a model of computation are
339. 9:36wildly
340. 9:37non-deterministic it means kind of
341. 9:39random in a way
342. 9:40and the job of the programmer becomes
343. 9:42one of proving that
344. 9:44non-determinism determinism means that i
345. 9:45can basically promise you what the
346. 9:48output would be there is no there's no
347. 9:49i'm not rolling a dice in there i'm not
348. 9:51shuffling anything there's no randomness
349. 9:52there
350. 9:53non-determinism means i often don't know
351. 9:55the order that these threads are gonna
352. 9:56these threads get out there and what
353. 9:58order they come back
354. 9:59i don't know and that's the hard part
355. 10:02about programming with threads is how do
356. 10:04you manage
357. 10:04all these threads taking different
358. 10:06amounts of time one thread went over
359. 10:07there just
360. 10:08got spun in the loop and maybe it's
361. 10:09going to come back in a year maybe never
362. 10:10come back
363. 10:11so who knows right how many what does my
364. 10:13program does managing
365. 10:15all and a program a single threading
366. 10:16program could do that too but not
367. 10:18if i send all it's like send all the i
368. 10:20hire all these workers go out and do
369. 10:21some stuff
370. 10:22and go like i pay all these b's go do
371. 10:24something and then
372. 10:25some of them haven't come back some of
373. 10:26them have some come back in different
374. 10:28orders
375. 10:28what do i do how do i manage that is
376. 10:30what ed was talking about
377. 10:33so here's the idea the abstraction is
378. 10:37they're all simultaneously active
379. 10:38remember i can rotate the time sharing
380. 10:40lets them all rotate so i've got
381. 10:42even so from the point of view of
382. 10:43software in a way
383. 10:46i don't care how many hardware threads
384. 10:48can ever be run i'm just going to say
385. 10:50well you know what makes sense to break
386. 10:51this up into 100 pieces just because
387. 10:53that's the way
388. 10:53logically this problem breaks up so
389. 10:55break up into 100 pieces
390. 10:56and let them all go and you're going to
391. 10:59notice that
392. 11:01if there actually are only force
393. 11:02hardware threads possible that may be
394. 11:04100
395. 11:07i'll say this way it might be faster to
396. 11:09break if there are only four hardware
397. 11:11threads
398. 11:12and i have a problem to break it up into
399. 11:14more than
400. 11:16four software threads are you gonna say
401. 11:18why why would that
402. 11:19why why why do this here's why let's say
403. 11:22one part of it gets stalled so one of
404. 11:25those hardware just gets stalled okay
405. 11:27so one quarter of your whole thing is
406. 11:29just being idle stalled because some
407. 11:31some part of the code is there and it's
408. 11:32needed to do extra work who knows
409. 11:34it's just stalled that's gonna
410. 11:35eventually return but it's just stalled
411. 11:38imagine if however broken to a hundred
412. 11:41of these guys
413. 11:42okay and 26 number 26
414. 11:45this is the one that's going to stall
415. 11:46like out of the 100 pieces there's one
416. 11:48thing that's just a particularly hard
417. 11:50computation let's just say so when that
418. 11:52comes in
419. 11:53it's going here and imagine if it's a
420. 11:55hundred now let's go back to this model
421. 11:58if only one of those hundred or if it's
422. 12:01only four one of those four
423. 12:02is going to be stalled and can take a
424. 12:04long time if i break into a hundred
425. 12:06pieces
426. 12:07then basically i can compute all 99 of
427. 12:09them like
428. 12:10let's say it's a lot of work so all 99
429. 12:12of them can finish
430. 12:14and that one guy is still solved still
431. 12:16okay still still competing still
432. 12:17okay finally it returns
433. 12:21in the four model i
434. 12:24these three finished and then this is
435. 12:26still waiting for that first one that
436. 12:28first stalled guy is still stuck still
437. 12:30stuck on stuff okay now it finishes
438. 12:31and then sells 25 more to do but if i
439. 12:34broke into 100
440. 12:35it's like those other 24 things that are
441. 12:38now waiting because the first guy got
442. 12:40stuck
443. 12:41can be processed over here if i break it
444. 12:43into 100 pieces
445. 12:44only that one guy that gets stuck was
446. 12:46stalled there so you could actually
447. 12:48imagine
448. 12:49that it makes sense for a particular
449. 12:51problem to divide up into
450. 12:53more software threads than you have
451. 12:55hardware threads that's what i'm saying
452. 12:57it could just be that and i don't think
453. 12:58if i described that very well but the
454. 12:59idea is
455. 13:00you're just stalling with yourself and
456. 13:02the other 25 24
457. 13:04of the problem but in the other in my
458. 13:06world these guys are computing all those
459. 13:08guys and you're stuck on 100th over the
460. 13:09problem and then when that gets done
461. 13:10you're done
462. 13:11rather than have to then compute the
463. 13:12other 24 undone guys that's what i'm
464. 13:14trying to say and who knows what's
465. 13:16happening in bad particular problem but
466. 13:17it could make sense to and there's a
467. 13:19little knob there's a no i have a
468. 13:20problem how
469. 13:21how much do i slice this up into for the
470. 13:23given amount of hardware threads i can
471. 13:24run it on a given amount of cores i have
472. 13:26given them out of machining them
473. 13:27dispatches two on the cloud
474. 13:29how much resolution how small a slice
475. 13:32should i do and so you
476. 13:33play with this curve and you play with
477. 13:35it and you see what the what the
478. 13:36knee and the curve is what the low point
479. 13:37of the curve is in terms of time okay
480. 13:40so point number one you get this
481. 13:42abstraction of software threads
482. 13:44okay you're gonna multiplex software
483. 13:46threads under hardware threads right the
484. 13:47idea
485. 13:48here's the pool and now you're gonna
486. 13:49grab some of them and pull them in here
487. 13:51pull them in pull them in work okay pull
488. 13:52it out put another one in you're gonna
489. 13:53try to get them all to be
490. 13:55matched in there um you could how do you
491. 13:58do that how do you bring them in and out
492. 13:59well
493. 14:00you can decide whenever you've got a
494. 14:02block thread you've got a cache miss
495. 14:04user input network access there's some
496. 14:06reason that thread is stalled for
497. 14:07whatever reason as we call that blocked
498. 14:09it could be a lot of those things right
499. 14:10cache miss i've got to go to command
500. 14:11it's a thousand cycles well
501. 14:13get that guy out of here while you're
502. 14:14going to sacramento make that kind of a
503. 14:15request that goes out there
504. 14:16pull it out and then bring somebody else
505. 14:18in to get some work done while the
506. 14:19sacramento returned it and maybe it's
507. 14:20even farther than sacramento maybe now
508. 14:22you know a virtual memory and maybe i
509. 14:23need to go to disk maybe it means a page
510. 14:25miss
511. 14:25oh my gosh how many is that a million
512. 14:28clock cycles for a page miss
513. 14:29possibly so get this guy out while it's
514. 14:32waiting on it while that's happening
515. 14:34do all the work okay you could also have
516. 14:36a timer like a little time slice so you
517. 14:38say
518. 14:38well okay they're all fine no cache
519. 14:40misses let's say i'm all doing you know
520. 14:41just
521. 14:42ads and r type instructions adds and
522. 14:44subtracts and xor it's just simple stuff
523. 14:45not even a memory access just just i'm
524. 14:47computing i'm like raw compute mode well
525. 14:50give some other give give some other
526. 14:51people a chance get some love to other
527. 14:52people so let some other people so maybe
528. 14:54slice out
529. 14:54after a couple of timers so you can
530. 14:56multiplex them in different ways
531. 14:59how do you remove it how do you remove a
532. 15:00software thread from a hardware thread
533. 15:02um so it's so here we go how do i take
534. 15:05it out how do i
535. 15:06unplug it and put it back in the kind of
536. 15:08waiting stage well i have to interrupt
537. 15:09execution i got to stop running i need
538. 15:11to save its state
539. 15:12i'm going to save its state so we did
540. 15:14this we did this we learned a little bit
541. 15:16in virtual memory how you
542. 15:17move things around uh for multiple
543. 15:19processes so you have to
544. 15:21save its register save its pc to memory
545. 15:24you got to pull it out save to memory
546. 15:25and now you've got it
547. 15:26okay so that's important um so i can
548. 15:28reinstate it so now all the things that
549. 15:30are part of that
550. 15:31part of that world of computation have
551. 15:33to be have to be saved and that's
552. 15:34obviously the registers in the pc
553. 15:37how do you do the same thing how do you
554. 15:38start a different software thread
555. 15:40how do you load that onto a hardware
556. 15:41thread well you go go to memory
557. 15:44grab its previously saved registers
558. 15:46until the hardware's registers
559. 15:47and you jump to its pc and you keep
560. 15:49going so basically registers in pc is
561. 15:50the piece
562. 15:51that's needed for these guys pull it out
563. 15:53pull it in pull it out pull it in and
564. 15:54you're doing this for
565. 15:55removing and adding different software
566. 15:57threads so here's an example very simple
567. 15:59i got a thread pool there's my pool of
568. 16:01threads
569. 16:02here's the list over here with a couple
570. 16:03of all the processes all the
571. 16:05threads i need to be to be running and
572. 16:08the os is going to map those threads
573. 16:10to the cores so that's the idea and
574. 16:12you're going to schedule that to make
575. 16:13that happen there are four cores
576. 16:15each core is actively running one
577. 16:17instruction stream at a time and that's
578. 16:18it so i've got this huge pool
579. 16:20and they're being mapped to the four
580. 16:22hardware threads if here i have only
581. 16:24one hardware thread per core and i'm
582. 16:26running on that and i'm just kind of
583. 16:27doing this until
584. 16:28until the program finishes or and by the
585. 16:30way you're seeing here many of these are
586. 16:31daemons many of these are programs that
587. 16:32just continue to run
588. 16:33if the if the name ends in a d as a the
589. 16:36list here you know user
590. 16:37s even user node d the d means daemon it
591. 16:40means it's running all the time
592. 16:42it doesn't stop it's not like well shoot
593. 16:44that was hard we're all done we're done
594. 16:45yet no
595. 16:46some of the programs never stop and so
596. 16:48the computer is always just processing
597. 16:49your computer
598. 16:50idle even you know even a computer
599. 16:52that's running anything like i'm just in
600. 16:54the
601. 16:54mac in the finder i'm just in the os
602. 16:56doing nothing i'm not running any
603. 16:57programs nothing's running but what
604. 16:58yes things are running it's listening
605. 17:00for hardware connections it's somebody's
606. 17:01running to be able to handle
607. 17:03like the keyboard that's your os uh
608. 17:06are there some network things there are
609. 17:07many things that are happening in the
610. 17:08background
611. 17:09who's up into the clock all those things
612. 17:10are running even though you don't
613. 17:11realize it as part of the os so
614. 17:13even if you're running no user programs
615. 17:15many things are running in your in your
616. 17:16system now you should check that out by
617. 17:18the way do i type ps minus
618. 17:19minus x and you'll see the list of all
619. 17:21the things running even when you're
620. 17:22running nothing else or maybe just run
621. 17:23terminal and then type that you'll see
622. 17:25wait i'm only running terminal
623. 17:26and there's a ton of things being run at
624. 17:27the same time okay all those are
625. 17:29processed
626. 17:30all that is complicated this is but the
627. 17:32nice thing is the os handles it for you
628. 17:34so far i haven't talked about it all
629. 17:35explicitly loading this thing in we even
630. 17:37talked about how to even split and fork
631. 17:38and join
632. 17:39fork myself and join it back we've done
633. 17:40any of that so we're just talking about
634. 17:41the big picture how about the oh
635. 17:43mostly we'll talk about what the os has
636. 17:44been doing all along and that's what's
637. 17:45happening all right
638. 17:46we're going to see how to make this work
639. 17:49we're getting lower and lower in the
640. 17:50abstraction level of being able to do
641. 17:51this ourself
642. 17:52explicitly you know touching some code
643. 17:54that actually splits this stuff and
644. 17:55joins it up
645. 17:56in a couple lectures all right we'll see
646. 17:57you there