
CUDA Matrix Multiplication Optimization: From Naive to Near-cuBLAS
Matrix multiplication is the single most important kernel in GPU computing.
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
Matrix multiplication is the single most important kernel in GPU computing. Every linear layer, every convolution, every attention head in every transformer — all of them reduce to a general matrix multiply (GEMM) at their core. When you call torch.mm() or tf.matmul(), you’re invoking a kernel that has been optimized for decades. NVIDIA’s cuBLAS library achieves over 90% of a GPU’s theoretical peak floating-point throughput on this one operation. Understanding how it gets there is understanding how GPUs actually work.
The textbook algorithm is O(N³): computing the product of two N×N matrices requires 2N³ floating-point operations. GPUs should be perfect for this — thousands of cores running in parallel, hundreds of gigabytes per second of memory bandwidth. An A6000 GPU can deliver 23,270 GFLOP/s of single-precision throughput. But a naive CUDA implementation of matrix multiplication achieves only about 309 GFLOP/s — 1.3% of peak. The algorithm is correct. The arithmetic is identical. The entire gap is about how data moves through the memory hierarchy.
This article walks through six optimization stages that close that gap, from 1.3% to 93.7% of cuBLAS performance. Each stage targets a specific hardware bottleneck — global memory coalescing, shared memory reuse, register-level data reuse, vectorized loads — and each one comes with an interactive visualization so you can see exactly what changes and why it matters. By the end, you’ll have a concrete mental model for how high-performance GPU kernels are designed, and why the same principles apply to every operation in deep learning.
All performance numbers in this article are measured on an NVIDIA RTX A6000 GPU (Ampere architecture, GA102 chip) with 48 GB GDDR6X running CUDA 12.x. The matrices are 4096×4096 single-precision floats unless otherwise noted. The cuBLAS baseline for this configuration is 23,270 GFLOP/s.
The textbook matrix multiplication algorithm is three nested loops. To compute C = A × B where A is M×K and B is K×N, each element of the output matrix C[i][j] is the dot product of row i of A and column j of B:
Copy
for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) for (int k = 0; k < K; k++) C[i][j] += A[i][k] * B[k][j];
This requires exactly 2·M·N·K floating-point operations (one multiply and one add per iteration of the inner loop). For square matrices of size 4096, that’s 2 × 4096³ = 137.4 billion FLOPs. Each element of C requires K multiply-accumulate operations — a full dot product between a row of A and a column of B.
On a GPU, the naive approach maps naturally: assign each thread to compute one element of C. Thread (i, j) reads the entire row i of A and the entire column j of B, accumulates the dot product, and writes the result. With 4096 × 4096 = 16.7 million threads running across dozens of SMs, this seems like it should saturate the hardware. It doesn’t — not even close.
Copy
global void matmul_naive(float *A, float *B, float *C, int M, int N, int K) { int row = blockIdx.y * blockDim.y + threadIdx.y; int col = blockIdx.x * blockDim.x + threadIdx.x; if (row < M && col < N) { float sum = 0.0f; for (int k = 0; k < K; k++) sum += A[row * K + k] * B[k * N + col]; C[row * N + col] = sum; } }
Each thread loops through the entire K dimension, performing one multiply-add per iteration. The arithmetic is correct and the parallelism is massive. But the kernel achieves only 309 GFLOP/s — less than 2% of what this GPU can deliver.
The visualization above shows the access pattern for a single output element. To compute C[i][j], the thread must read K elements from row i of A and K elements from column j of B. When thousands of threads do this simultaneously, the total memory traffic is staggering: every thread independently reads the full K dimension from both A and B, with no data sharing between threads. The access pattern for B is especially wasteful — and the reason comes down to how matrices are stored in memory.
A 2D matrix is stored in memory as a 1D array, laid out row by row. In row-major order, element [i][j] of an N-column matrix lives at memory address base + i*N + j. Consecutive elements within the same row are adjacent in memory. Consecutive elements within the same column are N positions apart.
This layout has a profound consequence for the naive algorithm. When a thread reads row i of A, it accesses A[i][0], A[i][1], A[i][2], ... — consecutive memory addresses that will be served from a single cache line fetch. But when it reads column j of B, it accesses B[0][j], B[1][j], B[2][j], ... — each element is N positions apart in memory. Every single access to B misses the cache and fetches a new cache line, of which only one element (4 bytes out of 64 or 128) is actually used. The remaining bytes in each cache line are loaded and immediately discarded.
Consider a concrete example with N=4096. A cache line is 128 bytes (32 floats) on modern GPUs. When accessing column j of B:
This is the fundamental problem: the naive algorithm has a compute-to-memory ratio of O(1). Each loaded value is used exactly once and then evicted. For every multiply-add (2 FLOPs), we load at least one value from slow memory (8 bytes in FP32 round-trip for loads and stores). That puts us firmly in the memory-bound regime, nowhere near the GPU’s compute capability.
To quantify: the A6000 has 768 GB/s of memory bandwidth. At 8 bytes per FLOP pair, the maximum achievable throughput is 768/8 = 96 GFLOP/s if we’re purely memory-bound. The naive kernel gets 309 GFLOP/s only because the L2 cache absorbs some of the redundant reads. But we need to get to 23,270 GFLOP/s — that requires a 242× improvement in the compute-to-memory ratio.
The fix is tiling: divide the matrices into small blocks that fit in fast memory, load each block once, and reuse it for multiple output elements. If a tile is T×T, each loaded value gets reused T times instead of once. The compute-to-memory ratio rises from O(1) to O(T) — and that’s the difference between 1% and 90% of peak performance.
The tiling algorithm divides A, B, and C into tiles of size T×T. Instead of computing each output element independently, we compute an entire T×T block of the output at once. The output tile C[ti][tj] is the sum of partial products across k-slices:
Copy
C[ti][tj] = sum over k of (A[ti][k] × B[k][tj])
For each k-slice, we load a T×T tile from A and a T×T tile from B into fast memory. Then we multiply these two small tiles together (a T×T matrix multiply using 2T³ FLOPs) and accumulate the result into the output tile. We repeat this for each k-slice until the entire dot product dimension has been covered.
The key insight: each tile of A and B contains T² elements and is loaded once from slow memory. But each element participates in T multiply-add operations during the tile multiply. So the data reuse factor is T — we get T times more compute per byte loaded.
Let’s make this concrete with T=32. For one output tile of C:
On a CPU, "fast memory" means L1 cache. With 32 KB of L1 cache, we can fit tiles up to about 64×64 in FP32 (two tiles of 64×64×4 bytes = 32 KB). On a GPU, the equivalent is shared memory — an explicitly managed on-chip scratchpad that sits right next to the compute units. The tiling principle is identical on both architectures. What changes is the memory hierarchy and the programming model for exploiting it.
The transition from CPU to GPU tiling introduces several new concerns: how threads cooperate to load tiles, how memory accesses are coalesced across warps, and how the barrier synchronization between load and compute phases is managed. These GPU-specific details are what make the next three sections critical.
Before diving into shared memory tiling on the GPU, we need to understand how GPU memory access works at the hardware level. The critical concept is memory coalescing.
A GPU organizes threads into warps of 32 threads that execute in lockstep. When threads in a warp issue memory requests, the hardware tries to combine (coalesce) their individual 4-byte requests into as few memory transactions as possible. If all 32 threads access 32 consecutive 4-byte addresses, the hardware can serve this as a single 128-byte transaction. If the 32 threads access scattered addresses, each thread’s request may become a separate transaction — up to 32 individual fetches for data that could have been served in one.
The coalescing rules are straightforward:
In the naive GPU matmul, each thread computes one element of C. Threads within a warp compute adjacent columns of the same row: thread 0 computes C[i][0], thread 1 computes C[i][1], and so on. When these threads load their values from A, they all read the same row — this is fine (it can be broadcast). But when they load from B, thread 0 reads B[k][0], thread 1 reads B[k][1], etc. In row-major storage, B[k][0] and B[k][1] are adjacent in memory — so loads from B are actually coalesced.
The problem is subtler than it appears. While B accesses coalesce, the total number of global memory transactions is still enormous because there is zero data reuse across threads. Every thread independently loads the entire k-dimension from both A and B. With M×N threads each loading K elements from A and K elements from B, the total global memory traffic is O(M·N·K) — proportional to the number of FLOPs rather than the matrix size. The memory bus becomes the bottleneck long before the compute units are saturated.
This is why the naive CUDA kernel achieves only 309 GFLOP/s on an A6000 — 1.3% of its 23,270 GFLOP/s peak. The arithmetic units sit idle, waiting for data to arrive from global memory (HBM). The solution is the same as on CPU: tile the computation so that data loaded from global memory is reused many times. On GPU, the fast reuse buffer is shared memory.
Each streaming multiprocessor (SM) on a GPU has a bank of on-chip memory called shared memory — typically 48 to 228 KB depending on the GPU generation. This memory sits physically next to the compute cores, with bandwidth exceeding 12,000 GB/s — over 16× faster than global memory (HBM). Unlike L1/L2 caches, shared memory is explicitly managed by the programmer. You decide exactly what goes in and when.
The shared memory tiling kernel follows a simple pattern:
Copy
#define TILE 32
global void matmul_smem(float *A, float *B, float *C, int M, int N, int K) { shared float As[TILE][TILE]; shared float Bs[TILE][TILE];
int row = blockIdx.y * TILE + threadIdx.y; int col = blockIdx.x * TILE + threadIdx.x; float sum = 0.0f;
for (int t = 0; t < K; t += TILE) { // Cooperative load: each thread loads one element As[threadIdx.y][threadIdx.x] = A[row * K + t + threadIdx.x]; Bs[threadIdx.y][threadIdx.x] = B[(t + threadIdx.y) * N + col]; __syncthreads();
// Compute from shared memory for (int k = 0; k < TILE; k++) sum += As[threadIdx.y][k] * Bs[k][threadIdx.x]; __syncthreads(); } C[row * N + col] = sum; }
This pattern reduces global memory traffic by a factor of T (the tile size). Instead of each thread independently loading the full K dimension, the entire thread block cooperatively loads a T×T tile and every thread in the block reuses it. With T=32, the global memory traffic drops from O(M·N·K) to O(M·N·K / T) — a 32× reduction.
For more on how shared memory fits into the broader GPU memory hierarchy, see the GPU Memory Hierarchy concept page. For details on how SMs are organized, see Streaming Multiprocessor.
Shared memory tiling alone brings performance from around 1,987 to 2,980 GFLOP/s — a 1.5× improvement. That might seem modest given the 32× reduction in global memory traffic, but it’s because the bottleneck has shifted. Global memory bandwidth is no longer the primary constraint. Now the limiting factors are:
The next optimization addresses the biggest of these: per-thread compute density.
In the basic shared memory kernel, each thread computes exactly one element of the output matrix. It load
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。