Skip to content

Complete Mathematics of "Optimization 6: The 4×4 Kernel (via AddDot calls)"

Optimization 6 expands the micro-kernel from a 1×4 row (Optimization 2–5) to a 4×4 block of \(C\). Rather than fusing everything at once, it builds the block by calling the original AddDot routine sixteen times — one per element of the \(4×4\) tile. This is deliberately a correctness-first structural step; the fused, register-bound version comes in Optimization 7–8.

1. The Mathematical Operation

For a \(4×4\) block of \(C\) located at rows \(i, i+1, i+2, i+3\) and columns \(j, j+1, j+2, j+3\):

\[ C_{i+r,\,j+c} \;\mathrel{+}=\; \sum_{p=0}^{k-1} A_{i+r,\,p}\, B_{p,\,j+c}, \qquad r = 0,1,2,3,\;\; c = 0,1,2,3. \]

In block form, with

\[ \mathbf{C} = \begin{bmatrix} C_{i,j} & C_{i,j+1} & C_{i,j+2} & C_{i,j+3} \\ C_{i+1,j} & \cdots \\ C_{i+2,j} & \cdots \\ C_{i+3,j} & \cdots \end{bmatrix}, \quad \mathbf{A} = \begin{bmatrix} A_{i,:} \\ A_{i+1,:} \\ A_{i+2,:} \\ A_{i+3,:} \end{bmatrix}, \quad \mathbf{B} = \begin{bmatrix} B_{:,j} & B_{:,j+1} & B_{:,j+2} & B_{:,j+3} \end{bmatrix}, \]

this is the block-matrix product

\[ \mathbf{C} \;\mathrel{+}=\; \mathbf{A} \cdot \mathbf{B}, \qquad \mathbf{A}\in\mathbb{R}^{4\times k},\ \mathbf{B}\in\mathbb{R}^{k\times4},\ \mathbf{C}\in\mathbb{R}^{4\times4}. \]

2. Construction by Sixteen Dot Products

The code's AddDot4x4 fills the tile by calling AddDot sixteen times:

AddDot(k,&A(0,0),lda,&B(0,0),&C(0,0));   // (r=0,c=0)
AddDot(k,&A(0,0),lda,&B(0,1),&C(0,1));   // (r=0,c=1)
...
AddDot(k,&A(3,0),lda,&B(0,3),&C(3,3));   // (r=3,c=3)

Each AddDot computes a scalar dot product:

\[ \gamma_{rc}^{(p+1)} = \gamma_{rc}^{(p)} + A_{r,p}B_{p,c}, \qquad C(i+r,j+c) \mathrel{+}= \gamma_{rc}^{(k-1)}, \]

i.e. the standard row-\(\times\)-column dot product for every \((r,c)\).

3. Loop Structure

The outer loops now tile both dimensions:

for (j = 0; j < n; j += 4)
    for (i = 0; i < m; i += 4)
        AddDot4x4(k, &A(i,0), lda, &B(0,j), ldb, &C(i,j), ldc);

Number of tile calls:

\[ \#\text{tiles} = \frac{m}{4}\cdot\frac{n}{4} = \frac{mn}{16}. \]

Each tile performs \(16\) dots of length \(k\), so total dots \(= \frac{mn}{16}\cdot 16 = mn\), and total FLOPs remain \(2mnk\).

4. Data Reuse Introduced by the 4×4 Tile

The block formulation lets us count reuse per tile:

  • A-panel: \(4\) rows of length \(k\) \(\Rightarrow\) \(4k\) elements, each read \(4\) times (once per column \(c\)).
  • B-panel: \(4\) columns of length \(k\) \(\Rightarrow\) \(4k\) elements, each read \(4\) times (once per row \(r\)).

Per tile, the input is \(8k\) elements used to produce \(4\cdot4=16\) outputs, each requiring a length-\(k\) dot. This is the seed of the register-blocking idea: a \(4×4\) accumulator tile lets every loaded \(A\) element and every loaded \(B\) element be reused 4 times before leaving the registers.

5. Why It Regresses (and Why It's Still Valuable)

Calling AddDot sixteen times discards the register-caching of the accumulators (Optimization 4–5): each AddDot writes its result through memory via *gamma. So per tile:

  • \(16\) function calls;
  • \(16k\) loads + \(16k\) stores of \(C\) through memory (back to the Optimization 3 pattern);
  • the same row of \(A\) (&A(r,0)) is loaded once per column \(c\), i.e. \(4\) redundant traversals of each A row.

This version is therefore slower than Optimization 5 in practice. Its purpose is purely structural: it establishes the correct 4×4 output register tile that the subsequent, fused versions optimize. It is a stepping stone, not a performance peak.

6. Summary

Metric Optim 5 (1×4) Optim 6 (4×4, byAddDot)
Kernel shape \(1\times4\) \(4\times4\)
\(C\) tile accumulators 4 registers 16 memory writes
FLOPs \(2mnk\) \(2mnk\)
per-element A reuse 4 4
per-element B reuse 1 4
Primary goal performance correctness + structure

Mathematically, Optimization 6 is just the block product \(\mathbf{C} \mathrel{+}= \mathbf{A}_{4\times k}\mathbf{B}_{k\times4}\) decomposed into sixteen scalar dot products. Its real contribution is defining the 4×4 register tile that later versions fill efficiently.