Complete Mathematics of "Optimization 8: Register-Bound Accumulators in `AddDot4x1`"¶

Optimization 8 takes the fused AddDot4x1 kernel (Optimization 7) and makes the register residency of the four accumulators explicit: it declares c_0, c_1, c_2, c_3 as register accumulators, accumulates across the whole \(p\)-loop without touching y, and flushes all four to y exactly once at the end.

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 Kernel Code¶

register double c_0, c_1, c_2, c_3, x_p;
c_0 = c_1 = c_2 = c_3 = 0.0;

for (p = 0; p < k; p++){
    x_p = x[p];
    c_0 += A(0,p) * x_p;   // accumulate, no y access
    c_1 += A(1,p) * x_p;
    c_2 += A(2,p) * x_p;
    c_3 += A(3,p) * x_p;
}

y[0] += c_0;  y[1] += c_1;  y[2] += c_2;  y[3] += c_3;   // flush once

3. Two-Phase (Init → Accumulate → Flush) Structure¶

Init:

\[ c_r^{(0)} = 0. \]

Inner loop recurrence (register-resident):

\[ c_r^{(p+1)} = c_r^{(p)} + A_{i+r,p}\,x_p. \]

Flush (once):

\[ y_{i+r} \;\leftarrow\; y_{i+r} + c_r^{(k-1)}. \]

4. Output Memory-Traffic Reduction¶

Step	Optim 7 (\(y\) in-memory)	Optim 8 (\(c\) in registers)
y reads in loop	\(4k\)	\(0\)
y writes in loop	\(4k\)	\(0\)
y reads after (for `+=`)	\(0\)	\(4\)
y writes after	\(0\)	\(4\)
Total y traffic	\(8k\)	8

For \(k=2000\), this removes \(8k \approx 1.6\times10^4\) output-memory ops per kernel call from the hot path.

5. ILP and Latency¶

Four independent register chains, one per row:

\[ c_r^{(p+1)} = c_r^{(p)} + A_{i+r,p}\,x_p. \]

Register residence removes memory latency from the recurrence (period = one FMA latency, not DRAM/cache latency).
Four chains interleave so the FP pipes stay fed.

Hot register state: 4 accumulators + 1 x_p broadcast + (soon) 4 A pointers = well within the register file, leaving room for the pointer advances of Optimization 9.

6. Summary¶

Metric	Optim 7	Optim 8
FLOPs	\(2mk\)	\(2mk\)
Accumulators	in `y` (memory)	registers
y traffic per kernel	\(8k\)	\(8\)
Inner-loop latency bound	memory latency	FP-add latency
Independent chains	4	4

Optimization 8 is the matvec counterpart of matmul's "defer the write": four partial sums ride in registers across the whole reduction and are committed to y once. This turns the inner loop into a clean, compute-(vector-)bound streaming accumulation, ready to have its \(A\) addressing optimized next.

Complete Mathematics of "Optimization 8: Register-Bound Accumulators in AddDot4x1"¶