Skip to content

Complete Mathematics of "Optimization 10: Statement Reordering (and OpenMP Hooks)"

Optimization 10 makes no change to the mathematics — it reorders the statements inside the AddDot4x1 loop body and adds commented-out OpenMP pragmas as parallelism hooks. Two distinct ideas are at play: (a) reordering independent FMAs for compiler scheduling / ILP, and (b) the latent option of parallelizing across output rows with OpenMP, left disabled so the ladder stays single-threaded and portable.

1. The Mathematical Operation (identical)

For \(r=0,1,2,3\):

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

2. Statement Reordering Inside the Kernel

x_p = x[p];

c_0 += *a_0_ptr * x_p;
c_1 += *a_1_ptr * x_p;

c_2 += *a_2_ptr * x_p;
c_3 += *a_3_ptr * x_p;

2.1 The math doesn't change

Each c_r still receives the same term \(A_{i+r,p}\,x_p\) in the same \(p\)-order. The four updates are independent (distinct accumulators), so their textual order is immaterial to the result.

2.2 Why reorder at all

The order in which the compiler schedules these FMAs and the subsequent loads determines whether it can:

  • interleave the four independent chains to hide FMA latency;
  • hoist / software-pipeline the next step's loads (of x[p+1] and the four A elements) behind the current FMAs.

Grouping the statement order to maximize the distance between dependent operations on the same accumulator helps the out-of-order scheduler keep every FP pipe filled. As in matmul's Optimization 10, this is a "free lunch": same numbers, better issue.

3. The Commented-Out OpenMP Hooks

// #pragma omp parallel for num_threads(4)
//    for (int i = 0; i < m; i += 4){ AddDot4x1(...); }

3.1 Mathematically, y = Ax + y parallelizes trivially over rows

Each output \(y_i\) depends only on row \(i\) of \(A\) and the whole vector \(x\):

\[ y_i = \sum_p A_{ip}x_p + y_i. \]

Different rows share only the read-only vector \(x\); there is no cross-row dependency. Hence the outer i-loop is embarrassingly parallel:

\[ y_{i_1} \perp y_{i_2} \quad\text{for } i_1\neq i_2. \]

A parallel for over i (or over i+=4 kernel groups) assigns disjoint y slices and disjoint A row-panels to threads — race-free as long as each y[i] is written by exactly one thread.

3.2 Why it's disabled

Leaving the pragmas commented out:

  • keeps this level single-threaded and portable (no OpenMP dependency in the ladder's core measurements),
  • preserves a fair comparison across optimizations on the same hardware,
  • documents where parallelism would go, without changing measured performance here.

4. Roofline Note: Parallelization vs. Memory Bound

Since matvec is memory-bound (arithmetic intensity \(\approx 0.25\) FLOP/byte), adding threads can scale throughput only up to the memory-bandwidth ceiling, not the compute ceiling. Parallelizing the row loop helps saturate bandwidth when one core's loads can't, but it cannot turn matvec compute-bound. This reinforces why the ladder's real wins come from vectorizing the streaming kernel rather than from concurrency.

5. Summary

Aspect Optim 8/9 Optim 10
Mathematics \(y \mathrel{+}= Ax\) identical
Accumulator order (given) reordered for ILP
Accumulators 4 4
FLOPs \(2mk\) \(2mk\)
OpenMP none pragmas present but disabled
Outer-loop parallelism none active documented, not enabled

Optimization 10 changes when independent work is issued (reordering) and where concurrency could be added (disabled OpenMP). Both leave the computed values untouched — it is a scheduling/preparation step rather than a new algorithm, and (like its matmul sibling) yields at most a modest scheduling win on a memory-bound kernel.