What is memory coalescing? 32 threads, 1 transaction vs 32 transactions.

*the tile*

Multiplying two matrices is the single most important operation a GPU does. It is the heart of every neural network layer, every attention calculation, nearly all the heavy lifting in AI.

↳ And the difference between a naive way of doing it and the clever way, called tiling, is not a small tweak. It is often close to a tenfold speedup, from the same arithmetic, on the same hardware.

Tiling is the flagship example of the one idea that governs almost all GPU performance: that the cost is never the math, it is moving the data. Seeing exactly how it rescues matrix multiplication teaches you the whole philosophy in one concrete picture.

The Setup

Start with what multiplying two matrices requires. Every entry in the result is computed by taking one row from the first matrix and one column from the second, marching down them together, multiplying pairs and adding up.

So to fill in the whole result grid, every row of the first matrix has to meet every column of the second. The total amount of arithmetic is large but perfectly parallel: one thread can compute each output entry independently. So far this looks like an ideal GPU job, tons of independent work.

The Fatal Flaw

Now the naive approach and its fatal flaw. You assign one thread to each output entry, and each thread reads its row from the first matrix and its column from the second, straight out of the slow main memory, and does its multiply-add march.

And here is the waste. Think about all the threads computing entries in the same row of the result. They all need the exact same row from the first matrix. But each one independently goes out to slow memory and fetches that entire row for itself. The same row gets pulled from slow memory again and again, once per thread that needs it. And the same is true for columns.

Every piece of the input matrices gets hauled out of slow memory not once, but as many times as there are threads that touch it, which can be hundreds of times over. The actual multiplying is quick, so nearly all the time is spent on this mountain of repeated slow-memory traffic. The operation is badly memory-bound, drowning in redundant fetches.

Cooperative Loading

So the question that points straight at the fix: if the problem is that the same rows and columns are fetched from slow memory over and over, can we fetch each piece just once, put it somewhere fast, and let all the threads that need it share that one copy?

That is tiling, and it uses the fast on-chip scratchpad memory that a group of threads shares. Instead of each thread independently streaming its whole row and column from slow memory, the threads cooperate. They break the matrices into small square blocks called tiles.

The group of threads works together to load one tile from each input matrix out of slow memory and into the fast shared scratchpad, one single trip. Then, with those tiles sitting in fast memory, every thread does its share of the multiplying by reading from the fast scratchpad, not slow memory.

Because the tile holds data that many threads need, each value loaded once from slow memory now gets reused by many threads out of fast memory. Once the group has squeezed all the arithmetic it can out of the current pair of tiles, it loads the next pair, and marches across the matrices tile by tile, accumulating the results as it goes.

The Dramatic Win

Now see why this is such a dramatic win, because it is worth making concrete. In the naive version, each value from the input was dragged out of slow memory once for every thread that used it. In the tiled version, each value is dragged out of slow memory once for the whole tile, and then reused by every thread in the tile from fast memory.

So if a tile is, say, sixteen by sixteen, then each value loaded serves a whole row or column of threads within that tile, meaning you cut the slow-memory traffic by a factor equal to the tile's width. Load once, reuse many times. The mountain of redundant slow fetches collapses to a fraction. And since the operation was memory-bound, slashing the memory traffic by that factor speeds up the whole thing by nearly the same factor. You moved the bottleneck off of memory and back onto the actual math, which is exactly where you want it.

The Tension

Now an objection that gets at the real tradeoff: if bigger tiles mean more reuse and less slow-memory traffic, why not use enormous tiles and reuse everything?

Because the fast scratchpad is tiny. It can only hold so much, and a tile has to fit inside it. Push the tile too big and it simply does not fit. Worse, the more scratchpad each group of threads claims, the fewer groups can run on the hardware at once, which chokes the GPU's ability to hide delays by switching between groups.

So tile size is a balance: big enough to get strong reuse, small enough to fit in the scratchpad and leave room for enough groups to run. It's the same tension that runs through all of this hardware, the fast memory is precious and scarce, and using it well means using just the right amount.

The Subtlety of Loading

There is one more subtlety that connects to how memory is delivered. When the group loads a tile from slow memory, it matters that the threads read neighboring locations together, so the hardware can grab them in one efficient sweep rather than many scattered fetches.

So a well-written tiled multiply is careful to arrange the loading so that consecutive threads pull consecutive values, keeping the tile-loading itself efficient. The tiling gives you reuse, and careful loading gives you efficient fetches, and you need both for the full speedup.