Chapter 3 — The Real Bottleneck

“Hitting the Memory Wall: Implications of the Obvious” — Wm. A. Wulf and Sally A. McKee, ACM SIGARCH Computer Architecture News, 1995

“For where your treasure is, there your heart will be also.” — Matthew 6:21 (ESV)

Why This Matters

For two weeks you have been studying processors. In Chapter 1 you took a system-on-chip apart block by block and learned to read an AArch64 instruction. In Chapter 2 you learned that not all cores are equal and that placement is a real decision. Both weeks left a promise hanging: the memory hierarchy is where most of your performance actually lives. This is that week.

Here is the fact the week is built on. On a modern mobile system-on-chip the arithmetic is nearly free and the data is expensive — three to four orders of magnitude more expensive in energy, and hundreds of cycles more expensive in time. A core that retires several instructions per cycle will sit stalled for two hundred cycles or more waiting on one word from main memory, and while it waits it still burns static power, still occupies thermal budget, and is still counted as “100% utilized” by every tool that does not know better. Wulf and McKee named this the memory wall thirty years ago and called its implications obvious. They are also the single most consistently ignored thing in a graduate student’s performance analysis.

Run it against The Four Questions. Performance: a cache miss costs more cycles than any branch mispredict or ISA difference you argued about in Week 1. Energy: moving a 32-bit word from DRAM costs orders of magnitude more than adding it to another, so the memory hierarchy, not the ALU, is where the battery goes. Thermals: memory traffic heats the SoC and the DRAM packaged with it, and sustained bandwidth is sustained power. Placement: an accelerator is a machine for not moving data, so you cannot choose a processor until you know how the workload touches memory. That is why the answer to “why is my code slow?” is, more often than any other, memory.

The AI thread this week is the headline, not a garnish. On-device inference is a memory workload wearing a compute costume: the weights must be read out of DRAM to generate every token, the key-value cache grows with every token already generated, and footprint rather than operation count decides whether the model runs on the device at all. Section 3.10 does that arithmetic with code/model-memory.csv and sets up Chapter 4, where you learn that the neural processing unit exists because of §3.9. The second AI register is the one you police in yourself: ask a language model for your phone’s L2 size and it will hand you a confident number with a decimal point in it. Some are right; you will not be able to tell which. This week you measure instead.

And then the question underneath. A cache is not a storage device; it is an argument — a hardware bet, remade every few nanoseconds, about what you will want next, and everything it keeps close it keeps at the expense of something else. Jesus says, “For where your treasure is, there your heart will be also” (Matthew 6:21, ESV). He is not talking about SRAM. He is talking about the same structure: what you keep near reveals, and then shapes, what you actually do. We take that up in §3.14, after the engineering has earned it.

3.1 — The Hierarchy, Top to Bottom

Every level of a memory hierarchy exists because the level below it is too slow, and every level is smaller than the one below because the technology that makes it fast is expensive in area, power, or both. That is the whole design. Memorize the shape, not the numbers.

Take those latencies as orders of magnitude, hedged — they genuinely vary by microarchitecture, generation and vendor. What does not vary is the ratio structure: each step down is a multiple, not a margin, and the step to DRAM is a cliff. Convert to nanoseconds for your own part by dividing by the clock: at 2–3 GHz a cycle is a few hundred picoseconds, so an L1 hit is about a nanosecond and a DRAM access is on the order of a hundred.

Three things a desktop course will not tell you. The SLC is not an L3: an L3 behind the DSU serves the CPU cluster, while a system-level cache sits in front of the memory controller and serves everybody — CPU, GPU, NPU, display, ISP — primarily to keep traffic off the DRAM pins, which is an energy decision before a performance one. The DRAM is thermally coupled: it is frequently packaged on or beside the SoC, which is good for power and signal integrity and means it shares the SoC’s thermal environment (Chapter 5). And there is no swap-to-disk safety net: a server under memory pressure pages to storage and gets slow; a phone kills something (§3.11).

Coach’s Note — Do not memorize cache sizes for any part. Memorize the shape — private and small at the top, shared and large at the bottom, a cliff before DRAM — then measure the machine in front of you. A measured knee in your own data outranks any number either of us could recite.

3.2 — The Cache Line, and Why Spatial Locality Is Not Optional

Caches do not move bytes. They move lines. On essentially all Arm application processors and on x86 a line is 64 bytes; a few designs use 128-byte lines instead, as Apple silicon does on some parts. Read one float and the hardware fetches the whole line containing it, evicts a line to make room, and charges you the full transfer. That single fact turns a software design question into a hardware bill. Define the metric and keep it:

Useful bytes per line = bytes your program actually consumes ÷ bytes the line delivered.

Read one 4-byte float from a 64-byte line and use nothing else in it and your ratio is 4/64 = 6.25%: a full DRAM transaction, and its full energy, for one sixteenth of a transaction’s worth of value. Do that in a loop and you have a program running at a sixteenth of the machine’s bandwidth while every profiler reports the core as busy.

