Skip to content

03 — matmul: Naive → Micro-Kernel (optim0 → optim8)

This tutorial walks the first half of the matmul ladder — from the naive triple loop to the register-blocked 4×4 micro-kernel.

The operation

We compute C = A·B + C, all matrices column-major (A(i,j) = a[j*lda + i]).

\[ C_{ij} \;\mathrel{+}=\; \sum_{p=0}^{k-1} A_{ip}\,B_{pj} \]

optim0 — the naive triple loop

for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
        for (p = 0; p < k; p++)
            C(i,j) += A(i,p) * B(p,j);

m*n*k dot products. Memory-bound: each output walks a full row of A and column of B, with strided access. Run it: ~1 GFLOPS.

optim1–2 — extract the dot product, then unroll

AddDot() captures the inner dot product. Unrolling the j loop by 4 computes four columns at once, exposing four independent accumulators and better ILP.

optim3–5 — the fused 1×4 kernel

AddDot1x4 computes a whole 1×4 row-tile in one pass over p, loading each A(i,p) once and reusing it for four B values. Register accumulators (optim4) stop touching C in the loop; pointer arithmetic (optim5) removes index multiplies.

optim6 — structural step: the 4×4 tile

AddDot4x4 builds a 4×4 block by calling AddDot sixteen times. It's slower but establishes the square output tile that everything else fills.

optim7 — fused 4×4 rank-1 kernel

One loop over p, updating all sixteen outputs:

\[ C \;\mathrel{+}=\; \sum_{p=0}^{k-1} \mathbf{a}_p\,\mathbf{b}_p^{T} \]

optim8 — fully register-tiled 4×4

All sixteen C accumulators live in registers for the whole p-loop, flushed once:

Bulk optim7 optim8
C traffic per tile compiler-dependent exactly 2·16
FMA chains (ILP) 16 16

This is the classic micro-kernel: a tight stream of sixteen independent FMA chains. Run ./build/matmat8.