Complete Mathematics of "Optimization 2: 4× Loop Unrolling over the Reduction Dimension"¶

Optimization 2 keeps the per-row dot-product form but manually unrolls the inner \(k\)-loop by 4. For a fixed output row \(y_i\), it processes four consecutive values of the reduction index \(p\) per loop trip. This reduces loop overhead and, more importantly, exposes multiple independent multiply–add operations that can overlap.

1. The Mathematical Operation (unchanged)¶

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

2. The Unrolled Loop¶

for (p = 0; p < k; p += 4) {
    y[i] += x[p]   * A(i,p);
    y[i] += x[p+1] * A(i,p+1);
    y[i] += x[p+2] * A(i,p+2);
    y[i] += x[p+3] * A(i,p+3);
}
for (; p < k; p++)                    // cleanup for k % 4 != 0
    y[i] += x[p] * A(i,p);

2.1 Grouped partial sum¶

Let the trip index be \(t\), so one trip covers \(p=4t,\dots,4t+3\). The body computes:

\[ y_i \;\mathrel{+}=\; x_{4t}A_{i,4t} + x_{4t+1}A_{i,4t+1} + x_{4t+2}A_{i,4t+2} + x_{4t+3}A_{i,4t+3}. \]

Floating-point addition is associative, so grouping the four terms per trip yields the same mathematical sum \(\sum_p A_{ip}x_p\) (up to round-off re-ordering, which is allowed and benign).

2.2 Cleanup for non-multiples of 4¶

If \(k\) is not a multiple of 4, a trailing scalar loop handles the remainder \(k \bmod 4\) elements. Since \(k=2000 = 4\cdot500\), here the main loop fully covers \(k\).

3. Instruction-Level Parallelism (ILP) Analysis¶

The four statements all update the same accumulator y[i]:

\[ y_i \mathrel{+}= x_p A_{ip}, \quad y_i \mathrel{+}= x_{p+1}A_{i,p+1}, \quad \dots \]

These are serially dependent on the single accumulator y[i] — each add must wait for the previous. So this particular unroll, by itself, does not break the dependency chain; a compiler may re-associate them into independent temporaries, but the source has one accumulator. This is an important limitation: the ILP benefit only fully arrives in Optimization 4+, where four separate register accumulators are introduced.

3.1 What the unroll does help¶

Loop control: one branch + pointer/p increment per 4 elements instead of per element — up to 4× fewer control-flow operations.
Address computation: fewer index recomputations for the strided \(A\) row.
Load scheduling: the compiler can batch the four loads of \(A(i,p..p+3})\) and let the multiplies overlap.

4. Memory Access (unchanged pattern)¶

Same stride structure as Optimization 1:

Access	Stride
\(A_{i,p}, A_{i,p+1}, \dots\)	\(\text{lda}\) (strided)
\(x_p, x_{p+1}, \dots\)	1 (contiguous)
\(y_i\)	reused

5. FLOP Accounting¶

Total arithmetic is unchanged:

\[ \text{FLOPs} = 2mk. \]

Per trip of the main loop: \(4\) multiplications + \(4\) additions = \(8\) FLOPs; across \(k/4\) trips per row \(\Rightarrow 2k\) FLOPs per row, \(\times m\) rows \(= 2mk\).

6. Summary¶

Metric	Optim 1	Optim 2
Unroll factor	1	4
Loop trips per row	\(k\)	\(k/4\)
Accumulators	1	1 (still one scalar)
Dependency chains	1 (serial)	1 (serial in source)
FLOPs	\(2mk\)	\(2mk\)
A access	strided	strided
ILP benefit	minimal	modest (control overhead ↓)

Optimization 2 reduces loop and address-computation overhead by unrolling the reduction loop 4×, but it keeps a single per-row accumulator, so the classic dependency-chain limit is not yet addressed. The decisive step — multiple independent accumulators — comes with the 4-output kernel.

Note on the reference "unrolling by 4 (column blocking)" in matmul: the analogous matmul unroll exposed four independent accumulators (four columns of \(C\)). For matvec, unrolling over \(p\) within a single output does not produce independent chains; the true parallelism in matvec comes instead from processing four output rows simultaneously (Optimization 3+), which is what the subsequent kernels exploit.