Locality is the word for doing better. Temporal locality means you will touch the same datum again soon; spatial locality means you will touch its neighbours soon, so the rest of the fetched line is not wasted. Temporal locality is a nice-to-have. Spatial locality is the tax structure of the machine — and the commonest place a graduate student loses it is data layout:

struct ParticleAoS {                       // array of structs: 32 bytes each
    float x, y, z, vx, vy, vz, mass;
    std::uint32_t id;
};
std::vector<ParticleAoS> particles(1'000'000);
for (const auto& p : particles) sum += p.x;   // 4 useful bytes per 32-byte struct

struct ParticlesSoA {                      // struct of arrays: one vector per field
    std::vector<float> x, y, z, vx, vy, vz, mass;
    std::vector<std::uint32_t> id;
};
for (float xi : soa.x) sum += xi;             // 16 useful floats per 64-byte line

In the AoS pass each 64-byte line holds two particles, so it delivers 8 useful bytes out of 64 — 12.5%. In the SoA pass every line delivers 64 out of 64, and the loop is trivially vectorizable as a bonus, because the values a SIMD register wants are already adjacent. Same algorithm, same complexity, same instruction count near enough. Eight times the delivered bandwidth.

Neither layout is universally right — a pass touching every field of one particle prefers AoS — which is why this is an architecture decision, not a style rule.

3.3 — Misses: The Three C’s, Associativity, and Replacement

A hit is a reference the cache can serve; a miss must be fetched from further down. The classical taxonomy of misses is thirty years old and still the fastest diagnostic vocabulary in the field:

• Compulsory (cold): the first touch of a line. Unavoidable in principle; reducible only by prefetching or by touching less data.
• Capacity: the working set is larger than the level. This is the miss that draws the staircase you will measure in §3.12.
• Conflict: the data fits, but too many of the lines you need map to the same set, so they evict each other. Entirely an artifact of the indexing scheme.

Conflict misses ambush people, so understand the mechanism. A cache is set-associative: the address of a line selects a set, and the set holds a fixed number of ways. If a level has S sets and 64-byte lines, addresses differing by a multiple of S × 64 land in the same set. Walk float image[1024][1024] down a column — a 4096-byte stride, a large power of two — and every row’s column j lands in the same handful of sets: you are touching a few kilobytes of distinct lines and still thrashing. Padding the row to 1024 + 8 floats, a change that makes the array bigger, can make that loop dramatically faster, because it breaks the alignment causing the collisions. “Make it bigger to make it faster” convinces students the machine is haunted. It is not haunted. It is indexed.

Replacement decides which way in a set to evict. Use LRU as your model, and know that real caches use cheaper approximations — pseudo-LRU and re-reference interval prediction are the usual families. So reason about eviction statistically: you cannot promise the hardware will keep a particular line, only make it likely by touching it often and not blowing the level’s capacity.

3.4 — Private, Shared, and the Bandwidth Cost of Agreeing

Chapter 2 promised you the coherence detail this week. Here it is.

Caches near the core are private; caches further down are shared — the L3 behind the DynamIQ Shared Unit serves the cluster, a system-level cache serves the chip. Private caches are fast because they are close and uncontended; shared caches absorb traffic that would otherwise reach DRAM.

The price of private caches is that two cores can hold copies of the same line, and those copies must agree. That is cache coherence, and you should carry two models of it. The teaching model is MESI/MOESI: every cached line sits in one of a small set of states — Modified, Owned, Exclusive, Shared, Invalid — and the protocol is the bookkeeping that makes a write invalidate every other copy before it lands and a read find the freshest copy wherever it lives. The implementation reality on Arm is the interconnect: the DSU, or the SoC-wide coherent interconnect, is the coherency point and holds a snoop filter — a directory of who has what — so a request need not broadcast to every cache. Arm’s coherent protocols are ACE and CHI; AXI is the non-coherent memory-mapped protocol, with AHB/APB for simpler peripherals. Chapter 6 owns the interconnect; what you need this week is the cost, and the cost is bandwidth — snoop traffic, invalidations and line migrations all consume the same interconnect bandwidth your GPU wants for textures and your NPU wants for weights.

Which brings us to the classic self-inflicted wound. False sharing: two cores write two different variables that happen to share a cache line. Logically there is no sharing at all; physically the line ping-pongs between two L1s, invalidated on every write, at coherence latency instead of L1 latency, forever.

// The bug: two threads, two counters, one cache line.
struct Counters { std::uint64_t a; std::uint64_t b; };   // 16 bytes: same line

// The fix: give each hot counter its own line.
struct alignas(64) Padded { std::uint64_t value; char pad[64 - sizeof(std::uint64_t)]; };

The fix costs bytes, can buy back an order of magnitude of throughput, and is invisible in the source unless you know to look. False sharing is a correctness-preserving, performance-destroying bug that no test will ever catch.

One mobile-specific wrinkle: not every requester is fully coherent with the CPU caches — some accelerators are only I/O-coherent, and some interfaces require explicit cache maintenance around a hand-off, which is why “zero-copy” to an accelerator is sometimes a clean-and-invalidate over a large buffer wearing a zero-copy label.

