Complete Mathematics of "Optimization 13: Packing the A Panel"

Optimization 12 blocked the computation into mc × kc A-panels, but the 4×4 kernel still read those panels directly from the strided column-major A layout. Optimization 13 introduces PackMatrixA, which copies each A-panel into a contiguous, kernel-friendly buffer before the kernel runs. This removes the strided-access penalty that has persisted since Optimization 1.

---

1. The Mathematical Operation (unchanged)

Still:

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

Packing does not change a single value — it only relocates the bytes of A into a different memory arrangement, so every computed element is identical.

---

2. The Problem: Strided Access to A

In the column-major layout, the four rows of a 4×4 tile in column \(p\) are four contiguous doubles:

\[ A(i,p),\; A(i+1,p),\; A(i+2,p),\; A(i+3,p) \quad \text{(contiguous, 32 bytes)}. \]

But the next column \(p+1\) starts at offset \(p\text{lda}+i\), i.e. \(\text{lda}\) doubles away. Stepping through \(p\) means jumping \(\text{lda}\cdot 8\) bytes each time:

\[ \text{stride} = \text{lda} \text{ doubles} = 2000 \cdot 8\text{ B} = 16\text{ KB}. \]

This stride is far larger than a cache line (64 B), so each A element pull wastes most of the fetched cache line, and TLB entries are consumed rapidly.

---

3. Packing: Restructuring A into Contiguous 4×k Runs

PackMatrixA(k, a, lda, a_to) walks the panel in column-major order and writes a contiguous packed copy. For the \(4×k\) block at rows \(i..i+3\):

\[ \underbrace{A(i,0)\;A(i+1,0)\;A(i+2,0)\;A(i+3,0)}_{\text{col 0}} \underbrace{A(i,1)\,A(i+1,1)\,A(i+2,1)\,A(i+3,1)}_{\text{col 1}} \;\cdots\; \]

i.e. the packed array stores, for the block, the interleaved sequence:

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

Now the four rows needed at step \(p\) are at packedA[4p..4p+3] — contiguous, no stride.

---

4. Data Reuse / Copy Cost

Packing copies the A-panel once per mc-block, then the kernel reads the packed copy. The copy cost is proportional to the panel size:

\[ \text{copy traffic (A)} = \underbrace{mk}_{A}\;\text{per } \frac{m}{\texttt{mc}}\text{-pass} \;\approx\; O\!\Big(\frac{mkn}{\texttt{mc}}\Big). \]

This is small relative to the arithmetic \(2mnk\) and, crucially, the packed reads are sequential (perfect prefetch, few TLB misses), so the copy is far cheaper than the strided reads it replaces.

---

5. Correctness of the Packed Kernel

Because the packed buffer is a pure permutation of the original panel — a bijection \(p'\neq p \Rightarrow \text{different bytes}\), and every element is present exactly once — the kernel's reads

\[ \sum_{p}\mathbf{a}_p\mathbf{b}_p^T \]

use exactly the same \(\mathbf{a}_p\) vectors as before. The mathematical result is bit-identical.

---

6. What Packing Enables

1. Sequential loads for both A and B, activating hardware prefetch.
2. Fewer TLB misses (dense, localized address space).
3. Optionally 16-byte alignment of the packed rows, satisfying aligned-SIMD loads.
4. A clean path to Optimization 14, which reads the fully packed buffer with plain pointer increments (no lda arithmetic at all).

---

7. Summary

Metric	Optim 12	Optim 13
Kernel	SSE 4×4	SSE 4×4
A access	strided (lda)	packed contiguous
A copy pass	none	one per mc-block
Memory traffic	\(O(mnk)\) strided	\(O(mnk)\) but sequential
Values computed	identical	identical

Optimization 13 removes the last persistent memory-pattern flaw: instead of the kernel chasing 16 KB strided jumps through A, it consumes a dense, contiguous panel. Packing trades a cheap one-time copy for dramatically better cache/TLB behavior, making the compute-bound kernel actually run at compute-bound speeds.