Complete Mathematics of "Optimization 5: Pointer-Advanced x + 4× Reduction Unroll"

Optimization 5 refines the AddDot1x4 4-output kernel in two ways:

1. It advances through x with a pointer (x_ptr) instead of an index — removing the index arithmetic for the contiguous vector.
2. It unrolls the \(p\)-loop by 4, processing four values of \(p\) per trip, which — combined with the four separate register accumulators introduced in Optimization 4 — exposes genuine instruction-level parallelism.

---

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 Structure

register double c_0, c_1, c_2, c_3, x_p;
double *x_ptr = x;
c_0 = c_1 = c_2 = c_3 = 0.0;

for (p = 0; p < k; p += 4){
    x_p = *x_ptr;                  // 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;

    x_p = *(x_ptr+1);              // x[p+1]
    c_0 += A(0,p+1)*x_p;  c_1 += A(1,p+1)*x_p;
    c_2 += A(2,p+1)*x_p;  c_3 += A(3,p+1)*x_p;

    x_p = *(x_ptr+2);              // x[p+2]
    c_0 += A(0,p+2)*x_p;  c_1 += A(1,p+2)*x_p;
    c_2 += A(2,p+2)*x_p;  c_3 += A(3,p+2)*x_p;

    x_p = *(x_ptr+3);              // x[p+3]
    c_0 += A(0,p+3)*x_p;  c_1 += A(1,p+3)*x_p;
    c_2 += A(2,p+3)*x_p;  c_3 += A(3,p+3)*x_p;

    x_ptr += 4;
}

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

---

3. Pointer Advancement for x

The four x reads use *x_ptr, *(x_ptr+1), *(x_ptr+2), *(x_ptr+3) and then x_ptr += 4. Because x is contiguous (stride 1), advancing by 4 is a simple +4 pointer increment each trip:

\[ \operatorname{addr}(x_{4t+q}) = \operatorname{base}(x) + (4t+q), \qquad q=0,1,2,3. \]

No index multiplication, no recomputed offsets — just one pointer bump per trip. (This addresses the vector side; the matrix \(A\) still uses the strided macro access A(r,p).)

---

4. ILP: Sixteen Independent FMAs per Trip

Each trip performs 16 multiply–adds across the four accumulators and four \(p\)-values:

\[ c_r \;\mathrel{+}=\; \sum_{q=0}^{3} A_{i+r,\,4t+q}\; x_{4t+q}, \qquad r=0,1,2,3. \]

The sixteen products \(A_{i+r,4t+q}\cdot x_{4t+q}\) are all independent (distinct \(A\) entries, distinct \(x\) entries), and they accumulate into four distinct chains \(c_0..c_3\). This gives both:

• Memory-level parallelism: the sixteen loads can be issued ahead (especially with software pipelining by the compiler);
• Four-way ILP in the accumulation chains.

Combined with pointer-based x, this is the tightest version so far of a scalar 4-output kernel.

---

5. Math: Grouped Partial Sums

Because the four contributions to each \(c_r\) in a trip are summed (by the hardware/compiler) before the chain advances, numerically:

\[ y_{i+r} \;\mathrel{+}=\; \sum_{t=0}^{k/4-1}\sum_{q=0}^{3} A_{i+r,4t+q}\,x_{4t+q} \;=\; \sum_{p=0}^{k-1} A_{i+r,p}\,x_p. \]

Associativity of FP addition justifies regrouping; the sum is mathematically identical.

---

6. Memory Access Profile

Access	Scheme	Behavior
\(x\)	pointerx_ptr	contiguous, +4/trip
\(A(i:i+3, p)\)	macro strided (variable\(p\))	4-run per column, jumplda between columns
\(y\)	flush once	contiguous 4 writes

---

7. Summary

Metric	Optim 4	Optim 5
x addressing	indexx[p]	pointer x_ptr
Reduction unroll	1	4
FMAs per trip	4	16
Independent chains	4	4 (×4 terms each)
A access	strided	strided
FLOPs	\(2mk\)	\(2mk\)

Optimization 5 does not change the mathematics — it tightens the inner loop by using a pointer for the contiguous x and unrolling the reduction 4×, so the compiler sees a wide batch of independent FMAs feeding four register accumulators. The remaining inefficiency is the stride-lda access to \(A\), which later levels address with pointers (Optimization 9+) and packing (Optimization 14).