Complete Mathematics of "Optimization 14: Full Packing + Pointer-Based Kernel"¶

Optimization 14 is the final maturity of the micro-kernel ladder. It packs both panels (\(A\) and \(B\)) into dense contiguous buffers and rewrites the 4×4 kernel to read them purely via raw pointer increments — no lda/ldb indexing, no strided jumps anywhere in the hot loop. The kernel becomes a tight stream of vector FMAs over contiguous memory.

1. The Mathematical Operation (unchanged)¶

Still:

\[ \mathbf{C} \;\mathrel{+}=\; \mathbf{A}_{4\times k}\,\mathbf{B}_{k\times4}\;=\;\sum_{p=0}^{k-1}\mathbf{a}_p\,\mathbf{b}_p^{T}. \]

2. Packing Both Matrices¶

2.1 Pack A (as in Optimization 13)¶

For the 4×k block at rows \(i..i+3\), PackMatrixA emits:

\[ \texttt{packedA}[4p + r] = A(i+r,\;p), \qquad 0\le p<k,\;0\le r\le 3. \]

2.2 Pack B (new)¶

PackMatrixB handles the k×4 block at columns \(j..j+3\). In column-major layout the four columns for row \(p\) are:

\[ B(p,j),\; B(p,j+1),\; B(p,j+2),\; B(p,j+3), \]

which are at addresses \(j\text{ldb}+p,\;(j+1)\text{ldb}+p,\;\dots\) — i.e. strided by ldb. Packing copies them into a contiguous run per row:

\[ \texttt{packedB}[4p + c] = B(p,\;j+c), \qquad 0\le p<k,\;0\le c\le 3. \]

Now the four B values for step \(p\) are contiguous at packedB[4p..4p+3].

3. The Pointer-Based Kernel¶

With both panels packed, the kernel keeps four pointers into packedB and reads packedA directly:

3.1 A read — pure advance¶

The two vector registers for A are loaded from packedA, then the pointer advances by a fixed 4 doubles (one full 4-row group):

\[ \mathbf{a}_{0,1}(p) = \texttt{load\_pd}(a),\qquad \mathbf{a}_{2,3}(p) = \texttt{load\_pd}(a+2),\qquad a \;\leftarrow\; a + 4. \]

No lda appears anywhere.

3.2 B read — contiguous broadcasts¶

The four B scalars are loaded from four contiguous doubles and broadcast to both lanes:

\[ \mathbf{b}_c(p) = \texttt{loaddup\_pd}\big(\texttt{packedB}[4p+c]\big),\qquad b \;\leftarrow\; b+4. \]

Each step advances B by 4 doubles — a simple constant increment.

3.3 Accumulation¶

The eight vector accumulators update exactly as in Optimization 11:

\[ \mathbf{\Gamma}_{rc} \;\mathrel{+}=\; \mathbf{a}_r(p)\cdot\mathbf{b}_c(p). \]

4. The Full Pipeline¶

InnerKernel orchestrates packing + kernel per panel:

for (j = 0; j < n; j += 4) {
    if (first_time) PackMatrixB(k, &B(0,j), ldb, &packedB[j*k]);
    for (i = 0; i < m; i += 4) {
        if (j == 0) PackMatrixA(k, &A(i,0), lda, &packedA[i*k]);
        AddDot4x4(k, &packedA[i*k], 4, &packedB[j*k], k, &C(i,j), ldc);
    }
}

The AddDot4x4 call now passes packedA/packedB buffers where both leading dimensions collapse to 4, so the kernel's pointer arithmetic is uniform and stride-free.

5. Memory / Performance Balance¶

Copy cost: packing \(A\) and \(B\) happens once per mc/nb block; the cost is \(O(mkn/\texttt{mc})\) for A and \(O(kn)\) for B — negligible next to \(2mnk\).
Kernel behavior: all loads are sequential; the kernel is a pure compute-bound stream hitting near-peak FMA throughput.
Residual: the packed buffers used here (calloc per InnerKernel) add allocation overhead in this pedagogical version; a production GotoBLAS would use pre-allocated, reusable buffers and register-tile 6×8/8×12. The mathematics and packing principle are identical.

6. Summary Table — The Complete Ladder¶

Level	Core idea	A access	B access	A/B reused
optim0–2	naive dot / unroll	strided	contiguous	no
optim3–5	fused `1×4`, registers, pointers	strided	contiguous	partial
optim6	`4×4` via 16 dots	strided	strided	no
optim7–8	fused `4×4`, 16 registers	strided	strided	4×4 tile
optim9–10	pointer A + reorder	strided	contiguous	4×4 tile
optim11	SSE vectorization	strided	dup	4×4 tile
optim12	cache blocking	strided	panel	panel reuse
optim13	pack A	packed	strided	packed reuse
optim14	pack A + B, pointer kernel	packed	packed	dense stream

7. Conclusion¶

Optimization 14 realizes the mathematical structure of the fast rank-1 accumulation

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

as a fully packed, pointer-driven, vectorized, cache-blocked micro-kernel: both operands stream contiguously from dense buffers, the sixteen (vectorized to eight) accumulators live in registers, and every load is sequential. This is the shape that modern BLAS libraries approach, giving near-peak performance on general-purpose CPUs.