3.5 — LPDDR, and the Bandwidth Arithmetic You Should Do in Your Head

LPDDR is the low-power branch of the DRAM family, and it is what phones, tablets, wearables and much laptop-class Arm silicon use. What the “LP” buys is not raw speed: lower supply and I/O voltages (a direct V² win, an exponent Chapter 5 will make you feel); aggressive low-power states such as deep power-down and self-refresh, which matter enormously for a device idle most of its life and never off; wider internal prefetch; and packaging — often package-on-package, DRAM sitting on the SoC, with short traces and shared thermals.

As of 2024–2025-generation parts LPDDR5X is mainstream, with data rates commonly quoted around 8533 MT/s and higher-bin parts above that. Treat that as hedged; the arithmetic below is exact:

theoretical peak bytes/s = data rate (MT/s) × bus width (bytes)

Read that table twice. Going from 68 to 273 GB/s there is not a DRAM generation change; it is the same DRAM at the same data rate on a wider bus. Width buys bandwidth, and width costs package pins, board area, controller area and power — which is exactly why a phone does not have it and a laptop does. A volume and energy decision, not a technology gap. When a spec sheet brags about a DRAM generation, ask for the interface width.

Coach’s Note — Theoretical peak is a ceiling nobody reaches. Achieved bandwidth depends on access pattern, refresh, bank and row locality, requests in flight, and who else is on the bus. Report a measurement as a fraction of peak and you are doing engineering; quote peak as though it were a measurement and you are doing marketing.

3.6 — Bandwidth Is Not Latency (and Little’s Law Tells You Why)

These two words get used interchangeably by people who should know better, and conflating them will wreck your analysis. Latency is how long one dependent access takes; you cannot hide it when the next address depends on the current load’s result. Bandwidth is how many bytes per second the system delivers in aggregate, and you can only exploit it with many independent requests outstanding at once.

The bridge between them is memory-level parallelism — how many misses a core can have in flight — plus the prefetchers, which detect a stride and issue loads before you ask. A sequential array walk has enormous MLP and is perfectly prefetchable, so it runs at bandwidth. A linked-list traversal has an MLP of one and is unpredictable by construction, so it runs at latency. Same number of accesses; utterly different performance.

Little’s Law makes it quantitative, and it is the best back-of-envelope tool in this chapter: bytes in flight = bandwidth × latency. Take the phone-class 68 GB/s interface from §3.5 and a DRAM latency on the order of 100 ns. To saturate it you must keep

68e9 bytes/s × 100e-9 s = 6800 bytes in flight
6800 bytes ÷ 64 bytes/line ≈ 106 outstanding line requests

roughly a hundred cache lines in flight at all times. A dependent pointer chase gives you one. That is why a program can idle a 68 GB/s memory system while achieving well under one percent of it, and why “we have plenty of bandwidth headroom” is not an answer to a latency problem. Prefetching, multiple threads and independent access streams are not marginal optimizations; they are the only mechanism by which a bandwidth number becomes real.

You measure both sides in §3.12: code/cache_walk.cpp walks sequentially and gives you a bandwidth staircase; code/pointer_chase.cpp chases a random cycle and gives you the latency staircase. The gap between the curves is your prefetcher and MLP, made visible.

3.7 — Unified Memory: The Copy You Avoid and the Bandwidth You Now Share

In a mobile SoC the CPU, GPU, NPU, ISP and display controller share one physical memory behind one memory controller. This is unified memory architecture, one of the genuinely important structural differences between mobile and classic desktop systems. It has a real win and a real cost, and you should be able to state both.

The win: the copy you do not make. With a discrete GPU across a peripheral bus, handing over a buffer means copying it across, and getting the result back means copying it again. On a unified-memory SoC you can — subject to §3.4’s coherence and alignment rules — hand over a pointer, and the bytes never move. For a camera pipeline passing a full-resolution frame from ISP to GPU to NPU to display, that is the difference between a feasible pipeline and an infeasible one, and the energy saved is precisely the energy of not doing several DRAM round trips (§3.9).

The cost: everything now contends. One controller, one set of DRAM pins, one bandwidth budget, one power budget, one thermal budget. A GPU saturating the bus starves the CPU; an NPU streaming weights starves the GPU. The display controller — hard-deadline, because a missed scanout is a visible glitch — must outrank both, which is why quality-of-service arbitration is not a nicety (Chapter 6). And because bandwidth costs power, power becomes heat, and heat throttles clocks, memory contention on a phone eventually shows up as the CPU getting slower for reasons that have nothing to do with the CPU.

The honest summary: unified memory removes a copy and adds a queue. Whether that is a win depends on whether your workload was copy-bound or bandwidth-bound. Say which, and how you know.

3.8 — Virtual Memory, the TLB, and the Devices That Do Not Go Through You

