01 — Computer Systems: The Non-Negotiable Substrate

“You are not learning CS:APP. You are memorizing the memory hierarchy so hard that GPU shared memory feels obvious.”

Why This Is First

GPUs are not a different kind of computer. They are the same von Neumann substrate with an aggressive memory hierarchy, more parallelism, and less patience. Every GPU optimization has a CPU analogue: coalesced global loads ↔ cache-line-aligned access, shared memory ↔ L1, warp divergence ↔ branch prediction failure, bank conflicts ↔ false sharing. If you learn these on the CPU first — where you can printf and perf stat freely — the GPU version becomes a familiar dialect instead of an alien language.

Specifically, you need to be able to answer, cold:

  • What is a cache line? What size on modern x86? (64 bytes.) On ARM? (64 or 128.)

  • What is the latency, in cycles, of an L1 hit? L2? L3? DRAM? (~4 / ~12 / ~40 / ~200+.)

  • What does “pointer chasing is slow” mean in terms of the pipeline stalling on load-use dependency?

  • What is virtual memory? TLB? Huge pages? Why does mmap a 100GB file work at all?

  • What is a data race, and how does std::atomic differ from volatile? (Trick: volatile is not for threading.)

Canonical Resource: CS:APP

Book: Computer Systems: A Programmer’s Perspective, Bryant & O’Hallaron, 3rd edition (2015). The 4th edition is drafted but the 3rd is what CMU 15-213 has taught against for a decade.

Chapters that matter for this roadmap (skip the rest for now, come back later):

Chapter

Why

2. Representing and Manipulating Information

IEEE 754, two’s complement, endianness. Do the practice problems on float representation — this is the same skill you’ll need for bf16/fp8.

3. Machine-Level Representation of Programs

You need to be able to read x86-64 assembly at a squint. You don’t need to write it.

5. Optimizing Program Performance

The entire chapter is a manifesto against premature optimization and for measuring first. Read it twice.

6. The Memory Hierarchy

The most important chapter in the book for you. Caches, blocking, spatial vs temporal locality, tiled matmul on the CPU. This is the Rosetta Stone for every GPU optimization you’ll do.

9. Virtual Memory

Because PagedAttention (Phase 4) is virtual memory reinvented for KV cache.

12. Concurrent Programming

GIL context, why lock-free is hard, memory ordering.

Course materials from CMU 15-213 (public):

  • Course page: http://www.cs.cmu.edu/~213/ (schedules rotate; the labs are stable)

  • Lecture videos on YouTube: search “CMU 15-213” for Randy Bryant / Greg Kesden recordings.

The Two Labs You Must Do

Cache Lab (~10 hours):

  • Handout PDF (stable URL): https://csapp.cs.cmu.edu/2e/cachelab.pdf

  • Part A: simulate an LRU cache and produce hit/miss/eviction counts on given trace files. This is where cache mechanics become physical intuition.

  • Part B: optimize a 32×32, 64×64, and 61×67 matrix transpose for a direct-mapped cache. This tiny problem previews every kernel decision you’ll ever make: blocking, avoiding conflict misses, spatial locality.

  • Reference solutions to compare against (only after your own attempt): https://github.com/JasonQSY/CMU-15-213-ICS

Malloc Lab (~20–30 hours):

  • Widely called the hardest single programming assignment at CMU. Implement malloc, free, realloc from scratch — explicit/segregated free lists, boundary tags, coalescing.

  • Direct payoff: when you later read vLLM’s block manager or llama.cpp’s arena allocator, you will recognize the data structures instead of decoding them.

  • Handout: linked from the CMU 15-213 course page.

If you have to skip one lab, keep Cache Lab. Malloc Lab is transformative but Cache Lab is essential.

Modern Alternatives (if you’re time-constrained)

