Lecture 19: GPU Architectures

What this lecture covers

The lecture asks how GPUs achieve massive data parallelism while staying easy to program, and answers it by separating the programming model from the execution model: GPUs are programmed with ordinary-looking scalar threads (SPMD, single program multiple data) but executed on SIMD hardware by dynamically grouping threads that share a program counter into warps. It first finishes the previous lecture's SIMD material (memory banking, bank conflicts, combined array-and-vector processors, Amdahl's law, SIMD instruction extensions in general-purpose CPUs) before introducing GPUs proper.

This is part of the Digital Design and Computer Architecture course's execution-paradigm sequence, following data-flow, out-of-order, VLIW, systolic-array, and SIMD lectures, and it is described as likely the last lecture focused heavily on processor-centric execution before the course turns to memory systems. After watching, you should be able to explain the difference between a programming model and an execution model, describe how a warp is formed and scheduled, and explain why fine-grain multithreading lets a GPU tolerate memory latency.

Key ideas

• Programming model vs execution model: what the programmer expresses (for example, sequential, SIMD, or multi-threaded code) can be entirely different from how the hardware actually executes it.
• SPMD (single program, multiple data): every thread runs identical code on different data, unlike general multithreading where threads can do unrelated work.
• Warp (or wavefront): a set of scalar threads at the same program counter that hardware dynamically groups together and executes as one SIMD operation.
• SIMT (single instruction, multiple thread): Nvidia's term for this warp-based execution style, contrasted with traditional lock-step SIMD instructions that require a known vector length.
• Fine-grain multithreading of warps: many warps are interleaved on a simple, in-order pipeline; a warp that misses in cache is pulled out so other warps can keep the pipeline busy.
• Stride and bank conflicts: when a memory stride shares a common divisor with the number of memory banks, concurrent accesses collide, which is why row-major versus column-major matrix layout matters for performance.
• Amdahl's law and the serial bottleneck: even highly vectorizable code is limited by its non-parallelizable fraction, which is why fast scalar/serial execution still matters on GPUs.

Walkthrough

From SIMD review to GPU motivation (6:37)

The lecture opens by placing GPUs in context: after covering irregular-parallelism paradigms (data flow, out-of-order, VLIW) and regular-parallelism paradigms (systolic arrays, SIMD), GPUs are introduced as arguably the most successful case of SIMD processing, used for far more than graphics today. The instructor previews that GPUs combine SIMD with MIMD-style multithreading in a specific way.

Bank conflicts and matrix layout in memory (16:44)

Building on the prior lecture's memory-banking material, this section works through why a stride that shares a common factor with the number of memory banks causes repeated bank conflicts. Using a row-major-stored matrix multiplication example, loading a matrix row has stride one (no conflicts), but loading a matrix column requires a much larger stride that can collide with a power-of-two bank count. The lecture discusses mitigations: more banks, more ports per bank, better data layout, matrix transposition units, and randomized (prime-based) address-to-bank mapping, noting there is no universally perfect solution.

Combining array and vector processing inside a GPU (26:49)

Pure array processors and pure vector processors are described as opposite ends of a spectrum; modern SIMD hardware, and GPUs in particular, combine both, exploiting parallelism in both time and space. The lecture shows a GPU-style internal view where the vector register file is partitioned across parallel "lanes," each lane holding specific indexed elements, and walks through an example with three functional units (load, multiply, add), 32 elements per vector register, and eight lanes, reaching 24 concurrent operations per cycle in steady state.

Automatic vectorization and the limits of Amdahl's law (30:50)

Using a simple vector-addition loop, the lecture shows how a compiler or programmer recognizes independent loop iterations and reorders them into parallel vector instructions, a process called vectorization. It then revisits Amdahl's law specifically for vectorizable code: with an infinite number of vector lanes, a 50% parallelizable program only reaches 2x speedup, a 99% parallelizable program caps at 100x, and only 99.9% parallelizable code reaches roughly 1000x, reinforcing why the serial (non-vectorizable) portion of a program is the real bottleneck.

SIMD instructions in general-purpose CPUs (39:54)

The lecture shows that SIMD ideas reached ordinary CPUs through instruction set extensions such as Intel's MMX, which partitions a wide ALU (for example 32-bit) into several narrower packed operations (four 8-bit adds, two 16-bit adds, and so on). It works through packed compare, packed multiply-add, and a full worked example of compositing two images using packed comparisons and masks to replace blue-background pixels with a new background, illustrating why multimedia and image processing motivated these extensions before machine learning did.

Programming model vs execution model: SPMD and warps (1:09:58)

After a break, the lecture formally separates programming models (sequential, data-parallel SIMD, multi-threaded MIMD/SPMD) from execution models (out-of-order, vector, array, data-flow, multiprocessor). Returning to the vector-addition example, it walks through three ways to express the same parallel loop: sequential scalar code, explicit SIMD vector instructions, and a third option, giving each independent loop iteration its own thread. This third option, SPMD, is what GPUs use: the programmer writes ordinary-looking scalar thread code with no vector length or vector registers, and the hardware dynamically groups threads at the same program counter into a warp.

Warp scheduling, latency tolerance, and GPU memory access (1:26:12)

The lecture details how warps are scheduled through a SIMD pipeline: fetch and decode happen once per warp since all its threads share a program counter, then execution is distributed across parallel lanes. Fine-grain multithreading interleaves many warps on a simple in-order pipeline with no branch prediction; a warp that misses in the memory hierarchy is pulled out of the schedule so other warps can proceed, which is why GPUs need large register files to hold many threads' state simultaneously and why memory bandwidth remains a central design pressure. The lecture closes by contrasting traditional lock-step SIMD (single thread, known vector length, vector ISA) with warp-based SIMD (many scalar threads, no vector length, ordinary scalar ISA, dynamically formed SIMD groups), and introduces SPMD synchronization using a character-counting example to preview control-flow divergence, the topic planned for the next lecture.

Before you watch

• Watch the previous SIMD architectures lecture in this course first, since this lecture continues directly from it on memory banking, array vs vector processors, and Amdahl's law.
• Review Flynn's taxonomy (SISD, SIMD, MISD, MIMD) and basic pipelining, both covered earlier in the course.
• Familiarity with fine-grain multithreading, covered in an earlier lecture, helps since GPU warp scheduling is explained as an extension of it.

Check your understanding

1. How do a programming model and an execution model differ, and why does the lecture say a GPU's programming model is not SIMD even though its execution model is?
2. Why does a matrix's row-major storage cause a large stride, and hence bank conflicts, when accessing a column?
3. What is a warp, and what hardware condition determines when threads get grouped into one?
4. Why does a memory-hierarchy miss cause a warp to be pulled out of the pipeline, and what does that accomplish?
5. According to Amdahl's law, why does even 99% parallelizable code cap out at roughly 100x speedup with infinite vector lanes?