Rung 1 — CPU Tiled Matmul Writeup

Aligned phase: Phase 0 (systems/math foundations) Ship by: end of M2 Effort: ~2 weeks, ~15 hrs total Signal: low-mid. This is a warm-up rung. Its purpose is to prove you can (a) benchmark honestly, (b) reason about caches, and (c) write a technical blog post.

The artifact spec

Write a C or C++ program that computes C = A @ B for square FP32 matrices of size 1024×1024, 2048×2048, and 4096×4096, and progressively optimizes it through these stages. Each stage MUST be benchmarked and included in the writeup.

Stage

Optimization

Expected speedup vs naive

0

Naive triple-loop

1.0× baseline (~1-2 GFLOPS)

1

Loop reorder (i-k-j)

3-5× (cache-friendly B access)

2

Register blocking (4x4 microkernel)

2-3× more

3

Cache blocking (block size = L1/L2 tuned)

2-3× more

4

SIMD (AVX2 or NEON intrinsics, 8-wide)

4-8× more

5

OpenMP multithreading

~N-core× more

Final

All combined

~50-200× vs naive; within 2-3× of MKL/OpenBLAS

The last row is the money shot. On a modern laptop the naive version does ~1 GFLOPS; MKL does ~200 GFLOPS on 8 cores. Getting to 30-60% of MKL is the achievable target.

Include a roofline plot. X-axis = arithmetic intensity (FLOPs/byte), Y-axis = achieved GFLOPS, horizontal line = peak FLOPS, sloped line = peak bandwidth × AI. Each version of your kernel is a dot on the plot. This plot is what makes the post look serious.

Repo structure

matmul-writeup/
├── README.md              # Blog-quality writeup, embedded numbers + roofline PNG
├── src/
│   ├── v0_naive.c
│   ├── v1_reorder.c
│   ├── v2_register.c
│   ├── v3_cache.c
│   ├── v4_simd.c
│   └── v5_openmp.c
├── bench/
│   ├── run_all.sh         # Pins clocks, sets CPU governor to performance, runs each 10× warmup + 100× measured
│   └── roofline.py        # Regenerates the plot from bench outputs
├── results/
│   ├── raw.csv
│   └── roofline.png
└── ATTRIBUTIONS.md        # Cite Simon Boehm, Stefan Salewski, MIT 6.172

README.md is the blog post. Use headings, tables, code snippets, one hero plot at top.

Where to post

  1. GitHub: github.com/<you>/matmul-writeup. Make it public. Star it yourself so it shows on profile.

  2. Blog: cross-post the README as a blog post on your own site (or dev.to / Substack if you don’t have one yet). Title: “CPU Matmul: from 1 GFLOPS to 60 GFLOPS in six versions.” URLs with GFLOPS in them get clicks.

  3. HN / r/programming: do not post here. This rung is too basic for HN — you’ll get roasted for redoing something that’s been done. Post to your Twitter/X circle instead.

  4. GPU MODE Discord #hip-rocm or #general: share once. Don’t spam.

  5. LinkedIn: skip. Save LinkedIn for rung 5+.

What signals it sends

  • “I can benchmark without embarrassing myself” (fixed clocks, warmups, measured throughput).

  • “I understand the memory hierarchy” (cache blocking, roofline).

  • “I can write about a technical topic in ≤2000 words with real numbers.”

This is a table stakes artifact. Every serious inference engineer has done this or the equivalent. The purpose is to not look like a fake later.

Past examples to study

  • Simon Boehm’s CUDA SGEMM worklog — https://siboehm.com/articles/22/CUDA-MMM. GPU version, but the same structure. Read the whole thing before starting. This is your target quality.

  • MIT 6.172 Performance Engineering — matmul lectures. YouTube search “MIT 6.172 matmul.” Charles Leiserson explains cache blocking end-to-end.

  • BLIS papers — https://github.com/flame/blis — the modern reference. Overkill for rung 1 but skim the design doc.

  • Stefan Salewski Nim/C matmul post — one Google search away. Similar to yours in scope.

Common mistakes

  1. Wrong compiler flags. Use -O3 -march=native -ffast-math for all versions including the naive baseline. Otherwise your “speedup” is fake.

  2. Not pinning clocks. On Linux sudo cpupower frequency-set -g performance. On Mac, disable Turbo Boost and note the clock in the writeup.

  3. Timing hot vs cold. First run has cold caches. Do 10× warmup then 100× timed; report median and P99.

  4. Not verifying correctness. After every version, assert(max_abs_diff(C_new, C_ref) < 1e-3). Speedups on wrong outputs are worthless.

  5. Comparing to BLAS incorrectly. Link against MKL or OpenBLAS, run the same benchmark harness, put it on the same plot. If your best version is 3× slower than MKL, say so honestly. Don’t hide it.

  6. Writing too much. 1500-2500 words. Anything longer is padding. One plot at top, tables in the middle, small conclusion.

Success criteria

  • Repo builds with make on Linux and Mac

  • bench/run_all.sh regenerates all numbers from scratch

  • Roofline PNG in the repo

  • Blog post published somewhere with a permalink

  • At least one person you don’t know reads it and comments or stars

  • You can explain any line of code in a phone study 6 months later

If all six check, ship rung 2.