Lecture 18: SIMD Architectures

What this lecture covers

The lecture asks how hardware can exploit data parallelism, where the same operation is applied to many pieces of data at once, and why this pattern underlies GPUs, vector supercomputers and modern machine-learning accelerators. It opens by wrapping up the prior systolic-array material with real examples (Google's TPU, Cerebras' wafer-scale chip, Microsoft's BrainWave), then formally introduces SIMD (single instruction, multiple data) through Flynn's taxonomy before working through array processors and vector processors in detail.

This is part of the Digital Design and Computer Architecture course's sequence on execution paradigms, following out-of-order, VLIW and systolic-array designs and leading into GPU architectures in the next lecture. After watching, you should be able to classify a machine using Flynn's taxonomy, explain the space/time duality between array and vector processors, calculate the execution time of vectorized code given memory bank latency, and describe why memory bandwidth, not compute, is usually the bottleneck in SIMD systems.

Key ideas

• Flynn's taxonomy: computers are classified by how many instruction streams and data streams they use — SISD (scalar), SIMD (one instruction, many data), MISD (systolic arrays), and MIMD (multiprocessors).
• Array processor: uses many processing elements to perform the same operation on different data elements at the same time (parallel in space).
• Vector processor: uses one (or few) pipelined functional units and performs the same operation on data elements in consecutive cycles (parallel in time).
• Vector registers and stride: a vector register holds many elements; the stride is the memory distance between consecutive elements, and it determines whether loads can sustain one element per cycle.
• Memory banking: memory is split into independently accessible banks so that many loads or stores can be in flight at once; the number of banks must exceed the bank access latency to sustain full throughput.
• Vector chaining: forwarding a partial vector result directly to the next functional unit instead of waiting for the whole vector, which deepens the pipeline and cuts execution time substantially.
• Gather and scatter: indexed loads and stores that let a vector processor operate on data that is not laid out with a constant stride, useful for sparse matrices.
• Vector masking: a per-element predicate register (vmask) that lets some elements of a vector operation be skipped, implementing conditional (if) execution without branches.

Walkthrough

Finishing systolic arrays and real accelerators (4:40)

The lecture briefly reviews systolic arrays' advantages (high efficiency, good reuse of fetched data, regular design) and disadvantages (poor fit for irregular parallelism, hard to program), then shows how the idea persists in modern hardware: Google's TPU uses a systolic array for matrix multiplication, Cerebras builds a wafer-scale accelerator, and Microsoft's BrainWave uses FPGAs. The lecture uses TPU energy measurements to make the point that over 90% of system energy in large ML models is spent on memory movement rather than computation, motivating later discussion of memory-centric computing.

Flynn's taxonomy and what SIMD means (22:59)

Flynn's taxonomy classifies machines by instruction streams versus data streams: SISD is a plain scalar processor, SIMD applies one instruction to many data elements, MISD resembles a systolic array (data flows through a chain of functional units), and MIMD covers multiprocessors and multithreaded processors. Modern systems, such as a phone's system-on-chip, combine several of these paradigms at once. SIMD is contrasted with data-flow parallelism (different operations run concurrently) and thread parallelism (independent control flows run concurrently).

Array processors vs vector processors (31:04)

SIMD can be implemented in space (array processor: many processing elements act on different data at the same time) or in time (vector processor: one pipelined functional unit processes elements in consecutive cycles). The lecture works through a short vector program (load, add, multiply, store on four elements) on both designs: the array processor finishes each instruction across all elements in one cycle, while the vector processor pipelines the same work across cycles. Vector processors are simpler to build, which is why they appeared first historically, while array processors became more attractive as transistor budgets grew; GPUs later combine both.

Vector registers, stride, and memory layout (42:13)

A vector processor needs vector data registers, a settable vector length register, and support for different memory strides. The lecture uses a matrix-multiply example stored in row-major order to show that loading a row has stride one, but loading a column requires a stride equal to the row width — a detail that directly affects how easily memory can keep up with the pipeline. Vector instructions also avoid intra-vector dependencies and control flow, which makes deep pipelining and easy address calculation possible.

Memory bandwidth, banking, and the Cray design (1:11:47)

Because a single vector instruction can trigger enormous numbers of memory accesses, memory bandwidth is often the real bottleneck. The lecture explains memory banking: splitting memory into banks that can each start one access per cycle, sharing address and data buses to limit chip pins, while requiring the number of banks to exceed the bank access latency to sustain one element per cycle. The Cray 1 supercomputer is used as a case study of combining a fast vector unit with an equally fast scalar unit, motivated by Amdahl's law and Seymour Cray's "two oxen or a thousand chickens" framing of specialized versus many simple cores.

Measuring the speedup: scalar vs vector vs chaining (1:27:58)

Working through a 50-element loop, the lecture compares dynamic instruction counts and cycle counts across four implementations: a plain scalar loop (304 dynamic instructions, around 2,004 cycles), a scalar loop with two memory ports (1,504 cycles), a vectorized version with 16 memory banks (285 cycles), and a chained vector version that forwards partial results between functional units (79 cycles, about 19 times faster than the original scalar code). The comparison also shows why VLIW's independent-instruction packing is a related but distinct approach, and why SIMD trades generality for efficiency on regular workloads.

Handling irregular data: vector length, gather/scatter, and masking (1:41:15)

The lecture closes by covering three practical complications: vector striping, splitting a loop into chunks that fit the hardware's maximum vector length; gather and scatter, indexed loads and stores used to pack sparse or irregularly placed data into vector registers; and vector masking, which uses a vmask register to implement predicated (conditional) execution so that only selected elements of a vector operation take effect, similar in spirit to how if/else is compiled for scalar code.

Before you watch

• Review the prior systolic-array lecture in this course, since the first 20 minutes build directly on it.
• Be comfortable with Amdahl's law, covered in an earlier lecture, since it is reused to explain why scalar performance still matters in vector machines.
• Recall pipelining and dependency hazards, since vector chaining is explained as an extension of pipeline forwarding.

Check your understanding

1. Where do array processors and vector processors each fall on the "parallel in space" versus "parallel in time" spectrum, and what hardware trade-off follows from that choice?
2. Why does loading a matrix column instead of a row change the memory stride, and why does that matter for sustaining one element per cycle?
3. Why must the number of memory banks exceed the bank access latency to avoid stalling a vector pipeline?
4. How does vector chaining reduce the 285-cycle vectorized execution time down to 79 cycles in the lecture's example?
5. What problem do gather, scatter, and vector masking each solve that a plain strided vector load or store cannot?