Complete Mathematics of "Optimization 6: The AddDot4x1 4-Output Wrapper (via AddDot)"

Optimization 6 introduces the named AddDot4x1 kernel — the canonical matvec micro-kernel shape — but constructs it by calling the scalar AddDot four times, once per output row. Like its matmul counterpart (Optimization 6), this is a deliberate correctness-first / structural step: it firmly establishes the 4×1 output kernel contract, which the fused, register-bound versions on either side refine.

Note: Optimization 3 already showed the fused single-loop 4-output form; the ladder here re-covers the territory under the AddDot4x1 name, then Optimization 7 fuses it once more. The naming mirrors the matmul ladder (which also momentarily "regressed" to a dot-product-assembled tile before fusing).

---

1. The Mathematical Operation

The 4×1 kernel produces four output elements from a 4×k panel of \(A\) and the vector \(x\):

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

In block form, with \(\mathbf{A}\in\mathbb{R}^{4\times k}\) the panel of rows \(i..i+3\):

\[ \boxed{\; \begin{bmatrix} y_i \\ y_{i+1} \\ y_{i+2} \\ y_{i+3} \end{bmatrix} \;\mathrel{+}=\; \mathbf{A}_{4\times k}\; x \;} \]

---

2. Construction by Four AddDot Calls

void AddDot4x1(int k, double *a, int lda, double *x, double *y){
    AddDot(k, &A(0,0), lda, x, &y[0]);
    AddDot(k, &A(1,0), lda, x, &y[1]);
    AddDot(k, &A(2,0), lda, x, &y[2]);
    AddDot(k, &A(3,0), lda, x, &y[3]);
}

Each AddDot computes one row dot product (as in Optimization 1):

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

The four calls iterate over p serially (four separate loops of length \(k\)).

---

3. Loop Structure

The outer matvec loop steps i by 4:

for (i = 0; i < m; i += 4)
    AddDot4x1(k, &A(i,0), lda, x, &y[i]);

Number of kernel calls: \(m/4\); each performs \(4\) dots of length \(k\), for a total of \(m\) dots and \(2mk\) FLOPs — unchanged.

---

4. Data Reuse Within the Kernel

Per AddDot4x1 call:

• x: read \(4\) times (once per AddDot call) — fully reusable, but redundantly re-traversed here;
• A row: each row read once per its own AddDot.

Because the four calls run as separate loops, the same vector x is walked four separate times, and the compiler may not fuse them. This is the reason Optimization 7 re-fuses into one loop: to traverse x exactly once and keep all four accumulators in flight simultaneously.

---

5. Why the Wrapper Matters Despite the Regression

• It gives the kernel a stable name and signature (AddDot4x1) that organizes the rest of the ladder.
• It makes the 4×1 output tile the unit of work, matching how the matmul ladder standardizes on 4×4.
• It is the structural anchor: everything from Optimization 7 onward optimizes inside this 4×1 contract.

---

6. FLOP Accounting

Per call: \(4\cdot2k = 8k\) FLOPs; over \(m/4\) calls:

\[ \text{FLOPs} = \frac{m}{4}\cdot 8k = 2mk. \quad\checkmark \]

---

7. Summary

Metric	Optim 5	Optim 6 (AddDot4x1 via AddDot)
Kernel name	AddDot1x4	AddDot4x1
Outputs per kernel	4	4
Loops per group	1 (fused)	4 (serial AddDot)
x traversal	once	4× (redundant)
Accumulators in flight	4	1 at a time
FLOPs	\(2mk\)	\(2mk\)
Purpose	performance	structure / naming

Optimization 6 defines the 4×1 micro-kernel by assembling four scalar dot products. It may run more slowly than the already-fused Optimization 5, but it establishes the canonical kernel contract that Optimization 7 fuses into a single efficient pass.