Locality & the Memory Hierarchy

Computer pioneers correctly predicted that programmers would want unlimited amounts of fast memory. The economical answer is a hierarchy that exploits locality and the cost/speed trade-offs of different memory technologies.

The principle of locality

Programs don't touch all code and data uniformly. They exhibit two kinds of locality, and every level of the hierarchy is a bet on one or both:

• Temporal locality: a byte referenced now is likely referenced again soon. (Loop counters, hot functions.) Caches exploit this by keeping recently used blocks.
• Spatial locality: a byte referenced now means its neighbors are likely referenced soon. (Array walks, instruction streams.) Caches exploit this by fetching a whole block (line) at once, not a single word.

Add one hardware fact — for a fixed technology and power budget, smaller memories can be made faster — and the hierarchy falls out naturally: keep the hot working set in a small fast store, back it with progressively larger, slower, cheaper stores.

The inclusion property

In most (not all) designs, the data in a lower level is a superset of the next level up. This inclusion property is typically maintained by main memory for caches, and by secondary storage for virtual memory. It simplifies coherence and lookup — but note the modern exception you'll meet in the case study: the Core i9's last-level cache is non-inclusive, so L2 and L3 hold different blocks and the effective capacity is their sum.

The processor–memory gap

The reason this chapter exists: processor demand for memory (requests/second) grew far faster than DRAM latency improved. DRAM latency improved only ~1.07×/year historically and has slowed since ~2010, while cores multiplied and each wants data faster. Bandwidth has scaled far better than latency — which is why so many techniques in this chapter are really about hiding or tolerating latency (prefetching, nonblocking caches, multiple banks) rather than eliminating it.

AMAT & Cache Performance

Average Memory Access Time is the single most important formula in the chapter. Every optimization that follows is an attack on one of its three terms.

Three levers, and naming which one you're pulling is the heart of cache design:

It composes recursively

Real machines have multiple cache levels, so the "miss penalty" of one level is itself an AMAT of the level below. Unrolled for three levels with a DRAM backstop:

Try it — feel the sensitivity

The calculator below computes AMAT and effective CPI live. The lesson interviewers want you to internalize: because L1's miss rate multiplies everything beneath it, a tiny change in L1 ripples massively into CPI. Drag L1's miss rate and watch the CPI number move far more than an equal change to L3.

Canonical worked examples

The calculator builds intuition; these fixed examples are the arithmetic you should be able to reproduce on a whiteboard. Numbers follow the chapter's formulas (drill values derived).

Cache Organization & the Three C's

A cache holds fixed-size blocks (lines). The two design questions are: where can a block go, and when it's not there, why did it miss? The second question — the three C's — is where interviews live.

Address decomposition & mapping

Given a block size and a number of sets, every address splits into three fields. This split is the cache's wiring — there's no arithmetic beyond shifting and masking:

• Block offset = log₂(block size) low bits — which byte within the block.
• Set index = log₂(number of sets) middle bits — which set to search.
• Tag = the remaining high bits — stored in the cache to confirm identity on a hit.

Associativity is just how many blocks live in one set. Direct-mapped = 1 way (one home per block, cheap but conflict-prone). Fully associative = 1 set (a block goes anywhere, no conflicts but expensive parallel tag search). n-way set associative is the practical middle.

Write policies

Reads are easy; writes force choices. Two orthogonal decisions:

The case-study machines both use write-back, write-allocate caches — note that in the A53/i9 sections.

The Three C's — a taxonomy of why misses happen

Every miss is exactly one of:

• Compulsory (cold): the first-ever reference to a block. Unavoidable except by prefetching or larger blocks. Independent of cache size.
• Capacity: the working set is simply bigger than the cache, so blocks are evicted and later re-fetched. Fix: bigger cache, or better locality.
• Conflict (collision): too many hot blocks map to the same set and evict each other, even though the cache as a whole has room. Fix: more associativity, victim cache, better indexing. Fully associative caches have zero conflict misses by definition.

Drive it

Configure a cache, pick a policy, and step an address trace. Watch sets fill and evict, see the live tag·index·offset decode, and read the three-C's breakdown. Try the presets in order — Sequential shows cold then capacity misses; Conflict thrash manufactures conflict misses you can then erase by raising associativity.

Replacement Policies

When a set is full and a new block must enter, which resident block dies? Replacement only matters on a miss to a full set, but on associative caches the choice can swing the miss rate — which is why "better replacement policies" is one of the chapter's ten advanced optimizations.

