[CS61C FA20] Lecture 32.6 - Flynn Taxonomy, SIMD Instructions: Matrix Multiply Example — Transcript

Full transcript

1. 0:00[Music]
2. 0:10hello
3. 0:11and welcome back to our parallelism
4. 0:12module
5. 0:14so now we know how do seamless
6. 0:17extensions work how are they supported
7. 0:21by the instruction set architecture are
8. 0:24they
9. 0:24generally roughly implemented in
10. 0:26hardware and how do we use these
11. 0:28instructions in
12. 0:29assembly and perhaps as in 36
13. 0:32and c so let's take a look at one
14. 0:36example
15. 0:36that puts things together and uses
16. 0:40the the similar instructions to perform
17. 0:43matrix multiplication so
18. 0:47we have seen this matrix multiplication
19. 0:48as a motivating example early on this is
20. 0:50a really tiny matrix it has
21. 0:53you know it is multiplying only two by
22. 0:55two matrices
23. 0:56two by two square matrices and produces
24. 0:58another
25. 0:59two by two square matrix but
26. 1:02i've circled these elements that we are
27. 1:05working with in a little bit different
28. 1:07way
29. 1:07than i've done it before i
30. 1:10do want to highlight here that the
31. 1:14way how data is organized in memory
32. 1:17matters a lot so be careful about that
33. 1:22we're assuming that the data is stored
34. 1:26in the column format so
35. 1:29in this case a11
36. 1:32is next to a21 they are neighbors in the
37. 1:36column
38. 1:36so they should be stored next to each
39. 1:38other in the memory
40. 1:40but generally in a larger matrix
41. 1:44a11 is not going to be next to
42. 1:47a 1 2.
43. 1:51okay so
44. 1:54let's see what do we need to do in order
45. 1:56to
46. 1:57perform a basically kind of a half of
47. 2:00this or a quarter of a matrix
48. 2:01multiplication
49. 2:02we'll use elements a 1 1 a 2 1
50. 2:062 1 and multiply them in b 1
51. 2:091 to get this
52. 2:13first two elements in
53. 2:16c 1 1 and c 2 1.
54. 2:19that's where the parallelism is going to
55. 2:21come from
56. 2:22so when we are doing matrix
57. 2:25multiplication
58. 2:26we will first initialize the matrix so
59. 2:29we'll set everything to zeros
60. 2:31and then we're going to be adding these
61. 2:34element-wise products to that running
62. 2:36sum
63. 2:38so uh in order to implement what i've
64. 2:42just said
65. 2:43we need to do a couple of steps first we
66. 2:46need to
67. 2:46load these operands into
68. 2:50the xmm registers
69. 2:53so if a11 and a21
70. 2:57are next to each other this is they're
71. 3:00stored in a column order
72. 3:01they're going to be read in order
73. 3:05and they're going to be stored together
74. 3:07as a
75. 3:09packed double precision vector
76. 3:14now there is another instruction that
77. 3:16enables us to essentially
78. 3:18read the next operand which by the way
79. 3:20are not necessarily
80. 3:22stored next to each other because b11 if
81. 3:25your b matrix is also stored in a
82. 3:27column order these two elements b 1 1
83. 3:30and b 1 2
84. 3:30are not going to be next to each other
85. 3:32so we can
86. 3:34read both of those in two separate
87. 3:36instructions
88. 3:38and make two copies of that there is a
89. 3:40separate instruction
90. 3:41ssc instruction that does that so we got
91. 3:44things where they
92. 3:45are supposed to be we can go ahead and
93. 3:48multiply them
94. 3:49but we're actually going to perform
95. 3:51multiply
96. 3:53and addition typically these ssc
97. 3:56instructions or different kinds of
98. 3:58vector instructions support something
99. 4:00that is called the fuse multiply add
100. 4:02so they do multiplication and addition
101. 4:06in one instruction
102. 4:10that instruction may take more than one
103. 4:12cycle but
104. 4:14it's you know like one take to do
105. 4:15multiply add
106. 4:18so in this case it is spelled out as
107. 4:24mm add then with the contents over here
108. 4:28of a multiple inside of it so that is
109. 4:31essentially these two instructions one
110. 4:33after another
111. 4:34uh we'll first do parallel
112. 4:36multiplication and then do parallel
113. 4:38addition
114. 4:39in xmm registers so as a result in c1 we
115. 4:42are going to
116. 4:43have a 1 1 b 1 1
117. 4:47and then in the upper part of that
118. 4:49register and in the lower part of the
119. 4:50register we're going to have a 2 1
120. 4:53b 1 1.
121. 4:56essentially this part over here
122. 5:00and then in
123. 5:04c2 we're going to have a11 b12
124. 5:08and 2 1 b 1 2.
125. 5:11then we continue we get the next
126. 5:15few elements of this matrix
127. 5:19register a is going to get loaded
128. 5:23with the next elements in the array so
129. 5:25will be the registers b1 and b2
130. 5:27these are all just xmm registers and
131. 5:30we turn the crank one more time
132. 5:34and we are done our
133. 5:37registers destination register c1 and c2
134. 5:40contain four elements of our
135. 5:44double precision result
136. 5:47matrix and that is it
137. 5:50that's essentially what is the you know
138. 5:52how we can use these
139. 5:53simply instructions to perform matrix
140. 5:57multiplication
141. 5:59multiple elements at a time
142. 6:05a code is shown here um i'm not going to
143. 6:08walk through it
144. 6:09it is reasonably uh straightforward
145. 6:14it is shown as an example of using
146. 6:16intrinsics
147. 6:17in the c code so what you'll find out
148. 6:20here is a
149. 6:21mix of standard c code with
150. 6:24the with the
151. 6:28intrinsic declarations and then
152. 6:31intrinsic instructions and that's it
153. 6:34it's a relatively quick code
154. 6:36it is worth walking through it and
155. 6:38understanding exactly how does it
156. 6:40implement what i've shown in the
157. 6:41previous few slides
158. 6:45we're almost ready to wrap up our
159. 6:47discussion about
160. 6:49the sim cindy architectures and
161. 6:52their role in parallelism
162. 6:56first i want to make a quick remark
163. 6:58about risk five we've been talking about
164. 7:00risk five so far
165. 7:01but we had to switch over to intel
166. 7:04x86 extensions um for
167. 7:08this module why is that well
168. 7:12there are risk five vector extension
169. 7:16there is a risk 5 vector extension that
170. 7:18is in development is still
171. 7:19in the draft it is almost ready to go
172. 7:25prime time but
173. 7:28we can't have any hardware there is no
174. 7:30hardware that supports it so we can't
175. 7:31have
176. 7:32projects and labs and so on give it a
177. 7:34year or two
178. 7:35and risk five vector extensions will be
179. 7:37there and we can do
180. 7:39everything in the risk live world for
181. 7:41now we need to
182. 7:42patch it up with the intel 686
183. 7:46avx and sscs
184. 7:52what you'll find out you know please you
185. 7:54can take a look
186. 7:55if you like into the v extension draft
187. 7:57there is a whole bunch of instructions
188. 7:59there assumes 512
189. 8:01wide vectors
190. 8:04in conclusion we have the examined
191. 8:08uh flint's taxonomy of parallel
192. 8:11architectures and
193. 8:12we have paid attention generally in cmd
194. 8:14and memdi
195. 8:16architectures and actually what we have
196. 8:18learned so far
197. 8:20are the cmd architectures and
198. 8:23we are going to revisit sim the
199. 8:24architectures when we take a look at
200. 8:26gpus a bit later
201. 8:28in the course
202. 8:31and in the next few segments we're going
203. 8:33to take a look at
204. 8:34memdi instructions we'll also examine
205. 8:38how this is implemented in case of
206. 8:40intel's abx simdi extension
207. 8:45and we can see that there is one
208. 8:47instruction that can fetch
209. 8:48and another instruction will operate on
210. 8:51a vector of data
211. 8:52or multiple operands simultaneously
212. 8:56and we've seen how we can use those how
213. 8:58we can directly access those
214. 9:00as c intrinsics
215. 9:04that is it it's time for a break
216. 9:07we'll continue with how do we work
217. 9:11with multiple processors in multiple
218. 9:14cores
219. 9:15see you later