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

Optimization 13 introduces PackMatrixA, which copies each 4×k row-panel of \(A\) into a contiguous packed buffer before the kernel consumes it. This removes the stride-lda jump that the AddDot4x1 kernel makes between columns, turning the matrix reads into dense, sequential loads. The mathematics is unchanged — packing is a pure permutation of bytes.

---

1. The Mathematical Operation (unchanged)

For \(r=0,1,2,3\):

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

---

2. The Problem: Strided Columns of A

In column-major layout, the four rows of the kernel's column slice at step \(p\) are contiguous:

\[ A(i,p),\;A(i+1,p),\;A(i+2,p),\;A(i+3,p) \;=\; a[p\text{lda}+i],\;a[p\text{lda}+i+1],\;a[p\text{lda}+i+2],\;a[p\text{lda}+i+3]. \]

But consecutive columns \(p, p+1\) are \(\text{lda}=2000\) doubles (16 KB) apart. Stepping \(p\to p+1\) jumps 16 KB — far beyond a 64-byte cache line — so the kernel's access stream is spread over a huge address range, wasting fetched cache lines and consuming TLB entries rapidly.

---

3. Packing: A Contiguous 4×k Repacking

PackMatrixA(k, a, lda, a_to) walks the 4×k panel column-by-column and writes an interleaved packed copy:

\[ \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 buffer satisfies:

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

Now the four rows at step \(p\) sit at packedA[4p..4p+3] — contiguous, exactly the slice the kernel wants, with no stride.

---

4. Where Packing Lives in the Blocked Flow

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

Combined with the mc×kc blocking of Optimization 12, each A-panel is packed once per mc-block; the copy cost is a one-time pass, far cheaper than the strided reads it replaces (sequential-write then sequential-read).

---

5. Copy Cost vs. Benefit

• Copy cost: copying the panel is \(O(\text{panel size})\) sequential work.
• Benefit: the kernel then reads the packed copy sequentially — perfect hardware prefetching, dense TLB footprint, no wasted cache lines.

Since \(A\) is streamed once anyway (matvec, memory-bound), the packing trades cheap sequential copies for dramatically better cache/prefetch/TLB behavior on the dominant matrix stream.

---

6. Note (Optimization 13 → 14)

In this level the kernel still uses &A(i,0) (the unpacked pointer) rather than the packed buffer — so the packed copy is produced but the kernel doesn't yet consume it. Optimization 14 completes the job by having the kernel read the packed buffer with raw += 4 pointer advances (lda = 4), eliminating the stride entirely.

---

7. Summary

Metric	Optim 12	Optim 13
Kernel	AddDot4x1	AddDot4x1
A access	strided columns	packed contiguous
Packing pass	none	per A-panel
Values computed	identical	identical
Memory traffic	strided	sequential reads

Optimization 13 packages the strided A stream into dense contiguous runs so the blocking of Optimization 12 can be exploited without cache-line wastage. Its full payoff is realized in Optimization 14, where the kernel actually consumes the packed buffer.