Complete Mathematics of "Optimization 8: Fully Register-Tiled 4×4 Kernel"¶

Optimization 7 already fused the sixteen updates into one \(p\)-loop, but it still read and wrote the \(C\) tile through memory on the way in/out and relied on the compiler to promote them to registers. Optimization 8 makes the register residency explicit and complete: it declares all sixteen \(c_{rc}\) as register accumulators, holds the eight \(a_r, b_c\) operands in registers, and performs a single read of the old \(C\) and a single write of the new \(C\) per element per tile.

1. The Mathematical Operation¶

Identical block product, still the rank-1 accumulation:

\[ \mathbf{C} \;\mathrel{+}=\; \sum_{p=0}^{k-1} \mathbf{a}_p\,\mathbf{b}_p^{T}, \qquad C_{i+r,j+c} \mathrel{+}= \sum_{p=0}^{k-1} A_{i+r,p}\,B_{p,j+c}. \]

2. Explicit Register State¶

2.1 Sixteen accumulator registers¶

\[ \mathbf{\Gamma} = \begin{bmatrix} \gamma_{00} & \gamma_{01} & \gamma_{02} & \gamma_{03}\\ \gamma_{10} & \gamma_{11} & \gamma_{12} & \gamma_{13}\\ \gamma_{20} & \gamma_{21} & \gamma_{22} & \gamma_{23}\\ \gamma_{30} & \gamma_{31} & \gamma_{32} & \gamma_{33} \end{bmatrix} \;\in\; \mathbb{R}^{4\times4}. \]

2.2 The two-level update¶

Initialization (read old \(C\) once):

\[ \gamma_{rc} \leftarrow C_{i+r,\,j+c} \quad \text{(load 16 values)}. \]

Inner loop (pure register arithmetic):

\[ \gamma_{rc} \;\mathrel{+}=\; A_{i+r,p}\,B_{p,j+c},\qquad r,c \in \{0,1,2,3\}. \]

Finalization (write new \(C\) once):

\[ C_{i+r,j+c} \leftarrow \gamma_{rc} \quad \text{(store 16 values)}. \]

This realizes, at the \(4×4\) tile level, exactly the "defer the write" idea first introduced for a \(1×4\) tile in Optimization 4.

3. Memory Traffic Accounting (per tile)¶

Let \(N_C\) be memory transfers of the \(C\) tile over the whole kernel.

Step	Loads	Stores
Old-C init	\(16\)	\(0\)
Inner \(p\)-loop	\(0\)	\(0\)
New-C finalize	\(0\)	\(16\)
Total	16	16

Compare Optimization 7, where without explicit register promotion the compiler might spill; Optimization 8 guarantees only \(2\cdot16\) transfers per tile regardless of \(k\). For \(k=2000\), this is essentially free relative to the \(8k\) A/B loads.

4. Register Pressure & Feasibility¶

The hot state is \(16\) accumulators + \(8\) operand registers (\(a_0..a_3\), \(b_0..b_3\)) + address/loop pointers. On a 64-bit ISA with 16 vector registers (SSE/AVX on x86-64, or NEON on ARM) plus GPRs, this fits comfortably:

16 vector registers for \(\mathbf{\Gamma}\),
4 for the \(\mathbf{a}_p\) column,
4 for the \(\mathbf{b}_p\) row,
remainder for pointers and counters.

This is why the \(4×4\) shape (16 accumulators) is a sweet spot: it is the largest tile that keeps all accumulators resident given 16 architectural vector registers, while leaving room for operands.

5. Floating-Point Considerations¶

Each \(\gamma_{rc}\) update is an FMA: one multiply and one add in a single instruction with one rounding, not two. Over the kernel:

\[ \text{FMAs} = 16 \cdot k, \qquad \text{FLOPs} = 2 \cdot 16 \cdot k = 32k \;\text{ per tile}. \]

Across all \(\frac{mn}{16}\) tiles:

\[ \text{FLOPs} = \frac{mn}{16}\cdot 32k = 2mnk. \]

The FMA latency chain per accumulator is one FMA per \(p\)-step; with 16 independent chains, the machine can sustain near its peak FMA throughput of (FP pipes) FLOPs per cycle.

6. Summary¶

Quantity	Optim 7	Optim 8
\(\mathbf{\Gamma}\) register-resident	implicit	explicit / guaranteed
\(C\) traffic per tile	compiler-dependent	exactly \(2\cdot16\)
FMA chains (ILP)	16	16
FLOPs	\(2mnk\)	\(2mnk\)
Kernel shape	\(4\times4\)	\(4\times4\)

Optimization 8 is the mathematical culmination of the register-tiling idea: the entire \(4×4\) output tile is carried as sixteen independent FMA chains in registers, touched only once at load and once at store, so the inner loop runs at the machine's FMA-compute ceiling rather than its memory bandwidth.