Tiling: The Trick That Makes Matrix Multiplication Faster
Learn the most important trick in GPU programming: load a piece of data once, then reuse it many times.
The last three lessons set up a puzzle. Memory is slow (the memory wall). There is a little very fast memory near the cores (the memory ladder). And matrix multiplication uses every number many times over: each number in the first matrix meets every column of the second. How do you exploit that?
The naive way computes each output on its own, fetching its row and column from slow memory every time. The same numbers get fetched again and again for different outputs: like walking down to the cellar for every pinch of salt, when you could have brought the whole jar upstairs.
Tiling brings the jar upstairs. A group of threads copies a small square piece of each matrix, a tile, into fast shared memory. Then it does every calculation that needs those numbers before moving on to the next pair of tiles. Same multiplications, same answer, far fewer trips to slow memory.
The bigger the tile, the more reuse: doubling the tile’s width roughly halves the trips to slow memory. Back on the roofline, that means higher arithmetic intensity, which slides the work from “waiting for memory” towards “maths at full speed”. The limit is space: shared memory holds only a couple of hundred kilobytes per SM, so the tiles have to fit.
This one idea is everywhere. The matrix libraries that run every AI model are, at heart, extremely carefully tuned tiling. And FlashAttention (2022), one of the most important speed-ups for transformers, is tiling applied to attention, so the huge table of attention scores never has to be written out to slow memory at all.
Key takeaways
- The same answer can cost very different amounts of memory traffic depending on the order of the work.
- Tiling loads a block of data into fast memory once and reuses it for many calculations.
- Doubling the tile size roughly halves the trips to slow memory, until the tiles no longer fit.
- Fast AI libraries, from cuBLAS to FlashAttention, are largely clever tiling.
Check your understanding
Go deeper (more technical)
For an N × N matrix multiply with T × T tiles, each output tile needs N/T pairs of input tiles, so the slow-memory loads are about 2N³ / T numbers instead of 2N³. The arithmetic intensity grows in proportion to T.
Real kernels tile at several levels at once: blocks tile into shared memory, warps tile into registers, and tensor cores (two lessons from now) work on small fixed tiles. FlashAttention (Dao and colleagues, 2022) computes attention tile by tile with a running softmax, so the N × N score matrix is never stored in HBM.