Matrix Tiling: Same Arithmetic, Ten Times Faster
The tiled matrix multiply performs exactly the same multiply-accumulate operations as the naive triple loop, in a different order. It wins because a block of each matrix is brought into cache once and used many times, instead of a row or column being re-fetched on every pass.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
What the naive loop actually asks the memory system for
Take C = A × B with row-major storage. In the standard i, j, k ordering, the innermost loop walks k. Access to A[i][k] moves along a row — consecutive addresses, so a line brings in several useful elements and the prefetcher recognises the stride. Access to B[k][j] moves *down a column*, so each step jumps a whole row-length in memory. Every one of those accesses lands on a different cache line.
That would be tolerable if those lines stayed resident, but for a large matrix they do not. By the time the next value of j needs the column again, the lines have been evicted by the intervening traffic. So the same elements of B are fetched from DRAM once per value of i — the working set is far larger than the cache, and the hardware has no way to help (Working Set: Why Performance Falls Off a Cliff, Cache Thrashing: Load, Evict, Reload, Repeat).
The arithmetic intensity — useful operations performed per byte transferred — is the number to watch. The naive version has terrible arithmetic intensity: it does roughly one multiply-accumulate per line fetched. The whole point of tiling is to raise that ratio, and it does so without changing the numerator.
1for i in 0..n:2 for j in 0..n:3 for k in 0..n:4 C[i][j] += A[i][k] * B[k][j]5 6// A[i][k] : sequential, prefetch-friendly7// B[k][j] : stride of one full row, a new line every step8// Reuse : none - by the next pass, B's lines are long evicted1for ii in 0..n step T:2 for jj in 0..n step T:3 for kk in 0..n step T:4 // this inner nest touches only three T x T blocks5 for i in ii..ii+T:6 for j in jj..jj+T:7 for k in kk..kk+T:8 C[i][j] += A[i][k] * B[k][j]9 10// Working set: 3 * T * T elements, chosen to fit a cache level11// Reuse : each loaded element participates in T operationsExactly the same multiply-accumulates happen, in a different order. The tiled version chooses T so that three T×T blocks fit comfortably in a cache level; each element brought in is then used T times before eviction instead of once. Transfers drop by roughly a factor of T while arithmetic stays identical — which is why this is a data-movement win and not a work-reduction win.
Choosing the tile size, and why the answer is not universal
The constraint is that the *working set of the inner nest* must fit in the cache level you are targeting, with room to spare. Three blocks are live at once — a block of A, a block of B and a block of C — so the requirement is roughly 3 × T² × sizeof(element) ≤ usable cache. "Usable" is doing real work in that sentence: the cache is shared with everything else the thread touches, and on a shared last-level cache, with everything the *other cores* touch too (What a Second Core Actually Adds).
That immediately tells you the tile size is machine-specific and cannot be a portable constant. A T tuned for one machine's L2 will overflow another's and thrash, or underfill it and leave reuse unclaimed. Production numerical libraries handle this by tuning at build or run time, and often by tiling at *several* levels at once — a large tile for L3, a smaller one nested inside for L2, and register blocking innermost.
This is also why the cache-oblivious approach is attractive in principle: a recursive divide-and-conquer multiply gets reuse at every level automatically, because the subproblems shrink until they fit whatever the cache happens to be. It gives up some of the constant-factor tuning that an explicitly blocked, hand-optimised kernel achieves, which is why the highest-performance libraries still tune explicitly.
| Quantity | Naive | Tiled | Why |
|---|---|---|---|
| Multiply-accumulate operations | n³ | n³ | Identical — no arithmetic is saved |
| Instructions retired | Roughly n³ plus loop overhead | Slightly more, from extra loop nesting | Tiling adds bookkeeping, not work |
| Cache lines transferred | Grows with n³ for the column-walked operand | Roughly n³ divided by the tile dimension | Each loaded element is reused T times |
| Arithmetic intensity | Low — about one operation per line | High — about T operations per line | This is the entire mechanism |
| Runtime on a large matrix | Memory-bound and slow | Approaches compute-bound | The bottleneck moves from DRAM to the ALUs |
The access pattern, drawn
The layout below shows why the column walk is so expensive. In a row-major matrix, one cache line covers several *horizontally adjacent* elements. Walking a row consumes all of them; walking a column uses exactly one element from each line it touches and discards the rest — so the effective useful fraction of every byte transferred is one over the elements-per-line.
Tiling fixes this not by changing the layout but by changing *when* the other elements in the line get used. Inside a tile, the loop comes back to neighbouring elements while their line is still resident, so the bytes that were fetched alongside the one you asked for are eventually consumed rather than evicted unused.
This is the same mechanism as Spatial Locality, applied deliberately rather than accidentally. The naive loop has good spatial locality on A and terrible spatial locality on B; the tiled loop has good spatial locality on both, because the block structure keeps every operand's next access nearby in both space and time.
A column walk asks for B[k][j] and is handed all eight elements. It uses one and moves to a different line for the next iteration; by the time the loop needs B[k][j+1], this line is gone. Tiling keeps the loop inside the block so the other seven are consumed before eviction.
Key points
- Tiled and naive matrix multiply perform identical arithmetic; only the order differs, and only data movement changes.
- The naive column walk uses one element per cache line fetched and discards the rest, then re-fetches the same lines on the next pass.
- Tiling raises arithmetic intensity — operations performed per byte transferred — by keeping a block resident while it is fully consumed.
- The tile size must keep three blocks inside a cache level, which makes it machine-specific and not a portable constant.
- Real libraries tile at several levels at once and tune at build or run time; a hard-coded tile size is a portability hazard.
Loop Order & Locality
Change an input and watch which number moves — and which one refuses to.
Identical arithmetic, identical element count, identical complexity. Only the order changed. Column-major traversal of row-major storage touches a new line on essentially every access; tiling restores the reuse by keeping a block resident while it is used.
Struct Layout & Padding
Each field must sit at an address that is a multiple of its size, so the compiler inserts padding to get there. Twenty-four bytes to hold fourteen bytes of data, and in an array of a million records that is ten megabytes of nothing.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop order → address stream: the innermost loop index decides whether an operand is walked along a row (contiguous) or down a column (strided by a row length).
- 2Address stream → line requests: a column walk requests a distinct line per element, so useful bytes per transfer collapse to one element.
- 3Line requests → eviction: with a working set far larger than the cache, those lines are evicted before the next pass needs them (Cache Replacement: LRU Is the Idea, Not the Implementation).
- 4Eviction → re-fetch: the same elements are pulled from DRAM once per outer iteration, multiplying total transfers.
- 5Tiling → residency: bounding the inner nest to a block keeps its operands resident, so each transferred element is used many times before it leaves.
- • "The tiled version is doing less work" — it does exactly the same multiply-accumulates, plus slightly more loop bookkeeping.
- • "Tile size 64 is the right answer" — it is the right answer for some cache size and element type, and wrong for others.
- • "This only matters for matrix multiply" — the same restructuring applies to transposes, stencils, joins and any loop nest that revisits data.
- • "Once it is tiled, it is optimal" — a tiled kernel that does not vectorize or that thrashes the TLB is still leaving a large factor on the table.
Consequences, controls and cost
- • Naive matrix multiply on large inputs is memory-bound: the ALUs idle while DRAM delivers, and adding cores helps little because bandwidth is the constraint.
- • The tiled version approaches compute-bound, which is the state where more cores and wider vectors actually pay.
- • Runtime shows a sharp knee as matrix size grows past a cache level, and the knee moves when the tile size changes.
- • A tile size tuned on one machine can perform noticeably worse on another with different cache capacity.
- • Use a tuned library (BLAS and equivalents) rather than hand-writing this — they tile at multiple levels, vectorize and are tuned per target.
- • If you must write it, tile so that three blocks fit the target cache level with room for other traffic, and derive the size rather than hard-coding it.
- • Tile at more than one level for large problems: a coarse tile for the last-level cache, a finer one nested inside.
- • Check that the inner kernel vectorizes ([[auto-vectorization]]); a tiled loop that fails to vectorize leaves most of the win unclaimed.
- • Measure last-level misses, not just runtime, so you can see whether the transfers actually fell.
- • Compare last-level cache misses between the two versions at the same matrix size; the tiled version should show dramatically fewer for identical instruction counts.
- • Compute achieved arithmetic intensity — operations divided by bytes moved — and compare against the machine's balance point.
- • Sweep tile size and plot runtime; the curve should show a clear basin whose position reflects a cache capacity.
- • Watch instructions retired: if it barely moved while runtime halved, the win was transfers, exactly as claimed.
- • Six nested loops instead of three: substantially harder to read, verify and modify.
- • The tile size is a machine-dependent tuning parameter that silently degrades when hardware changes.
- • Edge handling for matrices that are not multiples of the tile size adds real code and real bugs.
- • Hand-tiling competes with mature tuned libraries and usually loses; the effort is often better spent calling one.
Scope
§224 — what these claims are specific to.
- PLATFORM-SPECIFICTile sizes depend on the target machine's cache capacity, line size and associativity, and on how much cache other threads consume; a constant tuned on one machine is often wrong on another.
- SIMPLIFIEDThe layout illustration uses a 64-byte line and 8-byte elements for concreteness. Line size is commonly but not universally 64 bytes, and element size depends on the numeric type.
- GENERALThe underlying principle — reuse data while it is resident to raise operations per byte transferred — holds on any machine with a cache hierarchy.
Misconceptions
i, k, j genuinely helps, because it makes the innermost access to B contiguous — it is a real and cheap improvement. But it does not create *reuse*: the working set is still the whole matrix, so large inputs still stream from DRAM. Blocking is what bounds the working set.