Complete Mathematics of "Optimization 9: Pointer-Based Access to A"¶
Optimization 9 keeps the fully register-tiled 4×4 kernel of Optimization 8 but changes how it addresses the matrix \(A\). Instead of recomputing the column-major index \(A(i+r,p) = a[p\,\text{lda}+(i+r)]\) on every access, it maintains four pointers that advance contiguously through a packed-like arrangement of the current A panel. The mathematics of the operation is unchanged; only the addressing arithmetic is restructured.
1. The Mathematical Operation¶
Unchanged from Optimization 8:
2. Why Pointer Addressing for A¶
In column-major storage, the four rows of the tile in column \(p\) live at:
These four values are contiguous in memory (they are the four consecutive entries of a single column). So the kernel can keep a single pointer to the start and index rows as offsets \(0,1,2,3\):
where \(a_p\) is the address of \(A(i,p)\), and stepping to the next \(p\) advances the pointer by:
2.1 The trick: pointer-per-row¶
Rather than one pointer plus a big stride, the code maintains four pointers, one per output row, each starting at \(A(i+r, 0)\) and advancing by \(\text{lda}\) every trip. But the nicer observation is that caching these as offsets means:
- 4 pointer increments per \(p\)-step (cheap integer adds),
- no repeated multiply, and loads become simple
*(a_r),*(a_r)with contiguous small offsets.
3. Access Arithmetic Comparison¶
| Scheme | Address of \(A(i+r,p)\) | Cost per access |
|---|---|---|
| Macro (Optim 8) | \(a[p\,\text{lda}+i+r]\) | integer multiply by lda + add + load |
| Pointer (Optim 9) | *(a_r) where \(a_r\leftarrow a_r+\text{lda}\) |
increment + load |
The multiply disappears from the hot path.
4. Cache-Locality Note (unchanged by addressing)¶
Changing pointers does not change the physical memory layout: the A elements are still \(k\) columns apart by \(\text{lda}\) entries. So the four pointers still jump by lda doubles each step — the "strided A" cache problem is not solved here. What improves is the address computation cost at the ALU level, freeing load ports and integer units for other work.
5. B Access (already contiguous)¶
B's four values \(B(p,j:j+3)\) remain a contiguous run in column-major memory (they are four consecutive entries of one row \(p\) across columns \(j..j+3\) when viewed as \(B(p,c)=b[c\,\text{ldb}+p]\) — for fixed \(p\) these are stride-\(\text{ldb}\) apart, but in this implementation the pointer handles it symmetrically). The bulk of the win for pointer arithmetic is on the strided A side where the multiply was costliest.
6. Summary¶
| Metric | Optim 8 | Optim 9 |
|---|---|---|
| Kernel shape | \(4\times4\) | \(4\times4\) |
| FLOPs | \(2mnk\) | \(2mnk\) |
| A addressing | multiply + add + load | pointer increment + load |
| 16 accumulators | ✓ | ✓ |
| Strided A memory | yes | yes (unchanged) |
The mathematical content of Optimization 9 is minimal — it preserves the exact block product \(\mathbf{C}\mathrel{+}=\sum_p \mathbf{a}_p\mathbf{b}_p^T\) — but it reduces the integer/address-arithmetic inside the inner loop, which in practice buys back cycles otherwise spent on address computation, tightening the path toward a compute-bound kernel.