Matrix multiplication is usually introduced as a compact equation:
C = A × B
That notation hides the part that matters to real machines. A large multiplication is not one indivisible operation. It is a long sequence of reads, multiply-adds, partial sums, and writes. Performance depends heavily on the order in which those operations visit memory.
Open the interactive tiled matrix multiplication demo
The demo lets you advance one operation, one K tile, or one C tile at a time. Try the row-column and outer-product modes, then change the matrix size, tile size, data type, and memory layout.
Start with one result element
Let A have shape M × K and B have shape K × N. The result C has shape M × N. One result element is a dot product:
C[i,j] = sum over k of A[i,k] × B[k,j]
To compute C[i,j], we walk across row i of A, down column j of B, multiply corresponding values, and accumulate the products.
For a tiny matrix this description is enough. For a large matrix, repeatedly walking complete rows and columns can waste the cache. Values that were loaded moments ago may be evicted before the next result element needs them.
The arithmetic has not changed. The problem is the order in which data travels through the memory hierarchy.
Why large matrices are divided into tiles
A tile is a small rectangular region of a matrix. Instead of treating all of A, B, and C as single giant arrays, a tiled algorithm works on pieces chosen to remain useful in cache or registers.
For one output tile, the algorithm repeatedly combines:
- a tile from the same row region of A,
- a tile from the same column region of B, and
- the current partial values in the output tile.
A simplified loop structure looks like this:
for each row tile ii
for each column tile jj
keep C[ii, jj] active
for each reduction tile kk
C[ii, jj] += A[ii, kk] × B[kk, jj]
The kk loop is the tiled version of the summation over k. Each pass adds another partial contribution. Only after every K tile has contributed is that C tile complete.
If the dimensions are not exact multiples of the tile size, the tiles on the bottom or right edges are smaller. Good implementations handle these edge tiles with bounds checks or vector predicates rather than padding the entire matrix.
Row-column and outer-product views
There are two complementary ways to view the same multiplication.
Row-column: finish one dot product
The familiar view chooses one output cell and accumulates products along k:
C[i,j] += A[i,k] × B[k,j]
This is an excellent way to understand where one element of C comes from. In the demo, row-column mode highlights the active A row slice, B column slice, and C cell.
Outer product: update many C elements together
For a fixed k, take column k of A and row k of B:
C += A[:,k] outer-product B[k,:]
Their outer product creates a rank-1 contribution to many C elements at once. Inside a tile, this becomes:
C_tile += A[tile_rows,k] outer-product B[k,tile_columns]
The demo’s outer-product micro-step shows an A sub-vector and a B sub-vector producing a small grid of products, which is then accumulated into the active C tile.
These are not different answers or different matrix products. They are different loop organizations and different mental models for the same arithmetic.
The cache-line view
Processors usually move memory in cache lines, not one scalar at a time. The demo assumes a 64-byte cache line and lets you change the element type.
For 32-bit floating-point values, one cache line holds 16 adjacent elements. Whether those elements are useful depends on layout:
- In row-major layout, elements from the same row are contiguous.
- In column-major layout, elements from the same column are contiguous.
- A row traversal through a row-major matrix tends to use each fetched line well.
- A column traversal through that same matrix may jump between distant lines.
This is why the demo exposes independent layouts for A, B, and C. Switch B between row-major and column-major while watching the heatmap. The mathematical operation stays identical, but the highlighted addresses and cache lines change dramatically.
Production GEMM libraries often pack matrix panels into temporary contiguous layouts. Packing costs time, but it can turn irregular or strided access into predictable streams that are reused across many multiply-adds.
Choosing a tile size
There is no universally optimal tile size. It depends on:
- cache sizes and associativity,
- register or matrix-accumulator capacity,
- vector width,
- element type,
- matrix dimensions,
- number of threads, and
- the packing strategy.
A tile that is too small creates excessive loop and bookkeeping overhead. A tile that is too large spills useful data out of the intended cache level or register file.
Real high-performance implementations therefore use several levels of blocking: large panels for shared caches, smaller tiles for private caches, and microtiles sized for registers or specialized matrix hardware.
What the animation is really showing
The colors are a trace of data movement and ownership:
- active reads identify values fetched from A and B,
- active writes identify the C element or tile being updated,
- completed regions have received every required K contribution,
- unused regions are irrelevant to the current step, and
- the tile-order maps show where the algorithm will move next.
Advance one scalar step to follow the exact arithmetic. Then advance by a K tile or C tile to see the hierarchy of work. That jump from scalar operations to structured blocks is the central idea behind practical matrix multiplication.
The key lesson
Tiling does not reduce the fundamental 2 × M × N × K floating-point work of dense matrix multiplication. It reorganizes that work so data is reused near the processor instead of fetched repeatedly from slower memory.
The equation stays simple. The implementation becomes fast by respecting where the data lives.
Launch the tiled matrix multiplication visualizer
Next: how to give C tiles to threads without creating write races.