YouTube2Text

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

by CS 61C Departmental · 1,145 words · 210 segments · language en · Watch on YouTube

Full transcript

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

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 32.6 - Flynn Taxonomy, SIMD Instructions: Matrix Multiply Example by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 1,145 words across 210 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.