Sitting on top of the physical caches is the translation machinery, with its own cache, its own miss cost, and its own mobile-specific tuning knob. Each process runs in its own virtual address space; translation goes through multi-level page tables that the hardware itself walks, and the TLB caches recent translations. A TLB miss triggers a page-table walk — several dependent memory accesses, each of which can itself miss in the data caches — so a TLB miss is not “a little slower”; it can cost more than an ordinary cache miss.

The quantity to reason with is TLB reach: reach = TLB entries × page size. Exceed the reach and you take a walk on nearly every access no matter how well your data caches are doing. This is why AArch64’s translation granules matter architecturally. The architecture supports 4 KB, 16 KB, and 64 KB. Apple platforms use 16 KB pages; mainline Android and Linux have historically used 4 KB with 16 KB support arriving in recent generations — treat that second claim as generation-dependent and check the documentation for your target. Quadrupling the granule quadruples the reach for the same number of entries and shortens the walk; it also coarsens allocation and increases internal fragmentation. A real trade, made once, per platform, for everybody.

It is also why very large strides are a translation experiment as much as a data one: past a certain stride every access lands not only on a new line but on a new page, so a TLB miss and a page-table walk ride on top of the memory access. Be careful reading that off §3.12’s sweep, though, because raising the stride moves two things at once. The bytes a single pass actually touches are working set ÷ stride × line size — so a wider stride spans the same addresses while touching less data, and that shrinking footprint can slide back inside a cache faster than the translation cost grows. The right-hand end of a large-stride curve may therefore flatten, or sit below the same working set measured at a smaller stride, rather than flaring. Isolating TLB reach honestly means holding the touched footprint fixed while spreading it across more pages; the bench does not do that, and Rep 2 asks you what your own numbers actually show.

Memory-mapped I/O and DMA, briefly, because Chapter 6 owns them. Device registers live in the physical address space, so a load or store to the right address is a device transaction — hence volatile and memory barriers. DMA moves bulk data without CPU cycles, and an SMMU/IOMMU confines each device to the buffers it was given (Chapter 7). This week’s consequence: a DMA engine writing into memory is another bandwidth consumer and another coherence participant, and it does not appear in your CPU profiler at all.

3.9 — Why Moving a Word Costs More Than Computing On It

This is the headline of Week 3, and half of Week 4 follows from it.

The reference is Mark Horowitz, “Computing’s Energy Problem (and what we can do about it),” ISSCC 2014 — a real, widely cited keynote whose energy table has been reproduced across a decade of architecture papers. At 45 nm, and stated as orders of magnitude rather than precise values:

A DRAM access costs roughly three to four orders of magnitude more energy than the arithmetic you will perform on the value you fetched, and a small on-chip SRAM read costs tens of times more than the add but hundreds of times less than going off-chip. The absolute numbers move with process node — these are 45 nm figures — but the ordering, and the size of the gap, has not been overturned. Data movement dominates the energy budget of computation.

Run that against The Four Questions. On energy, the highest-leverage move for doing more work per joule is not a faster multiplier; it is not fetching the operand from DRAM. On performance, the same conclusion from the other direction: the stall is the cost. On thermals, energy per second is power and power is heat. And on placement, the payoff. An accelerator is, at bottom, a machine for not moving data. That explains two things that otherwise look like unrelated vendor quirks. A tile-based GPU renders into small, fast on-chip tile memory and writes only the finished tile out to DRAM, instead of reading and writing a full-resolution framebuffer and depth buffer in DRAM the way immediate-mode desktop rendering does — it exists to save external memory traffic, and therefore energy. An NPU is a matrix engine wrapped in a dataflow designed to maximize reuse of every value it fetched: load a weight once, consume it in as many multiply-accumulates as possible, then let it go. Its advantage over a CPU is only partly more multipliers; mostly it moves each byte fewer times. Chapter 4 treats both properly.

Specialized silicon is not primarily faster arithmetic; it is cheaper data movement. When Chapter 4 shows you a TOPS figure, the question this chapter equips you to ask is at what memory traffic?

Coach’s Note — This is the section that turns a student into an architect. Once you genuinely believe the fetch costs a thousand times the flop, you stop counting operations and start counting bytes moved, and how many times each one moved. That is the accounting real architects do, and it makes the rest of this book read as one argument instead of eight topics.

3.10 — The On-Device Model Is a Memory Problem in a Compute Costume

On-device inference is the defining new mobile workload, and the popular framing of it is wrong. It gets discussed as a compute problem — TOPS, matrix engines, “AI performance” — when token generation in a decoder-only transformer is, in practice, usually memory-bound.

Weights. The footprint is exact: weight bytes = parameters × bytes per weight. FP32 is 4 bytes, FP16/BF16 is 2, INT8 is 1, INT4 is 0.5 — so INT8 is exactly a 4× reduction against FP32, arithmetic rather than a benchmark. Chapter 4 covers what quantization costs in accuracy: “it depends on the model and the task, and you must measure it.”

The KV cache. Every token already generated leaves a key and a value tensor per layer, kept for the rest of the sequence:

KV bytes = 2 × layers × sequence_length × kv_width × bytes_per_element