Head-to-head

Same cache, same trace, four policies. Replacement ties when there's no reuse pressure; it separates when sets overflow with reuse. Try the Set thrash and Loop > capacity presets to make the policies disagree.

Belady's anomaly

Intuition says more capacity can only help. FIFO breaks that. On the classic reference string below, going from 3 to 4 frames increases the fault count — because FIFO isn't a stack algorithm and gives up the inclusion property that guarantees monotonic behavior. LRU, OPT, and LFU are stack algorithms and never show the anomaly.

Memory Technology & Optimizations

Caches are SRAM; main memory is DRAM; storage is Flash. Knowing the physics of each — and especially how DRAM extracts bandwidth from a fundamentally high-latency array — separates a memory-systems candidate from a generalist.

SRAM vs DRAM

How DRAM makes bandwidth from latency

A DRAM access is two phases: activate a row into the row buffer (the slow part — RAS), then read columns out of that buffer (fast — CAS). The architecture's whole game is amortizing the expensive row activation:

• Row buffer = an open row acts as a small cache; consecutive accesses to the same row are fast (row hits).
• Burst mode + SDRAM/DDR: one address yields a stream of words. DDR (double data rate) transfers on both clock edges. Generations (DDR3→DDR4→DDR5) raise transfer rates; the case study uses DDR5-4800.
• Banks, ranks, channels: independent banks let multiple row activations overlap; multiple channels multiply bus width. This is how you scale bandwidth without lowering latency — a modern i9 can sustain enough memory parallelism to feed many cores.

DDR generations: bandwidth soared, latency stalled

Peak DIMM bandwidth = transfers/s × 8 bytes. Notice the right-hand column: row-miss latency is essentially flat while bandwidth climbs an order of magnitude — the bandwidth-not-latency story in one table.

HBM — stacking for bandwidth

High Bandwidth Memory stacks DRAM dies with through-silicon vias, announced across AMD/Intel/NVIDIA from ~2017. It delivers far higher bandwidth (and lower access energy per bit) than a single DDR bus, at higher cost. The chapter discusses HBM as an additional cache level (an L4/LLC, 10×+ the on-chip LLC) and even as main memory; the i9's memory channels can attach HBM or standard DIMMs. HBM is the backbone of GPUs and accelerators — directly relevant for NVIDIA-style interviews.

Flash & the "in-between" trap

Flash (NAND) is nonvolatile, denser and cheaper than DRAM but slower, and it wears out — blocks tolerate a limited number of writes, so controllers do wear leveling. SSDs replace disks for secondary storage. The chapter also flags PCM (phase-change memory) as a cautionary tale: a technology that sat between DRAM and Flash but offered no decisive win in speed or price, and so failed to gain momentum — a pitfall we revisit in §2.7.

Dependability: ECC & Chipkill

At warehouse scale, "rare" memory errors become constant. A 10,000-server fleet sees DRAM faults continuously, so protection isn't optional — it's a design requirement, and the level of protection you choose is an architectural decision with real cost.

The ladder of protection

• Parity: 1 extra bit per word — detects a single-bit error, can't correct. Cheap but weak; a single-processor server with only parity has a worse unrecoverable error rate than a huge ECC fleet.
• SECDED ECC: single-error-correct, double-error-detect (Hamming-style codes). The standard for server DRAM. The chapter notes a ~17-server ECC system has roughly the failure rate of a 10,000-server Chipkill system — quantifying how much stronger Chipkill is.
• Chipkill: RAID-for-DRAM. Data and check bits are distributed across multiple chips so the system survives the complete failure of an entire DRAM chip. The chapter's figure: about one undetected/unrecoverable failure every ~2 months for a Chipkill-protected fleet — making Chipkill a requirement for large-scale systems.

Same hardware, three protection levels, four orders of magnitude difference in failure interval — the quantitative case for matching protection to fleet size.

The Ten Advanced Optimizations

The chapter classifies ten techniques by which metric they improve: hit time/power, bandwidth, miss penalty, miss rate, or miss-penalty/rate via parallelism. Complexity generally rises as you go down the list. Learn each as a triple: what problem, which AMAT term, what it costs.

Each optimization in depth

Expand any optimization for the full interview checklist: problem, technique, AMAT term, complexity, a concrete cited number, and the one-line takeaway. Cited figures follow the chapter's Section 2.3 discussion.

Nonblocking caches — worth a deeper look

