Lab 02 — Memory Hierarchy & Roofline Microbenchmarks (C)

Phase: 01 — GPU Architecture | Difficulty: ⭐⭐⭐☆☆ | Time: 3–5 hours Language: C11 + make | Hardware: any CPU (the methodology transfers to GPU)

Concept primer: ../WARMUP.md Ch. 6–7 (memory hierarchy, roofline), ../HITCHHIKERS-GUIDE.md §4–5.

Run

make
./membench            # latency curve + bandwidth + roofline placement

0. The mission

Stop trusting tables — measure a memory hierarchy yourself, with the same two techniques every GPU microbenchmarking paper uses (e.g., Jia et al.'s Volta dissection):

1. Pointer-chasing measures latency: each load's address depends on the previous load's value, so the CPU cannot overlap or prefetch — you see the raw round-trip per level.
2. Streaming measures bandwidth: independent sequential accesses let the hardware pipeline everything — you see the peak transfer rate.

Then you place two kernels on your machine's roofline and verify the model predicts which one is memory-bound. This is the exact methodology you'd use to characterize an unknown accelerator a vendor hands you (WARMUP Ch. 10).

1. What the program does

• Latency sweep: builds a randomly-permuted cycle of pointers in buffers from 4 KB to 256 MB and chases it 10M times. Plotting ns/load vs buffer size shows plateaus at each cache level, with cliffs between them.
• Bandwidth: streams a large array (read-sum, then memcpy-style write) and reports GB/s.
• Roofline placement: times vector_add (AI ≈ 0.083 FLOP/byte) and a blocked matmul (AI grows with block size), converts to GFLOP/s, and prints where each lands relative to min(peak, AI × measured_bandwidth).

Example output (Apple M-series; your numbers will differ — that's the point):

== latency (pointer chase) ==
     4 KB     1.2 ns/load     <- L1
   128 KB     3.1 ns/load     <- L2
     8 MB     9.8 ns/load     <- SLC/L3
   256 MB    98.4 ns/load     <- DRAM
== bandwidth (stream) ==
read  : 61.2 GB/s   write : 38.9 GB/s
== roofline ==
vector_add: AI=0.083  predicted ceiling  5.1 GFLOP/s  measured  4.7  -> memory-bound (92% of roof)
matmul b=64: AI≈10.7  measured 41.3 GFLOP/s           -> compute-bound region

2. Fill in ROOFLINE.md

The worksheet asks you to:

1. Identify each plateau and match it to your CPU's published cache sizes.
2. Compute your CPU's ridge point from measured bandwidth + estimated peak (cores × clock × SIMD width × 2 FLOPs).
3. Compute A100 and H100 ridge points from their spec sheets (WARMUP Ch. 7 has the answers — derive before checking).
4. Place batch-1 LLM decode (AI ≈ 2) on the H100 roofline and write the three-sentence implication (this is Phase 07's thesis statement).

3. Why the methodology transfers to GPUs

4. Common pitfalls

1. Sequential pointer chase — the prefetcher hides DRAM latency and you'll "measure" L1 everywhere. The permutation must be random. (Try it: replace the shuffle with identity and watch the curve flatten — instructive!)
2. Compiler deleting your loop — the chase result must feed a volatile sink or the optimizer removes everything. Same trick JMH uses (Blackhole), same trick you'll need in CUDA benchmarks.
3. Timing one pass — too noisy; the harness does warmup + multiple reps and reports the minimum (least-disturbed) run.
4. Forgetting -O2 — at -O0 you're benchmarking the compiler's laziness, not the memory system.

5. Extensions

• Add a strided read benchmark (stride 1, 2, 4, … 128 elements) and find the cliff at your cache-line size (64 B): past it, every load is a new line and bandwidth collapses by the stride factor. This is exactly the GPU coalescing argument of Phase 02 — uncoalesced access wastes the same way.
• Run under taskset -c 0 vs a core on another socket/cluster (Linux) and observe NUMA / cluster effects.
• Use perf stat -e cache-misses,cache-references ./membench and correlate the counters with your plateaus.

6. What this lab proves about you

You can characterize any memory system — CPU today, an OEM partner's accelerator next quarter — with two from-scratch benchmarks and place workloads on its roofline before a single line of vendor marketing reaches your team.