matrix

High-performance dense linear-algebra kernels in C, built the "FLAME / GotoBLAS way" — a guided ladder of optimizations for matrix × matrix (matmul) and matrix × vector (matvec).

This repository is a hands-on study of how a naive triple-loop matrix multiply or matrix–vector multiply is progressively turned into a cache-aware, vectorized micro-kernel. It mirrors the classic "How to optimize GEMM" tutorial by FLAME (Field Programmable Architecture Multimedia Extensions / Linear Algebra for Multicore) and provides a complete, runnable set of optimization levels, plus the mathematics behind each one.

---

Table of Contents

• What's inside
• Project layout
• Prerequisites
• Building
• Running the optimization ladder
• Using the reference kernels (API)
• Examples
• Tests
• Documentation
• Portability notes
• Contributing
• License

---

What's inside

Two kernel families, each with 15 optimization levels (optim0 … optim14):

Kernel	Operation	Signature
matmul (matrix × matrix)	C = A·B + C	matmul(m, n, k, a, lda, b, ldb, c, ldc)
matvec (matrix × vector)	y = A·x + y	matvec(m, k, a, lda, x, y)

Both use column-major storage (Fortran / BLAS convention), so A(i,j) = a[j*lda + i].

The optimization levels walk you through:

• 0–2: naive baselines, dot-product extraction, unrolling
• 3–5: fused micro-kernels, register accumulators, pointer arithmetic
• 6–8: the canonical 4×4 (matmul) / 4×1 (matvec) kernel, register blocking
• 9–11: pointer-based addressing, statement ordering, vectorization
• 12–14: cache blocking, matrix packing, fully packed micro-kernels

Each level is a self-contained, runnable program with its own main(), so you can build any level, run it, and watch the GFLOPS climb (or understand why it sometimes dips — e.g. the "structure-first" levels).

---

Project layout

matrix/
├── include/
│   ├── gemm.h                 # Public header for matmul (column-major)
│   └── matvec.h               # Public header for matvec  (column-major)
├── src/
│   ├── matmul.c               # Reference matmul kernel (library, no main)
│   ├── matvec.c               # Reference matvec kernel (library, no main)
│   ├── gemm.c                 # matmul reference DRIVER (main)  [at repo root]
│   ├── matmat/
│   │   └── optim0.c … optim14.c  # 15 self-contained matmul levels
│   └── matvec/
│       └── optim0.c … optim14.c  # 15 self-contained matvec levels
├── examples/                  # Ready-to-run usage examples
├── tests/
│   └── correctness.c          # Numerical validation vs. naive reference
├── docs/
│   ├── tutorials/             # Guided tutorials
│   └── research/              # The math behind every optimization level
│       ├── matmat/optim0.md … optim14.md
│       └── matvec/optim0.md … optim14.md
├── mkdocs.yml                 # Documentation site config
├── .github/workflows/docs.yml # Deploy docs to GitHub Pages
├── Makefile                 # Build & test helper
└── README.md

Note: gemm.c lives at the repository root — it is a small driver that calls the matmul() reference kernel. The sentence above lists it under src/ conceptually; the physical file is ./gemm.c.

---

Prerequisites

• A C99 (or later) compiler: gcc (Linux/WSL), clang (macOS, most Linux), or MSVC (cl on Windows).
• make for the convenience targets (optional — you can also just run gcc directly).
• Python 3 + pip only if you want to build the documentation site with mkdocs.
• No external math libraries are required — everything is self-contained.

---

Building

Quick start (everything)

make            # build every runnable optimization level + drivers
make test       # build and run the correctness test suite
make clean      # remove build artifacts

The build outputs go into a build/ directory (kept out of git via .gitignore).

Build a single level directly with gcc/clang

# matrix-vector, level 5
gcc -O2 -I include -o build/matvec5 src/matvec/optim5.c

# matrix-matrix, level 8
gcc -O2 -I include -o build/matmat8 src/matmat/optim8.c

Build the reference drivers

# matmul reference (driver gemm.c + library matmul.c)
gcc -O2 -I include -o build/ref_matmul gemm.c src/matmul.c

# matvec reference (link a small main against src/matvec.c, or use an example)

The optim*.c files under src/matmat/ and src/matvec/ are standalone (each has a main). The files src/matmul.c and src/matvec.c are libraries (no main) and must be linked with a driver.

---

Running the optimization ladder

Every optimization level is an executable that:

1. Allocates and fills random data,
2. Times the kernel,
3. Prints the elapsed seconds and achieved GFLOPS.

./build/matvec5
# -> Optimization 5 : Dot product took 0.00xxxx seconds GFLOPS : 3.xx

Run all levels and compare GFLOPS to see the ladder in action:

