hpc · advanced

Cache blocking & loop tiling

On modern CPUs arithmetic is cheap and memory is the bottleneck — a DRAM miss costs ~50x an L1 hit — so performance is about reusing data while it's still in cache (high arithmetic intensity). Naive i-j-k matrix multiply walks B down a column: with row-major storage that's a stride-N access that misses cache on every step once N exceeds the cache, turning O(N^3) compute into O(N^3) memory traffic. Cache blocking (tiling) restructures the loops to work on BxB sub-tiles small enough that the active tiles fit in L1/L2, so each loaded tile is fully reused before eviction. Combined with a unit-stride loop order (i-k-j) and SIMD vectorization of the contiguous inner loop, this is the structure of every high-performance GEMM — which in practice you get from a tuned BLAS (OpenBLAS, MKL) or Eigen.

The code

// Naive matrix multiply: C = A * B  (N x N)
for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    for (int k = 0; k < N; ++k)
      C[i][j] += A[i][k] * B[k][j];   // B[k][j] strides DOWN a column

// Blocked (tiled): work on BxB sub-tiles that fit in L1/L2
for (int ii = 0; ii < N; ii += B)
  for (int jj = 0; jj < N; jj += B)
    for (int kk = 0; kk < N; kk += B)
      // ... multiply the BxB tile, reusing it from cache ...

What this lesson walks through

1. 01The memory wall — FLOPs are free, data isn't
2. 02Naive matmul thrashes the cache
3. 03Tiling — shrink the working set to fit cache
4. 04Loop order + blocking + SIMD together

A modern core does many arithmetic ops in the time of one cache miss to DRAM. So performance is set by how well data fits in cache, not by the number of multiplies.