With out-of-order execution, stalling the whole pipeline on one miss wastes enormous parallelism. A nonblocking (lockup-free) cache continues to satisfy hits under a miss, and a more aggressive one allows misses under misses (multiple outstanding). The bookkeeping lives in MSHRs (miss status handling registers), which track each in-flight miss so returning data is matched to the right request — and misses can return out of order, especially if L2 is itself nonblocking. This is the cache-side counterpart to memory-level parallelism in the CPU, and it's why effective miss penalty drops far below the raw DRAM latency on a well-designed core.

Virtual Memory & Protection

Virtual memory treats physical memory as a cache of secondary storage and gives every process its own address space. The TLB is a cache of translations; the page table is the backing store. Same hierarchy ideas, one level up.

The moving parts

• Pages are the blocks of virtual memory. A virtual address splits into a virtual page number (VPN) and a page offset.
• The page table maps VPN → physical frame number (PFN), with protection bits per entry. Only the OS may update it — the basis of memory protection.
• The TLB caches recent VPN→PFN translations so you don't walk the page table on every access. TLBs act as caches on the page table, just as caches act on memory.

Step through a translation

The widget runs a sequence of virtual addresses through TLB → page-table walk → physical address, at a readable teaching scale (16-bit VA, 256-byte pages ⇒ 8-bit VPN + 8-bit offset). The trace deliberately includes a TLB hit (repeat access to a page), a TLB miss that the page table resolves, and an address that page-faults. Press Next step to advance.

The VIPT trick — why L1 size is "capped"

Translation is on the critical path, so we'd love the cache to start before the TLB finishes. If the cache index + block offset fit entirely within the page offset bits, those bits are identical in virtual and physical addresses — so the cache can index using virtual bits while the TLB translates the VPN, then check the physical tag at the end. That's a virtually-indexed, physically-tagged (VIPT) cache. It's why L1 capacity is often limited to roughly page size × associativity: it keeps the index inside the page offset and avoids aliasing. Both case-study L1s are VIPT — and the A53 even handles the one-bit overlap case with hardware alias detection.

Side-Channel Attacks on the Memory System

Virtual memory enforces protection in the architecture — but the microarchitecture leaks. The same caches and timing tricks that make memory fast can be turned into a covert channel that reads across protection boundaries. This is now core architect knowledge, not a footnote.

How they work

Side-channel memory attacks perturb the memory system and observe the effect through timing — using high-resolution timers or hardware performance counters. The cache is the leak: whether an address is cached or not changes its access latency, and that latency difference encodes secret-dependent behavior. Canonical patterns include Prime+Probe and Flush+Reload, where an attacker arranges cache state, lets the victim run, and then times its own accesses to infer which lines the victim touched.

Mitigations and their cost

Mitigations reduce the probability of leakage but can't eliminate all side channels if any resource is shared: partitioning caches, constant-time code that avoids secret-dependent memory access patterns, restricting fine-grained timers, flushing/isolating predictors and TLBs across boundaries, and disabling or constraining speculation on sensitive paths. Each costs performance — the running theme is that security and performance trade against each other in the memory system.

ARM Cortex-A53 vs Intel Core i9-12900

Two shipping memory hierarchies at opposite ends of the design space: a low-power embedded IP core and a high-end big.LITTLE desktop part. The contrast is the lesson — same principles, opposite priorities.

What to take from the numbers

• Non-inclusive LLC (i9): because L3 mainly holds blocks ejected from L2, L2 and L3 store different blocks — total cached data ≈ L2 + L3, not just L3. A deliberate capacity win over strict inclusion.
• Hashed L3 banking (i9): 3 bits of a hash select one of 8 banks, so only that bank activates — saving power (optimization 4) and spreading conflicts.
• Penalty dominates rate (A53): the chapter measures L1 miss rates ~7× the L2 rate, but the L2 penalty is ~9.5× larger — so L2 misses slightly dominate the memory-stressing benchmarks. A concrete reminder that miss rate alone never tells the story; you must weight by penalty.
• Local vs global, again: the A53's median L2 stand-alone miss rate is 15.1% but only 0.3% global — the §2.1 trap made real.

The full numbers, side by side

The detailed hierarchies from the chapter's figures. Read them as two answers to the same problem under different budgets.

ARM Cortex-A53 — PMD, energy-first

Features: critical-word-first, up to four memory banks, VIPT L1, write-back L1 D and L2 with write-allocate, approximate LRU.

Intel Core i9-12900 — desktop, throughput-first

