06 — Writing a New Level (optim15)

This tutorial shows how to add a new optimization level to the ladder. We'll add src/matvec/optim15.c as a concrete example.

The pattern for a new level

Every level is a self-contained program that:

1. does #include <matvec.h> (or <gemm.h>),
2. defines its kernel function (here matvec),
3. has a main() that fills data, times the kernel, and prints GFLOPS.

1. Write the source

Create src/matvec/optim15.c, copying the structure of optim14.c (the current best portable level) and changing the kernel. For example, a 4× reduce-unrolled, packed, register kernel:

#include <matvec.h>

#define A(i,j) a[(j)*lda+(i)]

void matvec(int m, int k, double *a, int lda, double *x, double *y){
    for (int i = 0; i < m; i += 4){
        double c0=0,c1=0,c2=0,c3=0;
        for (int p = 0; p < k; p += 4){
            c0 += A(0,p)*x[p];   c1 += A(1,p)*x[p];
            c2 += A(2,p)*x[p];   c3 += A(3,p)*x[p];

            c0 += A(0,p+1)*x[p+1]; c1 += A(1,p+1)*x[p+1];
            c2 += A(2,p+1)*x[p+1]; c3 += A(3,p+1)*x[p+1];

            c0 += A(0,p+2)*x[p+2]; c1 += A(1,p+2)*x[p+2];
            c2 += A(2,p+2)*x[p+2]; c3 += A(3,p+2)*x[p+2];

            c0 += A(0,p+3)*x[p+3]; c1 += A(1,p+3)*x[p+3];
            c2 += A(2,p+3)*x[p+3]; c3 += A(3,p+3)*x[p+3];
        }
        y[i] += c0; y[i+1] += c1; y[i+2] += c2; y[i+3] += c3;
    }
}

int main(void){
    /* copy the main() from optim14.c: fill random data, time matvec(...),
       print seconds and GFLOPS */
    return 0;
}

Copy main() from src/matvec/optim14.c and update the printed label to Optimization 15.

2. Make it build

The Makefile auto-discovers matvec levels by name. Because optim15 is covered by the matvec% pattern rule, it builds automatically:

make build/matvec15
./build/matvec15

If it doesn't, add 15 to MATVEC_LEVELS in the Makefile.

3. Document the mathematics

Create docs/research/matvec/optim15.md following the style of the other research notes: the math of the operation, the memory/stride analysis, the ILP story, a FLOP accounting, and a summary table.

4. Add a tutorial (optional)

If your level demonstrates a genuinely new technique, add a short section to an existing tutorial or create a new tutorial page, and register any new nav page in mkdocs.yml.

5. Verify

make clean && make && make test

And confirm the level still gives identical results to the reference — the ladder is about speed, never about changing the answer.

Tip

Want to fix the gap for x86? Sponsor a portable sse_compat.h so matmul optim11–14 compile on Apple Silicon too — see the research notes for what SSR/AVX intrinsics they expect.