Skip to content

Complete Mathematics of "Optimization 12: Cache Blocking (mc × kc Panels)"

Optimization 12 is the first change to the overall structure rather than the kernel. It introduces cache blocking: the \(k\)-loop and \(m\)-loop are tiled into panels of height \(\texttt{mc}=256\) and width \(\texttt{kc}=128\), and the 4×4 SSE kernel operates on one small panel at a time. The goal is to make the working set fit in cache.

1. The Mathematical Operation (unchanged globally)

Still the full block product, but re-expressed by partitioning the summation over \(p\):

\[ \mathbf{C} = \sum_{p=0}^{k-1} \mathbf{a}_p\mathbf{b}_p^T = \sum_{pblock=0}^{k/\texttt{kc}-1}\;\; \sum_{p=pblock\cdot\texttt{kc}}^{(pblock+1)\texttt{kc}-1} \mathbf{a}_p\mathbf{b}_p^T . \]

This is always valid because each \(p\) contributes an independent rank-1 term; grouping them in blocks of \(\texttt{kc}\) changes only the order of accumulation.

2. The Three-Level Loop Structure

The matmul routine becomes:

for (p = 0; p < k; p += kc) {          // C-level: k-panel
    for (i = 0; i < m; i += mc) {      // M-level: mc x kc block
        InnerKernel_(ib, n, pb, &A(i,p), &B(p,0), &C(i,0));
    }
}

where pb = min(k-p, kc) and ib = min(m-i, mc) handle ragged edges, and InnerKernel_ runs the 4×4 kernel over an ib × n output slab using the pb-deep panel of \(A\) and \(B\).

3. Why Blocking Helps: Roofline Revisited

3.1 The problem before blocking

The naive/earlier kernels re-scan \(A\) and \(B\) for every \(4×4\) tile. For a fixed block of \(C\) of size \(\texttt{mc}\times n\), the required inputs are:

  • an \(\texttt{mc}\times\texttt{kc}\) panel of \(A\),
  • a \(\texttt{kc}\times n\) panel of \(B\).

If these panels are kept in cache, then every element of each panel is reused many times before it is evicted — this is the whole point of the classic GAXPY/blocked decomposition.

3.2 Working-set size

For the \(p\)-loop with block size \(\texttt{kc}\), the inner InnerKernel_ reads:

\[ \text{working set} \approx \texttt{mc}\cdot\texttt{kc}\;( \text{A panel}) \;+\; \texttt{kc}\cdot n \;(\text{B panel}) \;+\; \texttt{mc}\cdot n\;(\text{C slab}). \]

With \(\texttt{mc}=256\), \(\texttt{kc}=128\), and a B panel \(128\times2000\):

  • A panel: \(256\times128 \times 8\text{ B} = 256\text{ KB}\),
  • B panel: \(128\times2000 \times 8\text{ B} = 2048\text{ KB}\),
  • C slab: \(256\times2000\times 8\text{ B} = 4096\text{ KB}\).

These are chosen relative to typical L2/L3 cache sizes so that the hot panels stream from cache rather than DRAM.

4. Memory-Efficiency Metric: Flops per Byte

The data movement of the whole multiplication with blocking is approximately:

\[ \text{Traffic} \approx \underbrace{mk}_{\text{A read once per C-panel restart}} \;+\; \underbrace{\frac{m}{\texttt{mc}}\,k\,n}_{\text{B}} \;+\;\text{(C traffic)} = O\!\Big(mn + nk + \frac{mkn}{\texttt{mc}}\Big). \]

Compare the naive \(O(mnk)\). Blocking reduces the \(B\)-traffic by a factor of \(\texttt{mc}\) and confines A-panel re-reading to per-panel granularity.

4.1 Arithmetic intensity

\[ I = \frac{2mnk}{\text{Traffic}(\texttt{mc},\texttt{kc})} \;\approx\; \frac{2\,\texttt{mc}}{1+1/\texttt{kc}+\dots} \]

which is now large (roughly \(O(\texttt{mc})\), \(I \gg 1\) FLOP/byte), moving the algorithm from memory-bound to compute-bound.

5. The Inner Kernel Stays Identical

InnerKernel_ is structurally the same SSE 4×4 kernel binding as Optimization 11; it just operates over sub-panels A(i:p+ib, p:p+pb), etc. Because the kernel itself is unchanged, correctness is preserved: the blocked order still sums all \(k\) rank-1 terms into each \(C\) element.

6. Block-Size Trade-offs

  • \(\texttt{mc}\) large → fewer B re-reads, but larger C slab that may overflow cache.
  • \(\texttt{kc}\) large → more reuse of each A element per inner loop, but bigger registers/working set.
  • The chosen \((\texttt{mc},\texttt{kc})=(256,128)\) balances these against typical cache hierarchies.

7. Summary

Metric Optim 11 Optim 12
Kernel SSE 4×4 SSE 4×4 (unchanged)
Loop tiling none kc=128, mc=256
Working set whole matrices A/B/C panels
Memory traffic \(O(mnk)\) \(O(mn + nk + mkn/\texttt{mc})\)
Arithmetic intensity low high (compute-bound)

Optimization 12 keeps the same micro-kernel but reorganizes the outer loops so that panels of \(A\), \(B\), and \(C\) are reused from cache. This is the structural optimization that converts a memory-bound kernel into a compute-bound one, and it is the foundation for the packing step that follows.