The 2 is one K tensor and one V tensor; kv_width is n_kv_heads × head_dim. The property people miss: the KV cache grows linearly with context length while the weights do not grow at all. At short contexts it rounds to nothing; at long contexts it can exceed the weights.

The dataset code/model-memory.csv puts numbers on both for deliberately fictional generic shapes, gen-0.5b through gen-8b. Its first line declares what it is — # SYNTHETIC TEACHING DATA — modeled on published behavior, not a measurement of any specific product. Every figure in it is arithmetic you can redo from the formulas above, and the assumed layer counts and KV widths are in the file’s comment block. It is modeled, not measured, and Appendix B documents it as such. Week 8 grades you on knowing the difference.

Now the payoff. Generating one token requires reading essentially all the model’s weights out of memory once, so there is a hard ceiling: tokens per second ≤ memory bandwidth ÷ weight bytes. Take gen-7b at INT4 from the dataset — 3337.9 MiB of weights, about 3.5 GB — on the phone-class 68 GB/s interface from §3.5:

68 GB/s ÷ 3.5 GB ≈ 19 tokens/s   (an upper bound, ignoring everything else)

That ceiling is set by bandwidth alone, with a perfect accelerator, no cache misses, no other bus traffic, no throttling and no runtime overhead; the real number will be lower. Notice what it does not depend on: how many multipliers the NPU has. Double the arithmetic throughput and it does not move. This is why quantization is a bandwidth technique before it is a capacity technique — halving the bytes per weight roughly doubles the ceiling.

Three consequences for Chapter 4. Footprint decides feasibility — real total memory is weights plus KV cache plus activations plus runtime plus framework plus the OS’s own needs, on a device that kills you rather than swapping you (§3.11), so total_mib is a floor and you must say so. Bandwidth decides speed. Reuse decides energy (§3.9) — which is why Chapter 4’s NPU dataflow section continues this one rather than starting a new topic.

Coach’s Note — When someone says a device “runs a 7-billion-parameter model,” the two questions that separate an architect from an enthusiast are: at what precision, and at what context length. The first sets the weight footprint and the bandwidth ceiling; the second sets the KV cache. Without both the claim has no content — and you now have the arithmetic to check the answer.

3.11 — Memory Pressure, NAND, and Why a Phone Cannot Swap Its Way Out

A server low on memory pages cold anonymous memory out to storage and becomes slow. A phone does something else: it kills things.

The reason is a stack of hardware facts, not a software preference. NAND has finite program/erase endurance, so treating it as swap wears it out. Flash writes are slow and, worse, variable — a write that triggers garbage collection can stall far longer than its average — and they cost meaningful energy and heat. A page-in from flash is microseconds to milliseconds against a DRAM access of tens of nanoseconds: not a slowdown but a different regime. So both major mobile platforms answer sustained memory pressure primarily by terminating background processes. The mechanism’s name and policy differ by platform and generation — Android has used a low-memory-killer mechanism (historically an in-kernel driver, later a userspace daemon) together with compressed in-memory swap, which trades CPU cycles for capacity without touching flash — so check the documentation for your target rather than trusting a remembered detail. The architectural consequence: your process’s continued existence is a resource the system may reclaim, which is why mobile application lifecycles are built around save-and-restore rather than “stay resident.”

Which brings us to the bottom of the hierarchy. NAND flash is programmed in pages and erased in blocks, and a block is much larger than a page — you cannot overwrite a page in place, you must erase its whole block first. Everything strange about flash follows: a flash translation layer maps logical addresses to physical pages; write amplification means writing a little logical data can force reading, erasing and rewriting far more; wear levelling spreads erases so no block dies first; garbage collection reclaims blocks in the background, competing with your foreground I/O, which is why flash latency has a long tail that averages hide. UFS is the mobile storage interface: serial, full-duplex, with command queuing — contrast the older, half-duplex eMMC. UFS 4.0 (2022) roughly doubled the per-lane rate over UFS 3.1, and real-world sequential reads land in the low single-digit GB/s. Hedge those; check the part.

Two consequences a desktop architect can forget: storage is a thermal and power actor (a sustained large write heats up and can itself throttle), and storage sets your cold-start time — loading a multi-gigabyte model file before the first token is generated is a large sequential read, which at low-single-digit GB/s is seconds, not milliseconds. The user calls that “the AI feature is slow,” and no NPU will fix it.

3.12 — The Bench: Three Programs That Prove All of It

Everything above is claims. Here is how you turn them into data. Toolchain setup is Appendix A; all of this runs on Workbench L (a laptop) or Workbench B (a cloud dev environment) with nothing but a C++17 compiler and Python 3.

g++ -O2 -std=c++17 -o cache_walk code/cache_walk.cpp && ./cache_walk    > cache-walk.csv
g++ -O2 -std=c++17 -o chase      code/pointer_chase.cpp && ./chase      > chase.csv
g++ -O2 -std=c++17 -o matmul     code/matmul_order.cpp && ./matmul 512

python3 code/hierarchy_plot.py cache-walk.csv     # then again on chase.csv

Defeating the optimizer, which is not optional

