Complete Mathematics of "Optimization 10: Statement Reordering for ILP"

Optimization 10 makes no change to the mathematics and no change to which memory addresses are touched. It purely reorders the statements inside the innermost loop body of the 4×4 kernel. The goal is to break floating-point dependency chains and improve instruction scheduling so the CPU's superscalar/FMA pipes stay saturated. It demonstrates that the order of independent math can matter for performance without changing the result.

---

1. The Mathematical Operation (identical)

Still the rank-1 accumulation:

\[ \mathbf{C} \;\mathrel{+}=\; \sum_{p=0}^{k-1}\mathbf{a}_p\,\mathbf{b}_p^{T}. \]

Elementwise, each accumulator gets an independent term each trip:

\[ \gamma_{rc}^{(p+1)} = \gamma_{rc}^{(p)} + A_{i+r,p}\,B_{p,j+c}. \]

---

2. Why Order Matters: Dependency Chains & Latency

The critical path through one accumulator over the whole loop is:

\[ \gamma_{rc}^{(0)} \to \gamma_{rc}^{(1)} \to \gamma_{rc}^{(2)} \to \cdots \to \gamma_{rc}^{(k-1)}. \]

The period of this chain is the latency of one FMA, \(L\) (e.g., 4 cycles). For a single accumulator, the kernel can only progress \(1\) FMA per \(L\) cycles. To reach the machine's peak FMA throughput of, say, \(P\) FMAs per cycle, we need at least \(L\cdot P\) independent chains in flight simultaneously.

With sixteen independent accumulators, we already have enough in principle. But the compiler's generated schedule depends on the textual order of the statements: if stores/loads or dependent pairs are packed together, the scheduler may stall.

---

3. Statement Reordering as a Scheduling Problem

Consider the inner loop body as a set of independent FMAs:

\[ \begin{aligned} &c_{00}\mathrel{+}=a_0b_0,\ c_{01}\mathrel{+}=a_0b_1,\ c_{02}\mathrel{+}=a_0b_2,\ c_{03}\mathrel{+}=a_0b_3,\\ &c_{10}\mathrel{+}=a_1b_0,\ c_{11}\mathrel{+}=a_1b_1,\ \dots,\ c_{33}\mathrel{+}=a_3b_3. \end{aligned} \]

A good schedule interleaves the sixteen chains so that no two writes to the same accumulator are adjacent (they would serialize on the same register), and so that loads of \(A_{i+r,p+1}, B_{p+1,j+c}\) for the next trip are issued early, hiding memory latency.

3.1 Formal view

Let each chain have a "distance" \(d_{rc}\) since its last update. Reordering maximizes the minimum spacing between consecutive updates of the same chain, i.e.:

\[ \max \min_{r,c}(\text{gap between updates of } \gamma_{rc}). \]

Larger gaps give the hardware more room to overlap the FMA latency of one chain with the arithmetic of others.

---

4. What Actually Changes

• Numbers: none. Floating-point sum order, grouping, and per-element results are identical to Optimization 8/9 because each \(\gamma_rc\) still receives its \(k\) terms in the same order.
• Instruction stream: different ordering of the 16 independent FMAs and of the pointer-increment/prefetch code, which the compiler schedules around.
• Performance: can improve by letting the pipelined FMA units issue back-to-back instead of stalling on a single chain's latency.

---

5. Interplay with Loads

Reordering also lets the compiler hoist the eight loads (\(a_0..a_3, b_0..b_3\)) for trip \(p+1\) before the sixteen FMAs of trip \(p\). This is classic software pipelining: load latency is hidden behind the FMAs of the previous trip, keeping the load ports and FP units both busy every cycle.

---

6. Summary

Aspect	Optim 8/9	Optim 10
Mathematics	\(\mathbf{C}+=\sum_p\mathbf{a}_p\mathbf{b}_p^T\)	identical
Accumulators	16	16
FLOPs	\(2mnk\)	\(2mnk\)
Statement order	naive grouping	interleaved for ILP
Dependency-chain spacing	may be poor	improved

Optimization 10 is the "free lunch" step: it changes only when independent operations are issued, not which operations run. By interleaving the sixteen independent FMA chains and hoisting next-trip loads, it helps the hardware fill every FMA slot — a pure scheduling refinement on top of the register-tiled kernel.