[CS61C FA20] Lecture 32.1 - Flynn Taxonomy, SIMD Instructions: Parallelism — Transcript

Full transcript

1. 0:00[Music]
2. 0:10hey
3. 0:11hello long time no see welcome back to
4. 0:1461c
5. 0:15we are getting into a brand new module
6. 0:17this time we are talking about
7. 0:19parallelism so we are still continuing
8. 0:22our quest to make
9. 0:23a better computer and to run our
10. 0:27applications faster so we have learned
11. 0:29some of the software techniques that are
12. 0:31helping us with that but
13. 0:33we spend most of the time trying to
14. 0:35build a better computer understand the
15. 0:36principles how these better computers
16. 0:38are built
17. 0:39one of those principles is
18. 0:43the use of parallelism and we have
19. 0:45encountered parallelism
20. 0:46already we have encountered
21. 0:50multi-programming as a way to better
22. 0:51utilize a processor
23. 0:54um while it's waiting for data to come
24. 0:58from dram we can perform some other
25. 1:01tasks
26. 1:03we have seen pipelining
27. 1:06as a way to increase the performance by
28. 1:09having by
29. 1:10working on multiple instructions at the
30. 1:12same time
31. 1:13in in the pipeline and that was the
32. 1:16primary way how
33. 1:17people tried to increase performance of
34. 1:20processors in
35. 1:21say the 90s up to early 2000s
36. 1:26we kept building deeper and deeper
37. 1:28deeper pipelines and simultaneously use
38. 1:30that to
39. 1:31crank up the clock frequencies
40. 1:34but as a result the power kept shooting
41. 1:37up
42. 1:37in every processor generation and that
43. 1:40was not sustainable
44. 1:41we had to do something different
45. 1:46in order to stay under reasonable power
46. 1:49limits
47. 1:49people explore the dimension of using
48. 1:52parallelism and in this case
49. 1:54we are going to take a look at how do we
50. 1:58work
51. 1:59with parallel data what does that mean
52. 2:01simply
53. 2:03we often in our applications work
54. 2:06with some sorts of vectors and we can
55. 2:10perform vector additions in this case
56. 2:14in parallel if we have multiple units
57. 2:16that are capable
58. 2:18of adding multiple multiple
59. 2:21elements of a vector at the same time
60. 2:25there are many opportunities for for
61. 2:27data parallelism out there
62. 2:28one of them we have already encountered
63. 2:31and it is one
64. 2:32of the most popular workloads nowadays
65. 2:35which is machine learning and inference
66. 2:38in
67. 2:38machine learning inference we often
68. 2:41start with
69. 2:42something and we would like to perform
70. 2:45classification
71. 2:46in this case you know we can start with
72. 2:49an image of a cat and would like
73. 2:51to say that's a cat and not a dog the
74. 2:54way how we do that
75. 2:56is by going through multiple layers of
76. 3:00um classification pitch restriction here
77. 3:05that in their essence are
78. 3:09fairly parallel they could be
79. 3:12convolutions
80. 3:13matrix of vector multiplications or
81. 3:15matrix matrix multiplications and after
82. 3:18a sequence
83. 3:19of those classification steps we can say
84. 3:22that this image
85. 3:23that there's a cat in this image and not
86. 3:25a dog and
87. 3:27in turn if we feed to our neural network
88. 3:30an image of a dog it'll tell us it's a
89. 3:32dog if we
90. 3:34feed hand written numbers
91. 3:37they'll be able to tell us whether that
92. 3:38number is an eight or a nine
93. 3:44there is parallelism here both
94. 3:48within each layer but also we can
95. 3:51process multiple layers
96. 3:52concurrently we have introduced matrix
97. 3:56multiplication
98. 3:57matrix multiplication is not just common
99. 4:00in
100. 4:00in neural nets it's one of the
101. 4:04most common operations that will
102. 4:06encounter in
103. 4:08engineering data science
104. 4:11and many other application domains
105. 4:14generally we'll find it in
106. 4:16image filtering or blurring or noise
107. 4:19reduction
108. 4:20and many of the machine learning kernels
109. 4:23[Music]
110. 4:25but it's not a modern type of
111. 4:29workload i mean it has been so prevalent
112. 4:31engineering that it has been supported
113. 4:33in
114. 4:34languages since long time ago for
115. 4:37example there was a language one of the
116. 4:39first languages that i've learned as a
117. 4:41student was something that is called
118. 4:43fortran um you guys might not have even
119. 4:46heard of a fortran
120. 4:47um tell us something a little bit about
121. 4:50my age
122. 4:51um fortran was a common
123. 4:54language for um engineering applications
124. 4:59in the past up to probably early 2000s
125. 5:02um when it was
126. 5:06basically uh replaced in in
127. 5:09most of the domains by c it took see a
128. 5:12while to
129. 5:13to displace fortran legacy fortran from
130. 5:16everywhere um in the world um
131. 5:19so in fortran there was this instruction
132. 5:22which was d
133. 5:23gem and d gem is a double precision
134. 5:25floating point matrix multiplication
135. 5:28so it was as prevalent
136. 5:31or as important that it needed its own
137. 5:36instruction
138. 5:38just to quickly recap our matrices
139. 5:40because it will be helpful
140. 5:42um in understanding how we work on them
141. 5:45a bit later
142. 5:46you know here is an example of a square
143. 5:49matrix with
144. 5:50i rows and j columns
145. 5:54important thing to keep in mind is we
146. 5:56generally can't
147. 5:57store this matrix as like a square
148. 6:00matrix in a memory
149. 6:01or in or on a disk
150. 6:04it is generally stored sequentially
151. 6:08so we have a choice here whether we
152. 6:09would like to store it by
153. 6:12serially by rows or columns
154. 6:16generally it is serialized by columns so
155. 6:20in this case the first element in the
156. 6:22matrix a 0 0 will be followed by
157. 6:25the second element in that column
158. 6:28a 1 0 and then we will store them all
159. 6:33up to a n minus 1 0
160. 6:36and then we would continue with the
161. 6:38second column
162. 6:39a 0 1 store all of them up to
163. 6:43a n minus 1.
164. 6:47one and so on all right
165. 6:51and what does the matrix multiplication
166. 6:53do
167. 6:54well it's if we say that we would like
168. 6:56to multiply
169. 6:57two matrices a and b and sort a result
170. 6:59in a c what we are essentially doing
171. 7:02we are performing an iterative process
172. 7:06that computes elements of a resulting
173. 7:09matrix c i
174. 7:10j as sums of pairwise
175. 7:13products a i k
176. 7:17and b k j the inner coefficient k
177. 7:21is the same and that basically means
178. 7:24that
179. 7:25the number of columns in matrix a has to
180. 7:28be the same as the number of rows in
181. 7:30matrix b
182. 7:32that's the only way how the matrix
183. 7:33multiplication is valid so we would like
184. 7:35to find this element
185. 7:38c i j we would perform
186. 7:41pairwise multiplication of all the
187. 7:44elements in
188. 7:45row i with all the elements
189. 7:49in column b
190. 7:52and sum them together to get the element
191. 7:54c i
192. 7:55j notice that all these
193. 7:58multiplications of elements a i k
194. 8:02and b k j can be performed concurrently
195. 8:06and then we will just add them together
196. 8:09so we're going to look a little bit more
197. 8:11into that after a
198. 8:13quick break