Complete Mathematics of "Optimization 12: Cache Blocking over the Reduction Dimension (kc) and Rows (mc)"¶

Optimization 12 introduces the same blocking structure as matmul's Optimization 12 — tiling the \(k\)- and \(m\)-loops into panels with \(\texttt{mc}=256\), \(\texttt{kc}=128\) — but applied to the matrix–vector product. Because matvec is memory-bound, the benefit here is subtler than in matmul: blocking improves cache/TLB locality of the matrix and vector slices rather than enabling operand reuse.

1. The Mathematical Operation (unchanged globally)¶

Still, for all \(i\):

\[ y_i \;\leftarrow\; \sum_{p=0}^{k-1} A_{i,p}\,x_p + y_i. \]

1.1 Repartition over the reduction index¶

Grouping the sum over \(p\) into blocks of width \(\texttt{kc}\):

\[ y_i \;=\; \sum_{b=0}^{k/\texttt{kc}-1}\;\; \sum_{p=b\,\texttt{kc}}^{(b+1)\texttt{kc}-1} A_{i,p}\,x_p \;+\; y_i. \]

This is mathematically identical — each \(p\) contributes one additive term, and grouping changes only the summation order.

2. The Three-Level Loop Structure¶

for (p = 0; p < k; p += kc) {          // k-panels
    pb = min(k-p, kc);
    for (i = 0; i < m; i += mc) {      // mc x kc blocks
        ib = min(m-i, mc);
        InnerKernel_(ib, pb, &A(i,p), lda, &x[p], &y[i]);
    }
}

InnerKernel_ runs the AddDot4x1 kernel over the ib × pb sub-panel, the pb-slice of x, and the ib-slice of y:

void InnerKernel_(int m, int k, double *a, int lda, double *x, double *y){
    for (i = 0; i < m; i += 4)
        AddDot4x1(k, &A(i,0), lda, x, &y[i]);
}

3. Why Block in a Memory-Bound Kernel?¶

3.1 In matmul, blocking creates reuse¶

In matmul, an mc × kc A-panel element is reused across many \(j\)-positions, so blocking cuts DRAM traffic by \(O(n)\). That huge win does not transfer to matvec: each \(A\) element is used once regardless of tiling.

3.2 In matvec, blocking improves locality and TLB/pf behavior¶

What matvec does gain:

x-slice locality: processing a kc-deep slice of x (\(\texttt{kc}\) doubles \(=1\) KB) keeps that part of x in L1 across an entire mc column-block, avoiding repeated full-vector DRAM sweeps.
A-panel locality: the m-loop over an ib-deep panel confines the working set; with \(\texttt{mc}=256\) the panel is \(256\times\texttt{kc}\) doubles.
Fewer TLB entries: blocked panels have a compact address footprint vs. touching the entire matrix column-descendingly.

3.3 Working set inside the p-block¶

For a p-block of width kc and the inner i-loop:

\[ \text{working set} \approx \underbrace{\texttt{mc}\cdot\texttt{kc}}_{\text{A panel}} \;+\;\underbrace{\texttt{kc}}_{\text{x slice}} \;+\;\underbrace{\texttt{mc}}_{\text{y slice}}. \]

With \(\texttt{mc}=256,\texttt{kc}=128\): A \(\approx 256\times128\times8=256\) KB — a size chosen to sit in typical L2.

4. Correctness of the Blocked Order¶

Because every output accumulates over all \(p\) via independent additive terms, spliting the reduction into kc-blocks and summing in sequence yields the same value:

\[ \sum_{p=0}^{k-1}(\cdots) \;=\; \sum_{b}\sum_{p\in \text{block }b}(\cdots). \]

The kernel itself (AddDot4x1) is unchanged — it just operates on pb-deep panels now.

5. Summary¶

Metric	Optim 11	Optim 12
Kernel	4-output auto-vectorized	same kernel
Blocking	none	kc=128, mc=256
x access	full vector per kernel	kc-slice, cache-resident
A access	whole matrix	mc×kc panels
FLOPs	\(2mk\)	\(2mk\)
Main win	(vectorization)	cache/TLB locality

Whereas blocking is the decisive optimization for matmul's data reuse, for matvec it is a locality refinement: it keeps the relevant slices of x and tiles of A cache-resident and reduces TLB pressure, complementing (rather than replacing) the vectorized kernel. It sets up the panel-based packing of Optimization 13–14.