On an L3 miss the block is filled into L2 and L1, not inserted into L3 — the LLC primarily holds blocks ejected from L2, so effective capacity ≈ L2 + L3.

Design poles

Reading the Measurements

A miss rate is not a cost. The single most common analysis error — and a favorite interview trap — is comparing miss rates across levels without weighting each by its penalty. This section is how to read cache data like an architect.

Weight every miss by its penalty

Misses at L1, L2, and L3 cost wildly different amounts. The honest figure of merit is the weighted contribution, not the raw rate:

MPKI (misses per thousand instructions) is the level-normalized rate; multiply by the level's penalty to get cycles. A 0.3% global L3 miss rate at a 200-cycle penalty can outweigh a 4% L1 rate at a 4-cycle penalty.

Diagnose by program behavior

Why cache-busters dominate averages

Miss behavior varies enormously by program — the A53's L1D miss rate spans 0.5% to 37.3%, a factor of 75. A single cache-buster like MCF sets the upper bound and drags the arithmetic mean with it. So a lone "miss rate" is nearly meaningless: report distributions, and be explicit that one outlier may be steering the average. This is also the chapter's first fallacy — predicting one program's cache behavior from another's.

Fallacies & Pitfalls

Memory hierarchy is the most quantitative subfield in architecture, yet it's riddled with traps. Each of these doubles as an interview "what's wrong with this reasoning?" prompt.

Fallacy — Predicting one program's cache behavior from another's

Miss rates vary enormously by workload. The chapter shows three SPEC programs whose misses-per-1000-instructions for the same large cache differ by huge factors (e.g., 9 vs 2 vs ~90). A cache tuned to benchmark A can be terrible for benchmark B. Lesson: never quote a single miss rate as "the" miss rate — characterize across representative workloads, and beware means dominated by one cache-buster (like MCF).

Pitfall — Not simulating enough instructions for accurate memory measurements

Three nested traps: (1) predicting a large cache's behavior from a short trace (the trace never fills the cache); (2) assuming locality is constant over a run — it isn't; and (3) locality varies by phase, so a snippet misrepresents the whole. Lesson: warm the cache and simulate long, phase-representative traces, or your numbers are fiction.

Pitfall — Not delivering high memory bandwidth in a cache-based system

Caches improve average latency but don't guarantee bandwidth to an application that must keep going to main memory (streaming, large sparse, ML). You can have great hit times and still starve a bandwidth-bound kernel. Lesson: design for bandwidth explicitly — channels, banks, HBM — when the workload blows past the cache.

Pitfall — A memory technology that "fits between" two others but wins at neither

The PCM cautionary tale: a technology slotted between DRAM and Flash that offered no decisive advantage in speed or price over either neighbor, and so failed to gain momentum. Lesson: a new tier must dominate an existing one on a axis that matters, or the ecosystem routes around it.

Interview Rapid-Fire

A consolidated drill set for senior memory-systems loops. Cover the answer, say yours aloud, then check. If you can do all of these crisply, you own Chapter 2.

The numbers & formulas to have cold

Conceptual drills

Source Notes & Corrections

Where the key numbers come from, and how conflicts were resolved. Rule used throughout: when the uploaded review deck and the textbook disagree, prefer the chapter, then note the correction.

Key figures and their source

Corrections applied

• i9 L1 size. An earlier draft of this guide listed the i9 L1 generically as "32 KiB, ~4-cycle." Corrected to the chapter/​deck figures: L1 I 32 KiB 8-way (4 cyc) and L1 D 48 KiB 6-way (5 cyc), dual-ported, 8 banks. (The 32 KiB 4-cycle figure is the i7 example used elsewhere in the chapter, not the i9-12900 case study.)
• Two bandwidth figures, two contexts. The chapter cites ~56 GiB/s in the §2.1 multicore-demand example and ~77 GB/s for the i9-12900 DDR5-4800 case study — not a conflict, two different numbers. The §2.1 bandwidth-wall example here uses 56 GiB/s; the i9 case study keeps 77 GB/s.
• Case-study processors. This guide uses the 7th-edition "Putting It All Together" pairing — ARM Cortex-A53 and Intel Core i9-12900 — not the 6th-edition Cortex-A8 / Core i7.
• Replacement naming. Both sources describe shipping "LRU" as an approximation (NRU / tree-PLRU / reuse predictors), not exact LRU; the guide says so throughout.
• Derived drill numbers. The single-level AMAT A/B drill and the CPI example use the chapter's formulas with illustrative inputs (so labeled), not measured device data.