for i in $(seq 0 14); do ./build/matmat$i; done
for i in $(seq 0 14); do ./build/matvec$i; done

The "reference" GFLOPS formula

Each program reports:

GFLOPS = 2 · (number of multiply-adds) / time

• matmul: 2 · m · n · k
• matvec: 2 · m · k

---

Using the reference kernels (API)

The public headers declare the kernels you can call from your own code.

include/gemm.h — matmul

#include <gemm.h>

void matmul(int m, int n, int k,
            double *a, int lda,
            double *b, int ldb,
            double *c, int ldc);

Computes C = A·B + C. All matrices are double, stored column-major:

• A is m×k, element (i,j) at a[j*lda + i]
• B is k×n, element (i,j) at b[j*ldb + i]
• C is m×n, element (i,j) at c[j*ldc + i]

lda, ldb, ldc are the leading (row) dimensions of each array.

include/matvec.h — matvec

#include <matvec.h>

void matvec(int m, int k,
            double *a, int lda,
            double *x, double *y);

Computes y = A·x + y. A is m×k column-major, x has length k, y has length m (both vectors are contiguous).

See the Examples section and the examples/ directory for complete, compilable samples.

---

Examples

The examples/ folder contains small, copy-paste-ready programs that show how to link against the reference kernels, e.g. examples/matmul_driver.c and examples/matvec_driver.c.

Build any example by compiling it together with the library it needs:

gcc -O2 -I include -o build/ex_matmul examples/matmul_driver.c src/matmul.c
gcc -O2 -I include -o build/ex_matvec  examples/matvec_driver.c  src/matvec.c

---

Tests

tests/correctness.c validates the reference matmul() against a naive triple-loop reference over a range of sizes, including cache-blocking boundaries and non-multiples-of-4 ("fringe") cases.

make test

Expected output ends with:

 TESTS PASSED

---

Documentation

Full documentation is built with mkdocs and mkdocs-material, and is deployed to GitHub Pages on every push to the default branch.

Build the docs locally

pip install mkdocs mkdocs-material
mkdocs serve          # http://127.0.0.1:8000
mkdocs build          # outputs to site/

Docs content

• docs/ – the documentation site source (mkdocs renders docs/index.md, docs/tutorials/*, and docs/research/*).
• docs/research/matmat/optim*.md – complete mathematics for each matmul optimization.
• docs/research/matvec/optim*.md – complete mathematics for each matvec optimization.
• docs/tutorials/ – step-by-step guided tutorials for working through the ladder.

Where GitHub Pages deploys

The workflow .github/workflows/docs.yml builds site/ and publishes it to GitHub Pages (branch gh-pages via actions/deploy-pages). Enable Pages → "GitHub Actions" in your repository settings once pushed.

---

Portability notes

• Column-major storage throughout (BLAS-compatible).
• matvec optim11 and the matvec family are portable across macOS, Linux, and Windows, and auto-vectorize (NEON / SSE / AVX) with no architecture-specific intrinsics.
• The matmat optim11–14 levels use x86 SSE intrinsics and #include "sse_compat.h", which is not provided in this repository (they are optional, x86-focused levels). The portable matmat reference (src/matmul.c) includes a scalar fallback for non-x86 targets. If you want to enable the SSE variants, provide your own sse_compat.h and build on x86-64.

---

Contributing

Contributions are welcome. A few good ways to get involved:

1. Write a new optimization level — add src/matmat/optim15.c or src/matvec/optim15.c and its math doc under docs/research/.
2. Improve an existing level — performance, comments, or a portable sse_compat.h.
3. Add tutorials — new step-by-step guides under docs/tutorials/.
4. Fix or extend tests — matrix and vector correctness, edge sizes, fringe cases.
5. Report a bug or request — open an issue describing the problem, the compiler/platform, and a minimal repro.

Contribution guidelines

• Use column-major storage conventions and keep each new level self-contained (its own main).
• Match the naming pattern: functions in gemm.h/matvec.h, levels as optim<N>.c in the matching src/ subfolder.
• Add the mathematics for any new level in docs/research/<family>/optim<N>.md so the ladder stays fully documented.
• Add a tutorial or example if your level demonstrates a genuinely new technique.
• Keep the build green: make and make test must pass on at least one of macOS / Linux (and ideally Windows).
• Respect the existing style: C99, -Wall -Wextra clean on the levels you touch, no new external dependencies.

Development workflow

git clone <your-fork-url> matrix
cd matrix
make
make test
# …make changes…
make clean && make && make test

---

License

This project is released for educational and research use. See the repository's license file (if present) for details — if you reuse or redistribute the code, please credit the FLAME-style optimization tutorial lineage it is based on.