[CS61C FA20] Lecture 32.2 - Flynn Taxonomy, SIMD Instructions: Matrix Multiplication — Transcript

Full transcript

1. 0:00[Music]
2. 0:10hi welcome back to our paralysis module
3. 0:13before we introduce the ways how we
4. 0:16actually accomplish
5. 0:17parallel operation let's try to
6. 0:19establish a baseline and our baseline
7. 0:21will be some common kernel executed
8. 0:24on a sequential machine
9. 0:27that we have studied so far by using
10. 0:30programming techniques
11. 0:32that are familiar to us so let's start
12. 0:35with matrix multiplication we have seen
13. 0:36matrix multiplication
14. 0:38uh to get a matrix c which is a product
15. 0:41of two matrices a and b we
16. 0:44would walk through over the elements
17. 0:48in that matrix c over all the rows
18. 0:51and columns to find the elements c
19. 0:54i j and they're going to be
20. 0:58element-wise products or corresponding
21. 1:01rows
22. 1:01and columns in matrices a and b so for
23. 1:05example to find an element c
24. 1:071 1 in this matrix that would be
25. 1:11a product of a 1 1 b
26. 1:141 1 plus a 1 2
27. 1:17b 2 1. when we plug in the numbers for
28. 1:20the
29. 1:23sample matrix down here that would be
30. 1:25equal to
31. 1:271 times 1 plus 0 times 2
32. 1:30equals to 1. and so on we continue doing
33. 1:34that
34. 1:35over the all the elements i
35. 1:38j in the matrix c when we write a
36. 1:41program this is essentially
37. 1:43a triple loop we are going to walk over
38. 1:47all the elements i j and k
39. 1:50in three loops let's take a look at the
40. 1:53implementation
41. 1:54in a familiar language like python so
42. 1:57matrix multiplication in python
43. 1:59essentially influence those three loops
44. 2:01we go over the
45. 2:03coefficients we want coefficients i and
46. 2:06j
47. 2:07within their range in this case these
48. 2:09are square matrices
49. 2:10we initialize each of the values
50. 2:14for the elements c i j
51. 2:18to zero and then we accumulate you know
52. 2:21in the inner loop we accumulate
53. 2:25a times b from corresponding places
54. 2:29in matrices a and b
55. 2:33when we try to time that we can find
56. 2:36out that the result is fairly
57. 2:38independent on the
58. 2:39size of the matrix we get about
59. 2:435 mega flops
60. 2:46what are mega flops well it's a measure
61. 2:48of
62. 2:49how fast is our computational throughput
63. 2:52you'll often hear people referring to
64. 2:55megaflops
65. 2:56and that stands for millions of floating
66. 2:58point operations per second
67. 3:00now each of the floating point
68. 3:02operations here that we encounter
69. 3:05is counted separately so we are going to
70. 3:07see a floating point add
71. 3:08and a floating point malt so each add
72. 3:11and each mult
73. 3:12are going to be two separate
74. 3:16floating point operations so
75. 3:19there is one floating point operation
76. 3:22that corresponds to multiplication
77. 3:25and one floating point operation that
78. 3:28corresponds to addition so
79. 3:30this line of code is two flops
80. 3:33so um when you take a look at this
81. 3:37then therefore since this is a triple
82. 3:38loop or square matrices of each other
83. 3:41size n
84. 3:42so it takes n cubed flops times two
85. 3:45because in within each iteration
86. 3:48we have two floating point operations
87. 3:53now is this fast
88. 3:56or slow it's kind of hard to tell i mean
89. 3:59we really haven't discussed that
90. 4:01so far so let's take a look at a second
91. 4:03example let's see how do we implement
92. 4:05this
93. 4:06in c language well there is not much
94. 4:08difference
95. 4:09in c we are going to have a scalar
96. 4:13which is our sequential uh kind of an
97. 4:16operation so here is our djm scalar
98. 4:19baseline
99. 4:20it's a triple loop element gets in an
100. 4:22element gets
101. 4:23initialized and we accumulate uh
102. 4:28a times b products to it
103. 4:32how long does that take to do well you
104. 4:35can actually run this experiment
105. 4:37there is a standard library time dot h
106. 4:39that exists in c
107. 4:40that we can invoke and what we can get
108. 4:42from that we can get
109. 4:44clock so we can get a
110. 4:47clock cycle when we start running this
111. 4:52matrix multiplication and we can get
112. 4:54then
113. 4:55clock that corresponds to the end
114. 4:58of execution of a problem and if we run
115. 5:01the program
116. 5:02we call djem as a function in between
117. 5:04we're going to get the number of clock
118. 5:05cycles
119. 5:06that it takes us to execute if we divide
120. 5:08that by the number of clocks per second
121. 5:11we get the speed of our matrix
122. 5:14multiplication
123. 5:15so if we repeat that versus python
124. 5:18and compare it to python this is what we
125. 5:19get and numbers here
126. 5:23of how many flops do we get
127. 5:26is actually in gigaflops not in
128. 5:30megaflops it's in gigaflops so billions
129. 5:32of floating point operations per second
130. 5:35compared to megaflops that we have seen
131. 5:38in with with the python
132. 5:42um and
133. 5:46we see something kind of surprising this
134. 5:49is
135. 5:49way faster you know code running in c
136. 5:52is way faster than code running in in
137. 5:56python it's not just a low light it's
138. 5:59like 240 times faster
139. 6:01that's crazy
140. 6:07yeah you should feel good about yourself
141. 6:09now we you know see
142. 6:10and you know how to do these things that
143. 6:13correspond to performance programming
144. 6:15that's a kind of a big deal
145. 6:19uh and you can think about you can start
146. 6:20appreciating 61c even more than you are
147. 6:22appreciating so far
148. 6:24because there is no other class that
149. 6:25gives you um 240 boost
150. 6:29240x boost in in your um
151. 6:33performance programming skills
152. 6:36there is one another interesting thing
153. 6:38here that we see
154. 6:40is that the performance in the numbers
155. 6:44of gigaflops is
156. 6:46constant until we get to a certain size
157. 6:49of a
158. 6:49matrix and then it drops
159. 6:55what do you think where does that come
160. 6:56from
161. 6:59it has highly likely to do something
162. 7:02with the cache size some of these things
163. 7:04may not be fitting
164. 7:06in the cache some of these matrices may
165. 7:08not be fitting in the cache
166. 7:12so this is great we improved the
167. 7:14performance
168. 7:15by 240x but you don't want to stop here
169. 7:18we are going to make this matrix
170. 7:20multiplication go faster and faster
171. 7:23throughout this module so we're going to
172. 7:26take a little break
173. 7:28and then talk a little bit about how do
174. 7:31we
175. 7:32classify these different types of
176. 7:34parallelism
177. 7:36see you after a break