You probably shouldn’t skip CS:APP entirely on a 13-month timeline — the ROI is that high — but if you must compress:

  • MIT 6.004 “Computation Structures” (edX / OCW): shorter, more circuit-flavored, less memory-hierarchy depth. Good if you want the hardware substrate story.

  • UC Berkeley CS61C “Great Ideas in Computer Architecture”: recorded lectures on YouTube. More modern pacing than CS:APP; good videos on caches and virtual memory.

  • Jon Gjengset’s “Crust of Rust” and “Decrusting” series for concurrency intuition in Rust idiom (transfers to modern C++).

  • “Latency Numbers Every Programmer Should Know” (Jeff Dean, updated by Colin Scott: https://colin-scott.github.io/personal_website/research/interactive_latency.html). Read it, then extend the table yourself for your target GPU:

L1 cache reference                    ~0.5 ns
Branch mispredict                     ~5   ns
L2 cache reference                    ~7   ns
Mutex lock/unlock                    ~25   ns
Main memory reference (DDR)         ~100   ns
GPU shared memory (~L1)              ~30   ns (~20 cycles @ 1.5GHz)
GPU L2                              ~200   ns
GPU HBM3 (H100)                    ~400–600 ns
NVLink small-message                 ~1–2 μs
InfiniBand RDMA small-message        ~2–5 μs
Cross-datacenter                    ~150   ms

Pin this table above your desk. Every optimization you make in Phases 2–4 is a story about which line you’re moving work between.

Profiling Tools You Must Own

You already do long-running services at Zoho, so you probably know htop and strace. Add these:

perf (Linux perf_events)

The universal profiler. Learn the four incantations:

# CPU cycles and instructions
perf stat -e cycles,instructions,cache-references,cache-misses,LLC-load-misses ./a.out

# Sampling profile
perf record -F 999 -g ./a.out
perf report

# Flamegraph (requires Brendan Gregg's FlameGraph repo)
perf record -F 999 -g ./a.out
perf script | stackcollapse-perf.pl | flamegraph.pl > flame.svg

# Instructions per cycle (IPC) — the single best CPU efficiency number
perf stat -e cycles,instructions ./a.out  # IPC = instructions / cycles

Drill: run the naive vs tiled matmul from Phase 0.4 under perf stat -e cache-misses,LLC-load-misses and predict the ratio before you look. It should be ~5–10×.

Flamegraphs (Brendan Gregg)

htop, iostat, numastat, nvidia-smi, nvtop

Survival-level fluency in each. numastat matters more than most people realize: NUMA effects on multi-socket servers can silently halve your throughput.

Later (Phase 2): Nsight Compute + Nsight Systems

Don’t touch these yet. They will make more sense when you have kernels to profile.

The Modern Reading List

Beyond CS:APP, these are the writings that will shape how you think:

  1. Horace He, “Making Deep Learning Go Brrrr From First Principles” — not exactly “systems” but the ethos of the whole roadmap. Compute-bound vs memory-bound vs overhead-bound. Read it now, re-read it after Phase 3. Host: horace.io / thonking.ai. (URL migrates occasionally; search “Horace He Brrr first principles”.)

  2. Brendan Gregg’s USE method: https://www.brendangregg.com/usemethod.html

  3. Ulrich Drepper, “What Every Programmer Should Know About Memory” (2007, but the physics hasn’t changed): https://people.freebsd.org/~lstewart/articles/cpumemory.pdf. Long. Skim parts 1–3; the rest as reference.

  4. Fabian Giesen’s blog (fgiesen.wordpress.com) — low-level performance essays; his “Reading bits in far too many ways” is a masterclass in bit-twiddling.

  5. Agner Fog’s optimization manuals (agner.org/optimize/): the reference for x86 micro-architecture. You will not read these front to back. You will reach for them when you need to know something exact.

Exit Deliverable for This File

Commit to a public gist or your portfolio repo:

  1. cache_lab.md — your Cache Lab Part A + Part B solutions with a paragraph explaining every optimization.

  2. latency_table.md — the latency numbers table above, filled in for your CPU (measure with lat_mem_rd from lmbench or sysbench memory) and your target GPU.

  3. perf_intro.md — a one-page cheatsheet of the four perf incantations you actually use, with output from a real profile you did.

When you can teach a junior engineer why for (i) for (j) A[i][j] is 10× slower than for (j) for (i) A[i][j] on a big matrix, with a flame graph to prove it, this file is done.