[CS61C FA20] Lecture 32.3 - Flynn Taxonomy, SIMD Instructions: Flynn's Taxonomy — Transcript

Full transcript

1. 0:00[Music]
2. 0:09welcome back to our policy module
3. 0:12so far we have explored the performance
4. 0:14of our baseline application
5. 0:16which was the matrix multiplication we
6. 0:19have compared
7. 0:20the throughput that we get for matrix
8. 0:22multiplication when it's written in
9. 0:23python
10. 0:24versus c and we have seen the c is
11. 0:26significantly faster
12. 0:27than python the reason for that is
13. 0:30python is a productivity language
14. 0:32and it is interpreted so it is
15. 0:35easier to write code in python
16. 0:39but at the cost of performance
17. 0:42interpreted means that it is not
18. 0:44directly compiled there is something
19. 0:46that
20. 0:47comes in the way of executing every
21. 0:50single one of these instructions and
22. 0:52adds a bunch of other assembly
23. 0:53instructions that need to be executed
24. 0:55on the other hand c is compiled and
25. 0:57compiles directly into the assembly and
26. 0:59is much more
27. 1:01efficient can we be more efficient in
28. 1:03writing
29. 1:04um sequential c code on
30. 1:07a processor on a on a serial processor
31. 1:10like the ones that we have
32. 1:12examined so far yeah perhaps
33. 1:15we can write assembly code and do better
34. 1:18but in general compilers are pretty good
35. 1:21nowadays
36. 1:22it's not that easy to to beat them but
37. 1:24still there is a chance
38. 1:26um the other way how we can get speed
39. 1:28ups is by
40. 1:29trying to address that bottom um slow
41. 1:32down that
42. 1:33when we are working with the with larger
43. 1:35matrices
44. 1:38and but we can do that
45. 1:42either in c or in assembly by using
46. 1:45so-called blocking techniques
47. 1:46and we might see them a bit later on
48. 1:50in this module
49. 1:54now how can we do actually faster
50. 1:57well we can do things faster by using
51. 2:00parallelism
52. 2:01and one of the goals of parallelism is
53. 2:05to essentially do the entire or
54. 2:09most of that inner loop of matrix
55. 2:11multiplication
56. 2:13concurrently by having hardware that can
57. 2:16do multiple multiplications
58. 2:19at the same time but before we get into
59. 2:22that
60. 2:22let's take a look at different types of
61. 2:24parallel hardware the
62. 2:26that we can encounter so first there is
63. 2:30an
64. 2:30important thing to distinguish in
65. 2:32parallelism between
66. 2:33software and hardware they're generally
67. 2:37orthogonal to each other so
68. 2:38this table is picked straight from the
69. 2:40book that compares
70. 2:42an older processor that is strictly
71. 2:45serial which was intel pentium 4 and
72. 2:48then there is a modern processor more
73. 2:50modern processor intel core i7
74. 2:52that has parallel features in it so
75. 2:55you know the same type of a code can be
76. 2:58run on a
77. 2:59serial processor or on a parallel
78. 3:01processor
79. 3:02and the speed up that we are going to do
80. 3:05to
81. 3:06to get is perhaps from using some of
82. 3:09these
83. 3:10um you know doing some of the inner
84. 3:13loop concurrently now software can be
85. 3:15running
86. 3:16sequentially like our matrix
87. 3:18multiplication
88. 3:19regardless of what type of uh of a
89. 3:21hardware we are running
90. 3:23on or concurrently like our operating
91. 3:25system now this is an operating system
92. 3:27in this example is vista you might not
93. 3:31even know what
94. 3:32is uh vista it's an operating system
95. 3:34that predates
96. 3:35um windows 7 or
97. 3:39windows 10 windows 7 and somewhere out
98. 3:41there
99. 3:42around windows xp there was
100. 3:46vista as well what we have seen
101. 3:49we use multi-programming to run multiple
102. 3:52processes
103. 3:54what it looks like concurrently even
104. 3:56though
105. 3:57we are running it on serial hardware
106. 4:01so choice of hardware and software
107. 4:04parallelism
108. 4:06are generally independent concurrent
109. 4:08software can
110. 4:09run on serial hardware sequential
111. 4:11software can run on parallel hardware
112. 4:15[Music]
113. 4:16flint's taxonomy which is what your
114. 4:18address next is
115. 4:20essentially a classification of parallel
116. 4:22hardware so let's take a look at that
117. 4:24this is named after professor
118. 4:28michael flynn who is a professor
119. 4:30emeritus at stanford
120. 4:31university so he has
121. 4:35classified different types of
122. 4:37parallelism between
123. 4:39the parallelism in data streams and
124. 4:41instruction streams
125. 4:43so there are four entries in this table
126. 4:47that correspond to single instruction
127. 4:50single data single instruction multiple
128. 4:53data
129. 4:54multiple instructions single data and
130. 4:56multiple instructions multiple data
131. 4:59let's take a quickly uh a look at those
132. 5:02what we have encountered so far
133. 5:04everything was single instruction single
134. 5:06data
135. 5:07that's how our single core sequential
136. 5:09processors operated
137. 5:12most of what we are going to be talking
138. 5:14about in this module are
139. 5:16simdi and mimdi architectures simdes
140. 5:19single instruction multiple data
141. 5:21mimds multiple instructions multiple
142. 5:23data
143. 5:25however most of the programs that you'll
144. 5:27find nowadays
145. 5:29are kind of a combination of that and
146. 5:30they can be called single program
147. 5:32multiple data and the idea there is that
148. 5:36we're going to run a single program that
149. 5:38is going to try to use multiple degrees
150. 5:40of parallelism
151. 5:41so it will be running of all the
152. 5:43processors
153. 5:44that have
154. 5:48memdi multiple instructions and multiple
155. 5:50data and there will be some cross
156. 5:52processor
157. 5:53coordination that we are going to see a
158. 5:56bit later in this module
159. 5:59cindy is a particular type of processors
160. 6:02that
161. 6:03has specialized hardware that
162. 6:06can run multiple
163. 6:10can operate on multiple data at the same
164. 6:13time
165. 6:13in so-called lock step
166. 6:18fashion and that is very good for
167. 6:22running these
168. 6:25arrays so it can basically crank
169. 6:29through one dimension of the array in
170. 6:31one instruction
171. 6:32and that's very useful not just for
172. 6:33neural nets imaging but many of the
173. 6:35scientific
174. 6:36applications okay
175. 6:39so let's quickly walk through all four
176. 6:42entries that we have in this table
177. 6:45first is the one that we have seen
178. 6:47already seen so far
179. 6:49this is the single instruction single
180. 6:50data or system
181. 6:52so there is a sequential processor that
182. 6:54basically sequences
183. 6:56through the instruction pool and
184. 6:59matches it with the data that
185. 7:02is in the memory and processes it one at
186. 7:04a time
187. 7:06so it's our traditional uniprocessor
188. 7:09the second in class is simdi
189. 7:14simdi is a type of computer that has
190. 7:16multiple processing units
191. 7:18these pu's are the processing units and
192. 7:23it will essentially issue one
193. 7:26instruction
194. 7:27say add and it will operate on
195. 7:31multiple data pairs at the same time in
196. 7:33this case there would be
197. 7:35four processing units
198. 7:38that would be capable of doing four
199. 7:40additions
200. 7:42you know for for each add instruction so
201. 7:45it would be
202. 7:46essentially adding formal element vector
203. 7:49to another
204. 7:50for element vector then
205. 7:53there is the third type that we
206. 7:57see here which is mindy which are
207. 8:00multiple instructions
208. 8:01multiple data streams so we would be
209. 8:04running
210. 8:04multiple issuing multiple instructions
211. 8:06at the same time that
212. 8:08each one would be operating on multiple
213. 8:11data
214. 8:13this is generally not just one processor
215. 8:16that does that this is generally a
216. 8:20concept of multiple processors
217. 8:22where each one of them is assembly
218. 8:23processor that are operating
219. 8:25concurrently
220. 8:26so each processor issues its own
221. 8:28instruction that
222. 8:29runs on multiple data so these mending
223. 8:33architectures are going to be again
224. 8:35covered a little bit later in this
225. 8:37module
226. 8:37that involve multi-core processors and
227. 8:40data centers or what we are going to
228. 8:42call warehouse scale computers where
229. 8:44there are many computers that
230. 8:47are housed in the same building and
231. 8:50finally
232. 8:51the fourth entry in that table table is
233. 8:53multiple instruction
234. 8:55single data stream misty well that
235. 8:59is not something that we really
236. 9:01encounter nowadays and it's not
237. 9:03something that we
238. 9:03really need this is a concept of you
239. 9:06know having the same
240. 9:08set of data you know and
241. 9:11then doing multiple things to that so
242. 9:13it's like
243. 9:14whether you're like would you like your
244. 9:17eggs scrambled
245. 9:19or sunny side up only say both
246. 9:22so it does not always
247. 9:26makes you know it is not something that
248. 9:28we will
249. 9:29frequently encounter as we want to do
250. 9:31two different operations
251. 9:32on the same data
252. 9:37that's it for now we are going to dive
253. 9:40next through the rest of this
254. 9:43segment into simdi architectures but
255. 9:47just after a quick break