Chapter 12: Parallel matrix multiplication
This introduction explains the data bottleneck in naive matrix multiplication and how tiling with shared memory can reduce repeated global-memory access.
After this chapter you will be able to
- Matrix multiplication data bottleneck. Explain why a naive GPU matrix multiplication can spend much of its time waiting for data and how tiling with shared memory addresses that bottleneck.
- Matrix multiplication fundamentals. Explain how matrix dimensions and row-column dot products determine the result and computational work.
- Naive thread and grid mapping. Describe how the naive kernel assigns output elements to threads and maps a two-dimensional launch to matrix rows and columns.
- Redundant global memory loads. Explain why the naive kernel repeatedly requests the same input values and describe the scale of that traffic in the section's example.
- Naive arithmetic intensity. Calculate the naive kernel's arithmetic intensity for the example and explain what it implies about the bottleneck.
- Thread block tile ownership. Describe how a thread block computes an output tile by cooperating over chunks of the input matrices.
- Shared memory data reuse. Explain how staging values in shared memory reduces repeated global memory access.
- Tiles and data reuse. Explain what a tile is and why matrix multiplication uses small tiles in shared memory.
- Tiled dot product accumulation. Trace how matching segments of an A row and B column produce partial sums for one output element.
- Floating point comparison. Explain why tiled results may differ from a CPU reference and how to compare them when debugging.
- Block and tile matching. Explain why this kernel requires both block dimensions to equal TILE_SIZE, and what goes wrong with smaller or larger blocks.
- Per-block shared memory tiles. Describe the two shared-memory tiles used for C = A × B and why reading loaded tiles avoids repeated trips to global memory.
- Chunked dot product accumulation. Trace how each thread accumulates its output element across tile-loop iterations, and explain why the dot product is processed in chunks.
- Cooperative tile loading. Explain how threads cooperate to load tiles of A and B into shared memory.
- Tile offset and indexing. Trace how the tile offset and thread index determine an A element's global column and its location in the shared tile.
- Partial tiles and boundaries. Explain how zero-padding and the final output boundary check handle dimensions that are not multiples of the tile size.
- Barrier after tile loading. Explain how __syncthreads() coordinates tile loading and computation, and what can happen without it.
- Shared memory partial products. Explain how each thread computes its partial dot product from the tiles and why shared memory helps.
- Conflict-free tile read patterns. Explain why the warp's reads from both shared-memory tiles avoid bank conflicts.
- Tile loop synchronization. Explain why each tile iteration needs two synchronization points and how the kernel finishes the dot product.
- Tiled memory traffic reduction. Explain how shared-memory tile reuse reduces global memory traffic, using the section's matrix example.
- Arithmetic intensity and Roofline. Explain how tiling changes whole-kernel arithmetic intensity and interpret the result using the example GPU's Roofline ridge point.
- Tile size resource limits. Explain why this kernel cannot use arbitrarily large square tiles despite the benefit of increased reuse.
- Production cuBLAS performance. Explain why cuBLAS is the default for production matrix multiplication and how its performance compares with the chapter’s tiled kernel.
- Single precision GEMM operation. Describe what cublasSgemm computes and how to select a plain matrix product.
- Row major transpose trick. Explain how to obtain a row-major matrix product using cuBLAS’s column-major convention, including the role of leading dimensions.
- Custom matmul use cases. Justify when writing a custom matrix multiplication kernel may be worthwhile despite the cuBLAS default.
- Missing Tile Barrier. Explain how a missing barrier can corrupt a tiled matrix product without raising an error.
- Matrix Layout Mismatch. Explain why using column-major arithmetic on row-major data can silently produce a wrong product.
- Two barriers in tiled multiplication. Explain why a tiled matrix multiplication loop needs synchronization both after loading and after computing.
- Matrix layout and indexing. Explain how column-major indexing misreads a row-major matrix, and apply the row-major index formula.
- Tile Size Resource Limits. Explain how thread and shared-memory limits constrain the tile size of a one-element-per-thread matrix multiplication kernel, and distinguish when violations are detected.
- Matrix Multiplication Inputs and Outputs. Describe the matrix dimensions and the input values needed to compute each output element.
- Cooperative Tile Data Reuse. Explain how threads in a block cooperate to load and reuse matrix tiles, and contrast this with independent global-memory fetching.
What it builds on
- Introducing shared memory (chapter 11) · Shared memory as storage accessible near threads.
- A first taste of tiling: transpose (chapter 11) · The initial example of tiling with shared memory.
- The global index formula (chapter 3) · Combining block and thread indices to locate work in a grid.
- Arithmetic intensity (chapter 10) · Arithmetic intensity as operations per byte moved.
- Compute-bound or memory-bound? (chapter 10) · The distinction between compute-bound and memory-bound work.
- The 3-Step Recipe (chapter 11) · Shared-memory cooperation among threads.
- The barrier: __syncthreads() (chapter 5) · The block-wide barrier provided by __syncthreads().
- Bank conflicts (chapter 11) · Shared-memory bank conflicts
Section by section
Introduction
This introduction explains the data bottleneck in naive matrix multiplication and how tiling with shared memory can reduce repeated global-memory access.
- Matrix multiplication data bottleneck: Explain why a naive GPU matrix multiplication can spend much of its time waiting for data and how tiling with shared memory addresses that bottleneck.
Why it matters: This explains why fast arithmetic alone does not guarantee fast matrix multiplication.
Key terms: global memory, shared memory, tiling
12.1 Understanding the problem
This section explains naive parallel matrix multiplication and analyzes why redundant memory requests make it memory-bound.
- Matrix multiplication fundamentals: Explain how matrix dimensions and row-column dot products determine the result and computational work.
Why it matters: The dimensions and dot products determine both the parallel work and the data each thread needs. - Naive thread and grid mapping: Describe how the naive kernel assigns output elements to threads and maps a two-dimensional launch to matrix rows and columns.
Why it matters: This mapping makes the independent output calculations parallel while covering the whole result matrix. - Redundant global memory loads: Explain why the naive kernel repeatedly requests the same input values and describe the scale of that traffic in the section's example.
Why it matters: The repeated requests explain the bottleneck that motivates tiled matrix multiplication. - Requested traffic and caching: Distinguish the kernel's requested memory traffic from bytes actually transferred from DRAM.
Why it matters: This distinction prevents the requested 4 GB from being mistaken for a measured DRAM transfer. - Naive arithmetic intensity: Calculate the naive kernel's arithmetic intensity for the example and explain what it implies about the bottleneck.
Why it matters: Arithmetic intensity quantifies why a workload with substantial arithmetic can still spend much of its time waiting for data.
Key terms: dot product, multiply-add, floating-point operations, naive kernel, 2D grid, thread blocks, ceiling division, global memory reads, redundant traffic, unique data
12.2 The solution: tiled matrix multiplication
This section explains how thread blocks tile matrix multiplication and reuse input data through shared memory.
- Thread block tile ownership: Describe how a thread block computes an output tile by cooperating over chunks of the input matrices.
Why it matters: This mapping shows how the matrix multiplication work is divided among blocks. - Shared memory data reuse: Explain how staging values in shared memory reduces repeated global memory access.
Why it matters: Reuse avoids repeatedly fetching the same input values from global memory.
Key terms: tiling, thread block, tile, shared memory, global memory, global memory transaction, data reuse
12.3 Tiles: breaking a matrix into bite-sized chunks
This section explains how matrix tiling enables shared-memory reuse and partial-sum computation, including tile-size limits and floating-point caveats.
- Tiles and data reuse: Explain what a tile is and why matrix multiplication uses small tiles in shared memory.
Why it matters: Tiling makes data reuse practical even when the full matrices do not fit in fast memory. - Tile size and limits: Describe what TILE_SIZE measures and the shared-memory and thread-count constraints on choosing it.
Why it matters: Tile size determines both the amount of tile storage and the thread count the kernel requires. - Tiled dot product accumulation: Trace how matching segments of an A row and B column produce partial sums for one output element.
Why it matters: This decomposition lets the kernel compute a result using one manageable pair of tiles at a time. - Floating point comparison: Explain why tiled results may differ from a CPU reference and how to compare them when debugging.
Why it matters: A bit-for-bit comparison can flag a correct floating-point computation as an error.
Key terms: tile, shared memory, data reuse, tile size, TILE_SIZE, threads per block, dot product, partial sums, tile iteration, matching strips
12.4 Walkthrough of a tiled kernel
This section introduces the tiled matrix multiplication kernel’s block layout, shared-memory tiles, and per-thread accumulation across dot-product chunks.
- Block and tile matching: Explain why this kernel requires both block dimensions to equal TILE_SIZE, and what goes wrong with smaller or larger blocks.
Why it matters: The one-element-per-thread design makes the launch dimensions part of this kernel’s correctness. - Per-block shared memory tiles: Describe the two shared-memory tiles used for C = A × B and why reading loaded tiles avoids repeated trips to global memory.
Why it matters: Shared tiles let threads reuse data close to the GPU’s computation. - Chunked dot product accumulation: Trace how each thread accumulates its output element across tile-loop iterations, and explain why the dot product is processed in chunks.
Why it matters: The tile loop makes a dot product too large for the shared-memory budget manageable in pieces. - Tile size tradeoff: Describe the tradeoff behind choosing a 32×32 tile and block in this example.
Why it matters: More data reuse does not automatically make the largest block the fastest choice.
Key terms: TILE_SIZE, blockDim, threadIdx, shared memory, tile, global memory, data reuse, dot product, sum, tile loop
12.5 Step 1: Load tiles into shared memory
This section explains cooperative loading of matrix tiles into shared memory, including tile indexing and boundary handling.
- Cooperative tile loading: Explain how threads cooperate to load tiles of A and B into shared memory.
Why it matters: Cooperative loading lets the block assemble the shared data needed for tiled multiplication. - Tile offset and indexing: Trace how the tile offset and thread index determine an A element's global column and its location in the shared tile.
Why it matters: The indexing connects each thread's shared-memory slot to the correct part of the input matrix. - Partial tiles and boundaries: Explain how zero-padding and the final output boundary check handle dimensions that are not multiples of the tile size.
Why it matters: Boundary handling preserves correct results for matrix dimensions that do not fit whole tiles.
Key terms: cooperative loading, shared tile arrays, t * TILE_SIZE, aCol, threadIdx.x, threadIdx.y, tileA, boundary check, zero-padding, partial tiles
12.6 Step 2: Synchronize
This section explains why a block-wide barrier is needed between loading shared-memory tiles and computing with them.
- Barrier after tile loading: Explain how __syncthreads() coordinates tile loading and computation, and what can happen without it.
Why it matters: This barrier ensures threads do not compute using tile data that is not ready.
Key terms: __syncthreads(), barrier, block, tile
12.7 Step 3: Compute using shared memory
This section explains how threads compute partial dot products from shared-memory tiles without bank conflicts.
- Shared memory partial products: Explain how each thread computes its partial dot product from the tiles and why shared memory helps.
Why it matters: Using the loaded tiles lets the computation avoid slower global-memory accesses inside the loop. - Conflict-free tile read patterns: Explain why the warp's reads from both shared-memory tiles avoid bank conflicts.
Why it matters: The access pattern allows threads to use both shared-memory tiles without bank conflicts.
Key terms: partial dot product, shared memory, global memory, latency, bank conflict, broadcast, warp, threadIdx.y, threadIdx.x
12.8 Step 4: Synchronize again, then repeat
Completes the tiled matrix multiplication loop and explains its synchronization, memory traffic, arithmetic intensity, and tile-size limits.
- Tile loop synchronization: Explain why each tile iteration needs two synchronization points and how the kernel finishes the dot product.
Why it matters: Both barriers protect shared tile data at different points in the loop. - Tiled memory traffic reduction: Explain how shared-memory tile reuse reduces global memory traffic, using the section's matrix example.
Why it matters: Reusing data on-chip addresses the repeated global loads that make the naive kernel expensive. - Arithmetic intensity and Roofline: Explain how tiling changes whole-kernel arithmetic intensity and interpret the result using the example GPU's Roofline ridge point.
Why it matters: Arithmetic intensity connects the traffic savings to the kernel's potential performance bottleneck. - Tile size resource limits: Explain why this kernel cannot use arbitrarily large square tiles despite the benefit of increased reuse.
Why it matters: A tile size must fit both the thread block and the shared-memory buffers, even if larger tiles improve reuse.
Key terms: __syncthreads(), sum, boundary check, dot product, TILE_SIZE, global memory traffic, shared memory, data reuse, arithmetic intensity, FLOPs
12.9 In production: use cuBLAS
This section explains why cuBLAS is the production default for matrix multiplication, how to use it with row-major matrices, and when alternatives or custom kernels are appropriate.
- Production cuBLAS performance: Explain why cuBLAS is the default for production matrix multiplication and how its performance compares with the chapter’s tiled kernel.
Why it matters: The kernel you build to learn tiling is not usually the best production implementation. - Single precision GEMM operation: Describe what cublasSgemm computes and how to select a plain matrix product.
Why it matters: The scalar parameters determine whether the existing output contributes to the result. - Row major transpose trick: Explain how to obtain a row-major matrix product using cuBLAS’s column-major convention, including the role of leading dimensions.
Why it matters: Understanding the storage convention prevents a matrix multiplication from silently producing the wrong result. - Specialized NVIDIA library choices: Distinguish cuBLASLt and CUTLASS from standard cuBLAS in terms of the control they provide.
Why it matters: Different levels of library control suit different optimization needs. - Custom matmul use cases: Justify when writing a custom matrix multiplication kernel may be worthwhile despite the cuBLAS default.
Why it matters: Custom code has a cost, so it is most useful when a library cannot meet a specific need. - GPU compute performance measure: State what GFLOPS measures and how floating-point multiplies and additions are counted.
Why it matters: GFLOPS gives you a way to interpret the compute-performance comparisons in this section.
Key terms: cuBLAS, tiling, Tensor Cores, FP32, FP16, cublasSgemm, single-precision, α, β, column-major
12.10 Common mistakes
This section identifies two silent errors that can produce an incorrect matrix product: a missing barrier and a mismatch in matrix indexing.
- Missing Tile Barrier: Explain how a missing barrier can corrupt a tiled matrix product without raising an error.
Why it matters: A kernel can run without an error while threads interfere with one another's tile data. - Matrix Layout Mismatch: Explain why using column-major arithmetic on row-major data can silently produce a wrong product.
Why it matters: A layout mismatch can give an incorrect product even when the program reports no error.
Key terms: barrier, tile, block, column-major arithmetic, row-major data
12.11 Mistake 1: Missing the second __syncthreads()
This section explains why tiled matrix multiplication needs a second synchronization barrier and why omitting it can be hard to detect.
- Two barriers in tiled multiplication: Explain why a tiled matrix multiplication loop needs synchronization both after loading and after computing.
Why it matters: Both barriers protect the shared tiles at different points in the loop. - Hard-to-detect race symptoms: Describe how the missing second barrier can produce misleading test results, including why a small matrix may appear correct.
Why it matters: A successful run or a small passing test does not rule out this synchronization bug.
Key terms: __syncthreads(), shared memory, tileA, tileB, write-after-read race, K, TILE_SIZE, non-deterministic
12.12 Mistake 2: Row-major vs column-major confusion
This section explains how mismatched matrix storage and indexing produce structured errors and how to correct and check them.
- Matrix layout and indexing: Explain how column-major indexing misreads a row-major matrix, and apply the row-major index formula.
Why it matters: Correct indexing prevents a kernel from producing plausible but systematically wrong matrix values. - Hand checked test case: Describe how to check for a matrix indexing mistake using a small test case.
Why it matters: A hand-checkable example can catch structured errors that a quick glance might miss.
Key terms: row-major order, column-major arithmetic, transpose, test case
12.13 Mistake 3: Tile size over the limits
This section checks tile sizes against GPU limits and recaps the inputs, outputs, and cooperative data reuse of tiled matrix multiplication.
- Tile Size Resource Limits: Explain how thread and shared-memory limits constrain the tile size of a one-element-per-thread matrix multiplication kernel, and distinguish when violations are detected.
Why it matters: A tile can fit in shared memory and still be too large to launch. - Matrix Multiplication Inputs and Outputs: Describe the matrix dimensions and the input values needed to compute each output element.
Why it matters: These dependencies identify the work and data needed for each output element. - Cooperative Tile Data Reuse: Explain how threads in a block cooperate to load and reuse matrix tiles, and contrast this with independent global-memory fetching.
Why it matters: Cooperative loading makes reuse explicit and reduces repeated global-memory traffic. - Shortest Path Loop Adaptation: Describe the practice exercise's changes to the matrix multiplication loop for finding shortest paths.
Why it matters: The exercise shows how changing the operations in a familiar loop can adapt it to another problem.
Key terms: TILE_SIZE, threads per block, shared memory budget, dot product, row, column, cooperative tile loading, shared tiles, global memory, reuse
12.14 Summary
Where this is used later
- What limits occupancy: three resources (chapter 14) · Block resource demands affect how many blocks can occupy an SM.
Concepts explained in this chapter
- shared memoryShared memory is a fast, explicitly managed memory space accessible to threads within a GPU thread block.
- matrix-matrix multiplicationMatrix multiplication is the algebraic operation that combines rows of one matrix with columns of another to produce a matrix of dot products.
- arithmetic intensityArithmetic intensity is the number of floating-point operations performed per byte transferred to and from memory.
- memory trafficMemory traffic is the amount of data transferred between memory and processing units during computation.
- data reuseData reuse is the practice of retaining or sharing a value so that multiple computations can use it without repeatedly fetching it from its original storage.
- tile sizeTile size is the number of rows and columns in a tile used by a tiled computation.
- tileA tile is a smaller rectangular block of elements taken from a larger matrix or other data structure.
- tiled matrix multiplicationTiled matrix multiplication divides matrix operands into smaller blocks that can be computed using local data reuse.
- tilingTiling is a technique that partitions data or computation into smaller blocks to enable reuse and reduce memory traffic.
- naive matrix multiplication kernelNaive matrix multiplication assigns one GPU thread to each output element, with that thread computing the full dot product for that element.
- GPU memoryDevice memory is memory located on a GPU and accessible to GPU computations.
- threadA thread is a sequence of instructions that performs a unit of computation.
- column-major orderColumn-major order is a multidimensional array layout in which elements of each column are contiguous in memory.
- row-major orderRow-major order is a multidimensional array layout in which elements of each row are contiguous in memory.
- CUDA kernelA CUDA kernel is a function launched on a GPU to execute concurrently across many GPU threads.
- block dimensionBlock dimensions are the configured extents of a CUDA thread block along its coordinate axes.
- cooperative loadingCooperative loading is a technique in which multiple threads work together to load data into a shared storage area.
- zero paddingZero padding extends an input with zero-valued elements beyond its boundary.
- synchronizationSynchronization is the coordination of concurrent computations so that their execution observes required ordering or completion constraints.
- write-after-read raceA write-after-read hazard occurs when a write may overwrite a location before a preceding read from it is complete.
- __syncthreads()__syncthreads is a CUDA barrier operation that makes threads in one block wait until all threads in that block reach the barrier.
- ceiling divisionCeiling division is division rounded upward to the smallest integer greater than or equal to the exact quotient.
- compute-boundCompute-bound describes a computation whose performance is limited primarily by the processor's computational capacity.
- floating-point operation countA floating-point operation is an arithmetic operation performed on floating-point values.
- memory boundA memory-bound kernel is a GPU kernel whose performance is limited primarily by memory data transfer.
- thread limitA thread limit is the maximum number of threads that can be assigned to one CUDA block.
- block sizeThreads per block is the configured number of GPU threads assigned to each CUDA thread block in a kernel launch.
- floating-point operations per secondFLOPS measures the rate of floating-point operations performed per second.
- shared memory broadcastA memory broadcast supplies one value read from a single address to multiple threads.
- barrierA barrier is a synchronization mechanism that makes participating threads wait until the required threads reach a specified point.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