Each program computes a result nobody uses, and a modern compiler is within its rights to notice that and delete your benchmark — at which point you measure an empty loop and report a machine with an eight-picosecond memory system. All three therefore carry a barrier:

inline void consume(std::uint64_t v) {
#if defined(__GNUC__) || defined(__clang__)
    asm volatile("" : : "r"(v) : "memory");
#else
    g_sink = v;
#endif
}

The empty asm volatile emits no instructions. The "r"(v) constraint says the value must exist in a register at that point, so the loads that produced it cannot be deleted; the "memory" clobber says memory may have changed, so the loop’s loads cannot be hoisted across repetitions. If a benchmark result looks impossibly good, suspect the optimizer before you believe the machine. Two further pieces of hygiene are built in, and Appendix C explains why each is mandatory: never report a first run, and never report a single one. The two staircase programs do both explicitly — a discarded warm-up pass, then a median of five timed trials. matmul_order.cpp gets there with one mechanism instead of two: three timed repetitions and a median of three, which by construction discards the slowest and the fastest, so a cold first pass never becomes the reported number. Neither shape is wrong. Reporting one and doing the other is.

cache_walk.cpp — the bandwidth staircase

code/cache_walk.cpp walks an array with a fixed byte stride over working sets doubling from 4 KiB to 128 MiB and prints nanoseconds per access. The default stride is 128 bytes, not 64, for a reason worth understanding: 64 bytes is the line size on essentially all Arm application processors and on x86, but a few designs use 128-byte lines, and a 64-byte stride on a 128-byte line gives two touches per line — so half your accesses would measure line reuse rather than line cost, and the staircase flattens. Stepping 128 guarantees at most one useful touch per line on either machine; run it both ways and the difference is your line size talking. Because the walk is sequential and predictable the prefetcher does its job, so you measure something closer to a bandwidth curve than a latency curve.

Illustrative shape, your numbers will differ:

 working set  ns/access  x prev
       4 KiB       0.3     1.00   <- everything fits in L1
     256 KiB       0.6     2.00   <- STEP: past L1
       4 MiB       1.0     1.60   <- STEP: past L2
      64 MiB       4.0     2.20   <- STEP: past the last cache, streaming DRAM
     128 MiB       4.5     1.10

Flat regions are levels; steps are capacity boundaries. The plotter code/hierarchy_plot.py finds the steps, prints an ASCII chart, and lists the inferred boundaries — labelled, correctly, as a hypothesis rather than a datasheet reading.

pointer_chase.cpp — the latency staircase

code/pointer_chase.cpp builds a single random cycle through the working set — every node points to the next, in a shuffled order — and chases it. Each load’s address comes from the previous load’s result, so memory-level parallelism is exactly one and no stride predictor helps: it measures true load-to-use latency. Two implementation details are load-bearing. Node spacing is 64 bytes, so the bytes touched equal the working set regardless of the machine’s line size. And the timed unit is a full lap, never a partial one — time 200,000 hops on a 128 MiB ring and you have quietly measured a 12 MiB footprint that fits in cache, and reported a beautiful, completely wrong number.

Illustrative shape, your numbers will differ:

 working set  ns/access  x prev
       4 KiB       1.0     1.00
     128 KiB       3.5     3.20   <- STEP: past L1
       2 MiB      12.0     3.10   <- STEP: past L2
      16 MiB      60.0     3.60   <- STEP: past the last cache
     128 MiB     100.0     1.05

Compare the two staircases: their difference is the lesson. The chase’s spread from L1 to DRAM will be dramatically larger than the strided walk’s — same hardware, same number of accesses, the only difference being whether the machine could see the next address coming. That gap is your prefetcher and MLP, quantified.

matmul_order.cpp — “fewer instructions” loses

code/matmul_order.cpp multiplies two N × N float matrices twice, once in ijk order and once in ikj. Both perform exactly N³ multiply-accumulates on the same values, and the program prints both checksums so you can confirm it. The only difference is loop order, so the only difference is memory access. In ijk the inner loop runs over k, so B[k*N+j] strides by N floats: one useful float per line fetched, spatial locality destroyed. In ikj the inner loop runs over j, so B[k*N+j] and C[i*N+j] walk contiguously and A[i*N+k] is loop-invariant: every byte of every line gets used — and the inner loop becomes trivially vectorizable, because locality is what makes SIMD possible in the first place.

Expect a multiple, not a margin, and report both mechanisms: ikj wins on locality, and wins again because that locality unlocked vectorization. One caution that is itself a lesson — build this at -O2. Some compilers perform loop interchange at -O3 and erase the very effect you are trying to observe. Record what your compiler did: a benchmark without its build flags is not a result.

Coach’s Note — One discipline governs all three: write your prediction down before you run anything. Predict-before-you-measure is the only mechanism by which a measurement can surprise you, and surprise is the entire information content of an experiment.

3.13 — Interactive Lab: The Memory Wall Walker

