04 02 Threads and Concurrency Part 2 — Transcript

Full transcript

1. 0:08[Music]
2. 0:21okay so next would be
3. 0:24the multi-core programming
4. 0:26okay so for application programmers
5. 0:29there are five areas where a multi-core
6. 0:32chips
7. 0:33present new challenges
8. 0:36okay
9. 0:37so
10. 0:38these are identifying the tasks
11. 0:40okay
12. 0:41balance
13. 0:43you've got data splitting
14. 0:46data dependency testing and debugging so
15. 0:49let's start with dividing activities or
16. 0:51identifying tasks
17. 0:53so this means examining application to
18. 0:55find activities that can be performed
19. 0:57concurrently
20. 0:59okay
21. 1:00when you say balance finding tasks to
22. 1:02run concurrently
23. 1:04that provide equal value example don't
24. 1:07waste a tread on a trivial tasks
25. 1:10all right
26. 1:11so next would be data splitting
27. 1:14so to prevent the threads from
28. 1:16interfering with one another so we have
29. 1:18to perform data splitting
30. 1:22next is
31. 1:24data dependency okay so when you say
32. 1:27data dependency if one task is dependent
33. 1:30upon the result of another
34. 1:33then the task needs to be synchronized
35. 1:35to assure
36. 1:36access in proper
37. 1:38order okay and last would be testing and
38. 1:42debugging so inherently more difficult
39. 1:44in parallel processing a situation
40. 1:47as the race conditions that we mentioned
41. 1:49on the processes
42. 1:51become much more complex and difficult
43. 1:53to identify
44. 1:55okay
45. 1:56now in a multi-core programming so we
46. 1:59will be
47. 2:01encountering terms of parallelism and
48. 2:02concurrency
49. 2:04okay now what's the difference between
50. 2:05these two so by definition when you say
51. 2:08parallelism it implies a system can
52. 2:10perform more than one task
53. 2:11simultaneously
54. 2:13okay
55. 2:14whereas concurrency
56. 2:17supports more than one task making
57. 2:19progress so single processor you've got
58. 2:22the core dual core multi-core octa-core
59. 2:25okay you've got the scheduler provided
60. 2:27concurrency
61. 2:30all right
62. 2:32okay
63. 2:33so
64. 2:35we mentioned earlier concurrency and
65. 2:37parallelism
66. 2:39okay
67. 2:40so a recent trend in computer
68. 2:42architecture is to produce tips with
69. 2:45multiple cores okay you've got dual
70. 2:48cores
71. 2:49quad core you've got octa-core all right
72. 2:52so
73. 2:54a multi-threaded application running on
74. 2:56a traditional single core chip
75. 2:58would have to be interleaved the threads
76. 3:01okay so as shown here so this is a
77. 3:04concurrent execution on a single core
78. 3:06system
79. 3:08okay
80. 3:09now on a multi-core chip however
81. 3:12the threads could be spread across
82. 3:14available
83. 3:15course so this is an example of a dual
84. 3:18core here
85. 3:19okay
86. 3:20and the threads are spread across
87. 3:24this available course here so t1 or
88. 3:26thread one thread two thread three and
89. 3:28thread four and so on so they are
90. 3:30distributed
91. 3:31among the available cores
92. 3:34okay so allowing through parallel
93. 3:36processing
94. 3:38okay so for operating systems multi-core
95. 3:41chips require new skeleton learning
96. 3:43algorithms so to make better use of the
97. 3:46multiple cores
98. 3:48available
99. 3:49so as multi trading becomes more
100. 3:51pervasive
101. 3:53and more important so thousands instead
102. 3:56of tens of threads okay cpus have been
103. 3:59developed to support more simultaneous
104. 4:01threads
105. 4:02per core in hardware so that means
106. 4:05with multi-core
107. 4:06okay so the performance is of course
108. 4:09faster than a single core
109. 4:12okay if you have a single core in the
110. 4:15dual core
111. 4:16okay so
112. 4:18compared so of course
113. 4:20you've got several tasks distributed in
114. 4:22a single cpu whereas in here the threads
115. 4:25are distributed on multiple cores
116. 4:28okay so that's faster of course
117. 4:31all right
118. 4:32so next would be
119. 4:35the types of parallelism
120. 4:37so in theory
121. 4:39there are two two different ways
122. 4:41to
123. 4:43parallelize the workload okay so these
124. 4:47are the data parallelism and the task
125. 4:49parallelism
126. 4:51okay so when you say data parallelism so
127. 4:54this divides the group up amongst
128. 4:56multiple cores or threads
129. 4:58and performs the same task for each
130. 5:01subset of the data so for example
131. 5:03dividing a large image into pieces and
132. 5:06performing the same digital image
133. 5:08processing on each piece
134. 5:10on a different core
135. 5:12all right so that is data parallelism
136. 5:16now when you say task parallelism
137. 5:18so dividing the task
138. 5:20to be performed among different cores
139. 5:22and perform them simultaneously so in
140. 5:25practice
141. 5:26no program is ever divided up solely by
142. 5:29one or other of this
143. 5:31but instead
144. 5:33some sort of hybrid combination
145. 5:37okay
146. 5:40okay so next would be
147. 5:44showing the data and task parallelism so
148. 5:46what's the difference between these two
149. 5:48as mentioned earlier
150. 5:49when you say data parallelism so
151. 5:52distribute subsets of the same data
152. 5:54across multiple cores
153. 5:57same operations on it
154. 5:59all right so when you say task
155. 6:01parallelism
156. 6:02distributing threads across course okay
157. 6:06each thread performing a unique
158. 6:09operation
159. 6:11all right
160. 6:14okay so next would be
161. 6:17the amdahl's law okay so what is this
162. 6:20amdahl's law so it identifies
163. 6:22performance gains from adding additional
164. 6:24cores on application that has both
165. 6:26serial and parallel components
166. 6:28so s is for serial portion and n is the
167. 6:32number or the processing course here
168. 6:35so this would compute this or this would
169. 6:37improve improve or speed up okay the
170. 6:40performance
171. 6:41that is if application is 75 parallel
172. 6:44and 25 serial so moving from one to two
173. 6:48course results in a speed up of 1.6
174. 6:50times actually it's not doubled all
175. 6:52right so it's not that if we are using a
176. 6:55single core
177. 6:56okay and we are using a dual core on the
178. 6:59other end so we cannot conclude that the
179. 7:03process has been doubled
180. 7:05okay
181. 7:06so to compute that speed up you'll have
182. 7:08this formula here
183. 7:10okay
184. 7:12so and
185. 7:13as mentioned here now
186. 7:15if the application is 75 parallel and 25
187. 7:18serial so moving from a single core to a
188. 7:22dual core results to the speed of 1.6
189. 7:25times only
190. 7:27all right so as n approaches infinity so
191. 7:30speed up approaches one over s here
192. 7:33okay
193. 7:34now the serial portion of the
194. 7:35application has this proportionate
195. 7:38effect on the performance gained by
196. 7:40adding additional course
197. 7:42okay
198. 7:45so this is what i stated on the
199. 7:48amdahl's law presented
200. 7:50in the previous slide
201. 7:52okay
202. 7:53so if you'll have here
203. 7:55this
204. 7:56on this x-axis you've got the number of
205. 8:00processing cores and on the y-axis
206. 8:03you've got to speed up
207. 8:04so if you are using a dual core so this
208. 8:07is something like 1.6 right based on the
209. 8:09computation
210. 8:10okay so if you are using a quad core of
211. 8:13course it's less than
212. 8:15times four
213. 8:16okay
214. 8:23all right
215. 8:24so next would be the user
216. 8:27and the kernel trends
217. 8:28okay so there are two types of threads
218. 8:31to be managed in a modern system and
219. 8:33these are of course the user threads and
220. 8:35the kernel threads all right so i say
221. 8:37user threads management done by user
222. 8:40level
223. 8:41okay
224. 8:42and kernel threads is supported by the
225. 8:44kernel okay
226. 8:46so for the user threads
227. 8:48so this includes the posix threads okay
228. 8:51which are used in linux okay
229. 8:54you also have this windows threads on
230. 8:57windows of course and java threads
231. 9:01now for the kernel threads
232. 9:03so
233. 9:04virtually all general purpose operating
234. 9:06system including windows
235. 9:09linux mac os ios and android this are
236. 9:12all under kernel threads
237. 9:17all right
238. 9:21okay
239. 9:22so
240. 9:23user threads are supported above the
241. 9:25kernel
242. 9:26okay so this is your kernel threads this
243. 9:28is your user threads so user threads are
244. 9:31supported above the kernel without
245. 9:33kernel support okay
246. 9:35so these are threads
247. 9:37that the application programmers would
248. 9:40put into their programs
249. 9:42and when you say kernel threads
250. 9:44kernel threads are supported within the
251. 9:47kernel of the os itself so all modern
252. 9:51oss support kernel level threads
253. 9:54allowing the kernel to perform multiple
254. 9:55simultaneous tasks
255. 9:58and or
256. 9:59to service multiple kernel system calls
257. 10:02simultaneously okay
258. 10:04now in a specific implementation
259. 10:07the user thread must be mapped to kernel
260. 10:10threads so using
261. 10:12one of the following strategies here
262. 10:16okay so there are three multi-threading
263. 10:20models and that includes
264. 10:23many to one one to one and many too many
265. 10:27okay so what's the difference between
266. 10:28these three here okay
267. 10:30so let's start with minutes one
268. 10:33okay so in the minute to one model many
269. 10:36user level threads all right
270. 10:39are mapped into a single kernel thread
271. 10:41here
272. 10:42okay so thread management is handled by
273. 10:45the thread library in the user space
274. 10:48okay
275. 10:50which is very efficient
276. 10:52so however
277. 10:54if a blocking system calls made
278. 10:59then the entire process blocks even if
279. 11:02the other user threads would otherwise
280. 11:05be able to continue
281. 11:08okay
282. 11:08so one chart blocking causes also black
283. 11:13now because a single thread or a single
284. 11:16kernel thread can operate only on a
285. 11:18single cpu
286. 11:19the many-to-one model does not allow
287. 11:21individual processes
288. 11:23to be split across multiple cpus
289. 11:29so
290. 11:29green threads
291. 11:32for solaris
292. 11:33okay
293. 11:35and
294. 11:36gnu portable threads implemented
295. 11:39the many to one model in the past but
296. 11:42few system continued to do so today
297. 11:45all right so the next one would be
298. 11:49one to one okay now with one to one
299. 11:52model it creates a separate kernel
300. 11:53thread to handle its user thread here so
301. 11:56there is
302. 11:58a corresponding user threads okay so for
303. 12:01every kernel threads here and vice versa
304. 12:03okay so one to one model overcomes the
305. 12:06problems listed above
306. 12:08involving blocking system calls and
307. 12:10splitting of processes across multiple
308. 12:12cpus
309. 12:13so however the overhead of managing
310. 12:16one-to-one model is more significant
311. 12:19involving the overhead
312. 12:22and okay the the slowing down of the
313. 12:25system
314. 12:26so most implementations of this model
315. 12:29place a limit on how many threads are
316. 12:31created
317. 12:33okay
318. 12:34so these are being implemented on
319. 12:37windows and linux
320. 12:41okay
321. 12:42so next would be
322. 12:46the many-to-many model
323. 12:48with many-to-many model
324. 12:50it multiplexes
325. 12:52any number of user threads
326. 12:54onto an equal or smaller number of
327. 12:58kernel threads so combining the best
328. 13:00feature of
329. 13:02one to one and many to one models
330. 13:05so users have no restrictions on the
331. 13:07number of threads created
332. 13:09okay
333. 13:10so black in kernel system calls do not
334. 13:12block the enter process so process can
335. 13:14be split into
336. 13:16or across multiple processors if you are
337. 13:18using multiple processors
338. 13:20and individual processes may be
339. 13:22allocated variable numbers of kernel
340. 13:24threads
341. 13:25depending on the number of cpus present
342. 13:28and other factors
343. 13:32right okay
344. 13:35so
345. 13:36how about this two level
346. 13:38okay how about this two level model so
347. 13:41what is this so the two level model
348. 13:44is a popular variation
349. 13:47of the many to many model
350. 13:51okay so which allows either many to many
351. 13:54or one-to-one operation
352. 13:57okay now this model
353. 14:00is being implemented on irix
354. 14:03hp ux and the true 64 unix
355. 14:06okay
356. 14:07as did with solaris prior to solaris 9.
357. 14:20[Music]
358. 14:28you