Complete Mathematics of "Optimization 4: Register-Bound Accumulators"

Optimization 3 updated the four outputs through memory on every iteration of \(p\) (via y0[0] += ...). Optimization 4 captures the four accumulators in CPU registers for the entire \(p\)-loop and writes them back to \(y\) only once, after the loop. This removes the repeated read-modify-write traffic to the output vector.

---

1. Mathematical Operation (unchanged)

Still, for \(r = 0,1,2,3\):

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

---

2. Accumulation in Registers

The kernel declares four register accumulators and one broadcast scalar:

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;
    c_1 += A(1,p) * x_p;
    c_2 += A(2,p) * x_p;
    c_3 += A(3,p) * x_p;
}

y0[0] += c_0;  y1[0] += c_1;  y2[0] += c_2;  y3[0] += c_3;   // flush once

2.1 The two-phase recurrence

Phase 1 — register accumulation (in \(p\)-loop):

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

Phase 2 — single flush (after loop):

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

No read of y and no write to y occurs inside the \(p\)-loop.

---

3. Memory-Traffic Reduction for the Output Vector

Let \(T_y\) be the number of memory transfers to the output group per kernel call.

Step	Optim 3 (\(y\) in-memory)	Optim 4 (\(c\) in registers)
Reads of \(y_i\) in loop	\(4k\)	\(0\)
Writes of \(y_i\) in loop	\(4k\)	\(0\)
Reads after loop (for +=)	\(0\)	\(4\) (read old \(y\))
Writes after loop	\(0\)	\(4\)
Total \(y\) traffic	\(8k\)	\(8\)

For \(k=2000\) this removes \(8k \approx 1.6\times10^4\) output memory ops per kernel call — eliminating the only non-streaming writes from the hot loop.

---

4. Latency / Dependency-Chain Analysis

Each accumulator runs an independent recurrence with period equal to one floating-point add latency:

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

• If \(c_r\) lived in memory (Optimization 3), the period is dominated by memory latency (tens of cycles).
• Held in a register (Optimization 4), the period is one FP-multiply-add latency (a few cycles).

The four chains \(c_0..c_3\) are independent, so they interleave and keep the FP pipes busy:

\[ \text{throughput} \approx \frac{\#\text{FP pipes}}{\max(L_{\text{FMA}},\ \text{issue width})}. \]

---

5. The register Keyword

The hints register double c_0..c_3, x_p; express intent that these hot scalars stay in registers. At -O2/-O3 the compiler generally promotes them anyway; the keyword documents the design and can help older compilers. Only 5 hot scalars are needed (4 accumulators + 1 x_p broadcast), which is far below the register budget.

---

6. Summary

Metric	Optim 3	Optim 4
FLOPs	\(2mk\)	\(2mk\)
Outputs per kernel	4	4
\(y\) traffic per kernel	\(8k\)	\(8\)
Accumulator location	memory	registers
Inner-loop latency bound	memory latency	FP-add latency
Independent chains	4	4

The mathematical idea is deferral of the final write: carry four partial sums in registers across the whole \(p\)-loop and commit them to y exactly once. This converts the inner loop from output-memory-latency-bound to a clean compute-bound vector accumulation — the foundation the rest of the ladder builds on.