[CS61C FA20] Lecture 32.6 - Flynn Taxonomy, SIMD Instructions: Matrix Multiply Example — Transcript
Full transcript
- 0:10Hello and welcome back to our
- 0:12parallelism module.
- 0:14So now we know how do SIMD
- 0:17extensions work, how they supported
- 0:20by the
- 0:22instruction set architecture, how they
- 0:24generally roughly implemented in
- 0:26hardware, and how do we use these
- 0:28instructions in assembly and perhaps as
- 0:32intrinsics in C.
- 0:34So let's take a look at one example that
- 0:37puts things together
- 0:39and uses the the SIMD instructions to
- 0:42perform
- 0:43matrix multiplication.
- 0:46So we have seen this matrix
- 0:48multiplication as a motivating example
- 0:50early on. This is a really tiny matrix.
- 0:51It has you know, it is multiplying only
- 0:54two by two matrices, two by two square
- 0:57matrices and produces another two by two
- 1:00square matrix.
- 1:01But I've circled these
- 1:04elements that we are working with in a
- 1:06little bit different way than I've done
- 1:08it before.
- 1:10Do want to highlight here that the way
- 1:14how data is organized
- 1:16in memory matters a lot.
- 1:19So be careful about that.
- 1:23We are assuming that the data is stored
- 1:26in the column format. So in this case
- 1:30A11
- 1:32is next to A21.
- 1:35They are neighbors in the column, so
- 1:37they should be stored next to each other
- 1:38in the memory.
- 1:40But generally in a
- 1:42larger matrix
- 1:44A11 is not going to be next to A 1 2.
- 1:51Okay.
- 1:53So let's see what do we need to do in
- 1:56order to perform a basically kind of a
- 1:59half of this or a quarter of a matrix
- 2:01multiplication? We'll use elements A11,
- 2:05A21,
- 2:0621 and multiply them in B11
- 2:10to get this
- 2:12um
- 2:13first two elements in C11 and C21.
- 2:19That's where the parallelism is going to
- 2:21come from.
- 2:22So,
- 2:24when we're doing matrix multiplication,
- 2:26we will first initialize the matrix. So,
- 2:29we'll set everything to zeros and then
- 2:31we're going to be adding these
- 2:34element-wise products to that running
- 2:36sum.
- 2:38So,
- 2:40in order to implement what I've just
- 2:42said, we need to do a couple of steps.
- 2:45First, we need to load these operands
- 2:48into the
- 2:51XMM registers.
- 2:53So, if A11 and A21 are next to each
- 2:59other, this is they're stored in a
- 3:00column order, they're going to be read
- 3:03in order.
- 3:05And they're going to be stored together
- 3:07as a
- 3:09packed double precision
- 3:12vector.
- 3:14Now, there is another instruction that
- 3:15enables us to essentially
- 3:18read the next operand, which by the way
- 3:20are not necessarily stored next to each
- 3:23other because B11 and your B matrix is
- 3:26also stored in a column order, these two
- 3:28elements B11 and B12 are not going to be
- 3:31next to each other. So, we can
- 3:34read both of those in two separate
- 3:36instructions and make two copies of
- 3:39that. There is a separate instruction,
- 3:41SSE instruction, that does that. So, we
- 3:44got things where they are supposed to
- 3:46be, we can go ahead and multiply them.
- 3:49But, we're actually going to perform
- 3:51multiply and addition. Typically, these
- 3:55SSE instructions or different kinds of
- 3:58vector instructions support something
- 4:00that is called a fused multiply add. So,
- 4:02they do
- 4:04multiplication and addition in
- 4:08one instruction.
- 4:10That instruction may take more than one
- 4:12cycle, um but it's, you know, like one
- 4:15take to do multiply add.
- 4:17Um
- 4:18so, in this case, um it is spelled out
- 4:21as um
- 4:24mmadd
- 4:25then with the contents over here of a
- 4:28multiple inside of it. So, that is
- 4:31essentially these two instructions one
- 4:33after another.
- 4:35Uh we'll first do parallel
- 4:36multiplication and then do parallel
- 4:38addition in XMM registers. So, as a
- 4:41result, in C1, we are going to have A11
- 4:45B11
- 4:47and then in the upper part of that
- 4:49register and in the lower part of the
- 4:51register, we're going to have A21 B11.
- 4:55Um essentially, this part over here.
- 5:01And then in uh um
- 5:04C2, we're going to have A11 B12 and A21
- 5:10B12.
- 5:11Then we continue. We get um the next few
- 5:15elements of this um
- 5:17matrix.
- 5:19Um
- 5:19Register A is going to get loaded uh
- 5:23with the next elements in the array. So,
- 5:25will be the registers B1 and B2. These
- 5:27are all just XMM registers. And we
- 5:32turn the crank one more time and
- 5:35we are done.
- 5:36Our registers, destination registers C1
- 5:39and C2, contain four elements of our
- 5:44double precision
- 5:45um result matrix.
- 5:48And that is it.
- 5:50That's essentially what is the how we
- 5:52can use these SIMD instructions
- 5:55to
- 5:57perform matrix multiplication multiple
- 5:59elements at a time.
- 6:05The code is shown here.
- 6:07Um I'm not going to walk through it. Um
- 6:09it is reasonably
- 6:12uh straightforward. Um it is shown as an
- 6:15example of using intrinsics in the C
- 6:18code. So, what you'll find out here is a
- 6:21mix of standard C code with the um
- 6:26with the intrinsics declarations and
- 6:30then uh intrinsic instructions.
- 6:34And that's it. It's a relatively quick
- 6:35code. It is worth
- 6:37walking through it and understanding
- 6:39exactly how does it implement what I've
- 6:41shown in the previous few slides.
- 6:45We're almost ready to wrap up our
- 6:47discussion about the SIMD architectures
- 6:51and uh their role in parallelism.
- 6:56First, I want to make a quick remark
- 6:58about RISC-V. We've been talking about
- 7:00RISC-V so far, but we had to switch over
- 7:04to Intel x86 extensions um
- 7:07for this module. Why is that? Well,
- 7:12there are RISC-V vector extension. There
- 7:16is a RISC-V vector extension that is in
- 7:18development. It is still in the draft.
- 7:20It is almost uh ready to go
- 7:24uh
- 7:25prime time.
- 7:27But, we can't have any hardware. There
- 7:29is no hardware that supports it, so we
- 7:31can't have projects and labs and so on.
- 7:34Give it a year or two, and RISC-V vector
- 7:36extensions will be there, and we can do
- 7:39everything in the RISC-V world. For now,
- 7:41we need to patch it up with Intel 686
- 7:46AVX and SSEs.
- 7:51Um
- 7:52what you'll find out, you know, please
- 7:54you can take a look if you like into the
- 7:56V extension draft. There is a whole
- 7:58bunch of instructions there as some 512
- 8:01wide vectors.
- 8:04In conclusion, we have
- 8:07examined
- 8:08Flynn's taxonomy of parallel
- 8:11architectures and we have paid attention
- 8:13generally in SIMD and MIMD
- 8:16architectures. And actually, what we
- 8:18have learned so far are the SIMD
- 8:20architectures.
- 8:22And we're going to revisit SIMD
- 8:24architectures when we take a look at
- 8:26GPUs a bit later in the course.
- 8:31And in the next few segments, we're
- 8:33going to take a look at MIMD
- 8:35instructions.
- 8:36We have also examined how this is
- 8:38implemented in case of Intel's AVX SIMD
- 8:43extension.
- 8:45And we can see that there is one
- 8:47instruction that can fetch and another
- 8:49instruction will operate on a vector of
- 8:51data or multiple operands
- 8:53simultaneously.
- 8:57And we have seen how we can use those,
- 8:58how we can directly access those as C
- 9:01intrinsics.
- 9:04That is it. It's time for a break and
- 9:07we'll continue with
- 9:10how do we work with multiple processors
- 9:13and multiple cores.
- 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.