Complete Mathematics of "Optimization 5: Pointer Advancement + 4× Loop Unrolling"¶

Optimization 5 makes two changes to the 1×4 micro-kernel:

Pointer-based addressing for \(B\): instead of recomputing the column-major address \(B(p,c)=b[c\,\text{ldb}+p]\) every iteration (which requires a multiply by \(\text{ldb}\)), it keeps four pointers that advance by 4 each group of steps.
4× unrolling of the \(p\)-loop: four values of \(p\) are processed per loop trip, exposing more instruction-level parallelism.

1. The Mathematical Operation (unchanged)¶

Still, for \(c=0,1,2,3\):

\[ C_{i,\,j+c} \;\mathrel{+}=\; \sum_{p=0}^{k-1} A_{i,p}\, B_{p,\,j+c}. \]

2. Pointer-Based Addressing of \(B\)¶

2.1 Macro-based addressing (Optimization 4)¶

For column \(c\) the macro gives:

\[ B(p, c) \;=\; b\big[(j+c)\,\text{ldb} + p\big]. \]

Each access involves the integer product \((j+c)\cdot \text{ldb}\), an add, an address computation, and a load. This is repeated for all four \(c\) on every \(p\).

2.2 Pointer-based addressing (Optimization 5)¶

The kernel keeps four pointers to the current element of each of the four \(B\) columns:

\[ b^{\,*}_{00} \to B(0,j), \quad b^{\,*}_{01} \to B(0,j+1), \quad b^{\,*}_{02} \to B(0,j+2), \quad b^{\,*}_{03} \to B(0,j+3). \]

In column-major storage, successive rows \(p\) of a fixed column are contiguous, so the true address of \(B(p,c)\) relative to \(B(0,j+c)\) is just \(p\). Hence after processing \(p\), all four pointers simply advance by 1:

\[ b^{\,*}_{0c} \;\leftarrow\; b^{\,*}_{0c} + 1. \]

The multiply-by-\(\text{ldb}\) disappears entirely.

3. The 4× Unrolled Loop¶

The code writes the loop as:

for (p = 0; p < k; p += 4) {
    a_0p = A(0, p);
    c_00 += a_0p * *b_00_ptr;  c_01 += a_0p * *b_01_ptr;  // p
    c_02 += a_0p * *b_02_ptr;  c_03 += a_0p * *b_03_ptr;

    a_0p = A(0, p+1);
    c_00 += a_0p * *(b_00_ptr+1);  /* ... */               // p+1

    a_0p = A(0, p+2);                                     // p+2
    ...

    a_0p = A(0, p+3);                                     // p+3
    ...
    b_00_ptr += 4; b_01_ptr += 4; b_02_ptr += 4; b_03_ptr += 4;
}

3.1 Grouped unrolling¶

Let the loop trip index be \(t\), so the four body iterations correspond to \(p = 4t, 4t+1, 4t+2, 4t+3\). For each \(c\):

\[ \gamma_c \;\mathrel{+}=\; a_{4t}B_{4t,\,c} + a_{4t+1}B_{4t+1,\,c} + a_{4t+2}B_{4t+2,\,c} + a_{4t+3}B_{4t+3,\,c}. \]

No numeric order change at all — addition is associative so the four partial products can be summed in any grouping; numerically this is identical to the serial accumulation (up to floating-point round-off order).

4. Why These Changes Help¶

4.1 Fewer address computations¶

The macro form redoes \(\text{ldb}\)-multiplication for every element. The pointer form turns address update into a simple integer increment, leaving more ALU/load ports free for the actual arithmetic.

4.2 More ILP¶

Within one trip, the four accumulator chains receive four independent updates. The compiler can schedule:

load \(a_{4t}\);
issue four multiply-adds that all depend on the same \(a_{4t}\) but independent \(\gamma_c\);
meanwhile prepare the next loads.

This keeps multiple FP pipes busy and hides load latency.

4.3 Reduced loop control overhead¶

Instead of one branch + pointer update per \(p\), we do one per group of four \(p\). Branch overhead drops by a factor of 4.

5. Arithmetic Intensity¶

FLOPs stay \(2mnk\). The additional work-removed per tile is \(O(k)\) fewer address ALU ops, which is a constant-factor improvement, not an asymptotic one. The main residual inefficiency is the strided access to \(A\) (stride \(\text{lda}=m\)), which the kernel still reads one element at a time.

6. Summary¶

Resource / metric	Optim 4	Optim 5
FLOPs	\(2mnk\)	\(2mnk\)
\(B\) addressing	\(\times \text{ldb}\) each access	pointer increment
Loop unroll factor	1	4
Kernel shape	\(1\times4\)	\(1\times4\)
Dependency chains	4	4 (more interleaving)
A access	strided (stride\(m\))	strided (stride\(m\))

The key mathematical idea is expressing the inner loop in a form where the address arithmetic is a simple linear increment, and unrolling to expose multiple independent accumulator updates per branch, so the FP pipes stay busy.