Below this chapter you will find The Memory Wall Walker. It is part of the chapter, not an extra. Use it after §3.12’s programs, so you can check the simulator’s story against your own data. The main panel gives you three controls: working-set size, access pattern (sequential, strided, or random), and cache-line reuse — how many bytes of each fetched line your code actually consumes. Set them and the widget reports which level serves the access, estimated nanoseconds and picojoules per access, and the resulting effective bandwidth, all against a running “compute-only” baseline so the energy gap from §3.9 is visible as a number rather than a claim. Drive it deliberately: hold the working set fixed and sweep the pattern to isolate the prefetcher, then hold the pattern fixed and sweep the working set to walk down the staircase you measured yourself. The second panel is the array-of-structs versus struct-of-arrays toggle from §3.2 — flip it and watch useful-bytes-per-line move, and with it the effective bandwidth for identical logical work.

What the widget cannot teach is your actual machine. The model is a model; your staircase is data. When they disagree the data wins, and why is a far better report than “as expected.”

3.14 — Where Your Treasure Is

A cache knows nothing. It cannot see the future and it holds no opinions. And yet the only honest way to describe what a cache does is in the language of expectation: it keeps near what it believes you will want, at a cost, in limited room, by discarding something else. Every line resident in L1 is a claim that this datum matters more, right now, than every datum evicted for it. The hierarchy is not a filing system. It is a standing argument about value.

That is why Matthew 6:21 is the right verse for a chapter on memory, and not merely a pun on “treasure.” Jesus says, “For where your treasure is, there your heart will be also” (Matthew 6:21, ESV). Notice the direction of the sentence. We assume the heart chooses first and the treasure follows. He says the opposite: locate the treasure and you have located the heart. What you keep near is not a consequence of what you love; it is diagnostic of it, and over time formative of it. The placement is the evidence — which is exactly how we read silicon. You cannot ask a chip what it values; you read the floorplan. Area spent on cache is a bet about locality; a fixed-function video block is a bet that people will watch video; a system-level cache is a bet that keeping traffic off the DRAM pins is worth the SRAM it costs. Nobody writes those beliefs down; they are legible anyway, in what got kept close.

Two things follow, and I want both, because either alone is a sermon rather than an argument. The first is about finitude, and it is good news. A cache is not small because its designers were lazy. It is small because fast is expensive, expensive means area, area means power, power means heat, and heat means a phone you cannot hold. The limit is real, it was not chosen, and it cannot be argued away — and it is precisely the limit that produces the craft, because an infinite cache would need no replacement policy, no associativity, no thought about layout. In Chapter 1 you met that idea as a boundary set from outside; here is its constructive half. A finite capacity forces a real decision about what matters, and a real decision about what matters is the beginning of every serious craft. Nobody has infinite hours, attention, or capacity for care either. That is not the tragedy of a life; it is the condition of a life having a shape at all.

The second is the hard edge, and an engineer should feel it before a Christian does. Locality is a bet, and a bet can be wrong. A cache that keeps the wrong lines close does not fail loudly. It fails as a persistent, invisible tax — every access a little more expensive than it should be, every profiler still reporting the core as busy, nothing crashing. The machine works; it works badly, forever, because it holds close what it does not use and re-fetches what it does. That is a precise picture of a misordered life, and it is why the verse is a warning as much as an observation: the failure is quiet, it compounds, and it is visible only if you go and measure.

Which is the habit this chapter exists to install: you do not get to assume your locality is good, you go and look at what your program keeps close and what it re-fetches. The examined version of that question — what am I actually keeping close? — is older than computing, and it has never once been answered honestly by assumption either.

3.15 — Common Pitfalls

Pitfall: Counting instructions instead of counting memory traffic. Example: A student “optimizes” a kernel from 12 operations per element to 9 and reports a 25% improvement the wall clock refuses to confirm — the kernel was stalled on DRAM throughout and the ALU had cycles to spare. Fix: Establish whether you are memory-bound before optimizing arithmetic. Compute bytes moved per unit of work, compare against §3.5’s bandwidth arithmetic, and check whether removing work changes the time. If it does not, the arithmetic was never the cost.

Pitfall: Reporting theoretical peak bandwidth as though it were a measurement. Example: “This part has 68 GB/s of memory bandwidth” appears in a report with no access pattern, no measurement, and no acknowledgement that a dependent chase would achieve well under one percent of it. Fix: Quote peak as peak and measured as measured, always with the access pattern that produced it. Little’s Law (§3.6) tells you how many outstanding requests the peak demands; if your workload cannot supply them, the peak is not available to you.

Pitfall: Measuring a benchmark the compiler deleted, or a working set you never actually touched. Example: A cache walk reports 0.02 ns per access on a 3 GHz machine — a physically impossible sixteen accesses per cycle. Or a chase over a 128 MiB ring is timed for 200,000 hops, touches about 12 MiB, and returns a “DRAM latency” of 4 ns. Fix: Use the §3.12 barrier, confirm the result is consumed, sanity-check every number against the clock period, and make the timed unit a whole lap of the structure rather than a fixed hop count.

