Complete Mathematics of "Optimization 7: The Fused `AddDot4x1` Micro-Kernel"¶

Optimization 7 fuses the four AddDot calls (Optimization 6) into a single loop over \(p\), keeping all four output accumulators alive together. This is the canonical, compute-optimal matvec micro-kernel: each pass over \(p\) reads one broadcast x_p and a contiguous 4-run of \(A\), and updates all four outputs at once.

1. The Mathematical Operation¶

For the 4×k panel of rows \(i..i+3\):

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

equivalently,

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

2. The Kernel Code¶

void AddDot4x1(int k, double *a, int lda, double *x, double *y){
    for (p = 0; p < k; p++){
        double x_p = x[p];
        y[0] += A(0,p) * x_p;   // y_i
        y[1] += A(1,p) * x_p;   // y_{i+1}
        y[2] += A(2,p) * x_p;   // y_{i+2}
        y[3] += A(3,p) * x_p;   // y_{i+3}
    }
}

3. Why Fusing the Four Loops Helps¶

3.1 Compare Optimization 6 (four serial loops)¶

for p:  y[0] += A(0,p)*x[p]
for p:  y[1] += A(1,p)*x[p]
for p:  y[2] += A(2,p)*x[p]
for p:  y[3] += A(3,p)*x[p]

Four full traversals of p; x is walked four times; only one accumulator is live at a time.

3.2 Optimization 7 (single fused loop)¶

for p:
    y[0] += A(0,p)*x[p]
    y[1] += A(1,p)*x[p]
    y[2] += A(2,p)*x[p]
    y[3] += A(3,p)*x[p]

x[p] is loaded once per p and reused by all four rows. Four accumulators are live simultaneously → four independent dependency chains.

4. Instruction-Level Parallelism¶

The four updates share the same scalar x_p but accumulate into four different outputs, so they are independent:

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

Per p-step this is four independent FMAs with no chain between different rows. The FP units can execute them in parallel, and the compiler can load \(A(i:i+3,p)\) as one contiguous 4-vector while broadcasting x_p — the archetypal auto-vectorizable shape.

5. Memory Access: Contiguous Column Slices¶

Column-major layout makes the four \(A\) reads contiguous:

\[ A(0,p)=a[p\text{lda}],\ A(1,p)=a[p\text{lda}+1],\ A(2,p)=a[p\text{lda}+2],\ A(3,p)=a[p\text{lda}+3]. \]

At each p-step we read a contiguous 4-double run (32 bytes — half a cache line), stepping by lda between columns. Compare this to the stride-lda single-element reads of the scalar row-dot versions: far better cache-line utilization and prefetching.

Access	Behavior
\(x_p\)	1 scalar load, broadcast to 4 rows
\(A(i:i+3,p)\)	4 contiguous doubles
\(y[i:i+3]\)	4 distinct output writes

6. Data-Reuse / Traffic Summary per Kernel Call¶

For one \(4\times k\) panel:

Quantity	Loads
\(x_p\)	\(k\) (each used 4×)
\(A\) elements	\(4k\) (each used once)
\(y\) updates	4 (one each)

\(x\) is reused 4× per element within the kernel — the only operand with reuse (consistent with matvec's memory-bound character, where \(A\) is streamed once).

7. FLOP Accounting¶

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

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

8. Summary¶

Metric	Optim 6	Optim 7
Kernel	`AddDot4x1`	`AddDot4x1`
Loops per group	4	1
`x` traversal	4 ×	1 ×
Live accumulators	1	4
A read	strided rows	contiguous 4-run
FLOPs	\(2mk\)	\(2mk\)

Optimization 7 is the fused, canonical 4-output matvec micro-kernel: it reads x once, spews a contiguous 4-vector of \(A\), and drives four independent accumulators — the structure that subsequent steps hold in registers (Optimization 8), pointer-advance (Optimization 9–11), and pack (Optimization 13–14).

Complete Mathematics of "Optimization 7: The Fused AddDot4x1 Micro-Kernel"¶