Complete Mathematics of "Optimization 3: The Fused `AddDot1x4` Micro-Kernel"¶

Optimization 2 called AddDot four separate times to compute the four adjacent columns of \(C\) for a fixed row \(i\). Optimization 3 replaces those four function calls with a single fused kernel AddDot1x4 that computes all four accumulators in one pass over \(p\). This is the first genuine micro-kernel in the ladder.

1. The Mathematical Operation¶

The kernel computes, for a fixed row \(i\) and four consecutive columns \(j, j+1, j+2, j+3\):

\[ \boxed{\; C_{i,\,j+c} \;\mathrel{+}=\; \sum_{p=0}^{k-1} A_{i,p} \cdot B_{p,\,j+c} \quad \text{for } c = 0,1,2,3 \;} \]

which can be written as a rank-1 vector update in the \(p\) loop:

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

2. Fusing the Four Loops¶

2.1 Optimization 2 (four separate `AddDot` calls)¶

Each call runs a full loop of length \(k\):

for p:  C(i,j)   += A(i,p)*B(p,j)      // loop 1
for p:  C(i,j+1) += A(i,p)*B(p,j+1)    // loop 2
for p:  C(i,j+2) += A(i,p)*B(p,j+2)    // loop 3
for p:  C(i,j+3) += A(i,p)*B(p,j+3)    // loop 4

Critical redundancy: The element \(A_{i,p}\) is reloaded from memory/registers four times — once per loop. Similarly, the loop counter, branch overhead, and address computation for \(A\) are repeated four times.

2.2 Optimization 3 (single fused loop)¶

for p:
    C(i,j)   += A(i,p)*B(p,j)
    C(i,j+1) += A(i,p)*B(p,j+1)
    C(i,j+2) += A(i,p)*B(p,j+2)
    C(i,j+3) += A(i,p)*B(p,j+3)

Now \(A_{i,p}\) is loaded exactly once per \(p\) iteration and reused for all four products.

3. Savings From Fusing¶

Resource	Optim 2 (4 calls)	Optim 3 (fused)	Saving
Loop trips over\(p\)	\(4k\)	\(k\)	\(3k\) fewer
Loads of\(A_{i,p}\)	\(4k\)	\(k\)	\(3k\) fewer
Function-call overhead	\(4\) per \((i,j)\) tile	\(1\) per \((i,j)\) tile	\(3\) fewer
Loop-branch/pointer updates	\(4k\)	\(k\)	\(3k\) fewer

Total arithmetic is unchanged: still \(2mnk\) FLOPs.

4. Memory Access Inside the Kernel (Column-Major)¶

Using the column-major macros:

\[ A(i,p) = a[p \cdot \text{lda} + i], \qquad B(p,c) = b[c \cdot \text{ldb} + p], \qquad C(i,c) = c[c \cdot \text{ldc} + i]. \]

Inside the \(p\) loop (fixed \(i\), varying \(p\)):

Access	Address expression	Stride
\(A_{i,p}\)	\(p \cdot \text{lda} + i\)	\(\text{lda}=m\) (strided)
\(B_{p,\,j+c}\)	\((j+c)\cdot \text{ldb} + p\)	\(1\) (contiguous) for each \(c\)
\(C_{i,\,j+c}\)	\((j+c)\cdot \text{ldc} + i\)	single location each

So four contiguous streams of \(B\) (one per column \(c\)) feed four FMA chains, all multiplied by the same strided scalar \(A_{i,p}\).

5. Why This Is a Micro-Kernel¶

A micro-kernel is the innermost computational engine that the rest of the algorithm repackages data for. Here the kernel consumes:

one row of \(A\): \(\mathbf{a}_i = [A_{i,0}, \dots, A_{i,k-1}]\),
a \(k \times 4\) panel of \(B\): the four columns \(j \dots j+3\),
and produces a \(1 \times 4\) row of \(C\).

Its shape \(1 \times 4\) is deliberately chosen to map onto four independent accumulator registers that we will keep in registers in the next step.

6. Summary¶

The operation is mathematically identical to Optimization 2.
The innovation is code fusion: one loop over \(p\) instead of four, loading each \(A_{i,p}\) once.
This removes redundant loads and loop overhead, and sets the stage for keeping the four \(C\) accumulators entirely in registers (Optimization 4).

Complete Mathematics of "Optimization 3: The Fused AddDot1x4 Micro-Kernel"¶