Pitfall: Trusting a language model for a cache size, a latency, or a bandwidth figure. Example: A report states “the L2 is 4 MB per core” because a model said so, confidently, with a plausible generation name attached. No vendor page says it, and nothing in the student’s own data supports it. Fix: Every figure is either cited to a primary source — a vendor specification page, an architecture reference manual — or measured by you, with the method stated. Use AI to explain a mechanism; never to source a number. Appendix D treats a fabricated figure as an integrity failure, not a deduction.

Pitfall: Sizing an on-device model by parameter count alone. Example: “It’s a 7B model and we have 8 GB, so it fits” — stated with no precision, no context length, and no room for the operating system. Fix: Do the §3.10 arithmetic: parameters × bytes-per-weight, plus the KV cache at your context length, plus activations, runtime and framework, on a device that terminates processes rather than swapping (§3.11). Then check the bandwidth ceiling separately — fitting and being fast are different questions.

3.16 — Reps

Open the reps and do all of them. This week’s conditioning is literal: build a measurement bench, take real data on your own machine, learn to read a staircase. The reps are where the project’s numbers come from.

This week’s AI policy. Use AI to explain a mechanism you did not follow — set-associativity, Little’s Law, why a KV cache grows. Never use it to source a figure: every number in your deliverables is either measured by you, with the method recorded, or cited to a primary source you actually opened. Rep 10 makes this explicit by having you catch a fabricated figure on purpose. Each deliverable ends with the AI-usage note defined in Appendix D.

A preview:

• Rep 1 — Build the bench and take your first cache staircase, predicting the knees before you look.
• Rep 3 — Chase pointers and separate true latency from prefetched bandwidth by comparing the two curves.
• Rep 4 — Loop order: make ijk lose to ikj on identical arithmetic, then explain both mechanisms behind the win.
• Rep 7 — Do the bandwidth arithmetic by hand — MT/s times bus bytes, then Little’s Law for requests in flight.
• Rep 10 — Verify a cache-size claim from a language model against a primary source and your own measurement.

A short “Check Your Reps” quiz is embedded on this page below the lab. It is an ungraded self-check; take it before you move on. Then sit this week’s graded knowledge check in Canvas — worth 1.5%, same material, larger pool, randomized draw, so retaking it is real practice rather than memorization.

3.17 — This Week’s Project

This week’s lab is Project 3 — The Memory Wall Lab, worth 7%, like every weekly lab.

You will run all three programs on your own machine, record every run in a measurement log with medians and dispersion per Appendix C, and infer your machine’s cache hierarchy from your own data, stating each boundary as a hypothesis with the evidence behind it. Then the graded core, which is reasoning rather than measurement: predict how each of your three results would differ on a phone-class SoC, and say why, in the vocabulary of The Four Questions. The deliverables are report.docx and measurements.xlsx, plus the ai-usage.txt note.

Medium tier hands you a cache-hostile kernel and asks you to make it substantially faster without changing its asymptotic complexity, proved with before-and-after measurements. Hard tier is the judgment piece: a memory-budget memo for an on-device model, built on code/model-memory.csv arithmetic, choosing a precision and a context length for a stated budget and defending it on footprint, bandwidth ceiling, and what you would need to measure on real hardware to confirm it.

3.18 — Coach’s Final Word

You came into this week able to read a block diagram and reason about core placement. You leave it with the habit that will make you useful: asking, of any workload, where does the data live, how far does it move, and how many times? Look at what you can do now. You can name the levels of a hierarchy and the order of magnitude between them without reciting a vendor’s marketing. You can compute useful-bytes-per-line, tell a capacity miss from a conflict miss, do the bandwidth arithmetic, and use Little’s Law to say whether your workload can reach that number. You can state, with a citation, that moving a word from DRAM costs orders of magnitude more energy than the arithmetic performed on it — and derive from that one fact why accelerators exist at all. And you can size an on-device model in weights and KV cache and compute its bandwidth ceiling, which a great many working engineers cannot.

Most of all, you measured. You built a bench, defeated the optimizer, took the median of five, and drew a staircase out of your own machine. That staircase is yours — not a figure from a textbook or a number a model recited with unearned confidence, but data, taken under conditions you recorded, that you can defend. Chapter 8 will ask you to do it for a whole system.

Next week, the accelerator fleet — which is not a new topic. It is §3.9 with more silicon: every accelerator in Chapter 4 is an answer to the energy cost of a fetch. Then Chapter 5 shows you the budget that governs all of it.

Where your treasure is, there your heart will be also. Measure what you actually keep close. It will tell you the truth about your program, and it is a question worth asking about more than programs.

See you next week.

Up next: Do the reps — the bench you build there is the bench the project grades. Then open Project 3 — The Memory Wall Lab and measure your own machine. Toolchain: Appendix A. Dataset provenance: Appendix B. Measurement-log format, repetition and median rules, reporting template: Appendix C. Grading and the AI policy: Appendix D. Anything you cannot name: Appendix E. After that, Chapter 4 — beyond the CPU: the accelerator fleet, and the week the midterm lands.

Previously: Chapter 2 — not all cores are equal: heterogeneous multicore and the cost of placement.