A Quantitative Reframing of Memory Hierarchy Optimisation — Epoche C1
Review: Computer Architecture: A Quantitative Approach (6th ed.) For decades, a pervasive misconception in computing has been that improving memory performance primarily entails scaling caches up: make the fast memory bigger and faster, and programs will run proportionally faster. While intuitively appealing, this view overlooks the interplay of factors that actually governs modern processor efficiency. Hennessy and Patterson's Computer Architecture: A Quantitative Approach (6th ed.) decisively overturns the simplistic view, and it does so in a characteristic way: every design question is reduced to a small set of measurable quantities, an equation relating them, and benchmark data that fixes the values. The authors demonstrate that real advances come from modelling access patterns and data locality — where a program's memory references actually fall — rather than from brute-force increases in capacity. Why a Hierarchy Exists at All The starting point, which the book establishes before any optimisation is discussed, is an economic impossibility: no single memory technology is simultaneously large, fast and cheap. The fast technology, static RAM (SRAM), stores each bit in a flip-flop-like circuit of six transistors that holds its value as long as power is applied; it can be read in under a nanosecond when placed on the processor die, but six transistors per bit makes it expensive in silicon area. The dense technology, dynamic RAM (DRAM), stores each bit as charge on a single capacitor gated by one transistor — six times fewer devices, hence far more bits per unit cost — but reading that charge, and doing so across a chip boundary, takes tens of nanoseconds: roughly a hundred processor clock cycles on a multi-gigahertz core. A hierarchy — a small SRAM cache close to the processor, backed by successively larger and slower tiers down to DRAM — squares this circle only because of a measured property of programs called locality. Temporal locality: a memory address referenced now is likely to be referenced again soon (loop counters, stack variables). Spatial locality: addresses near a referenced one are likely to be referenced soon (array traversals, sequential instruction fetch). Caches exploit both by keeping recently used data, and by fetching data in blocks of (typically) 64 adjacent bytes rather than single words. Locality is why a cache holding a few hundred kilobytes can satisfy well over 90 per cent of the references of a program whose data occupies gigabytes; it is an empirical regularity of real workloads, quantified in the book across the SPEC benchmark suites, not a law of nature — and programs that lack it (pointer-chasing over huge graphs, for example) defeat the hierarchy no matter how large the cache. The Governing Equation: Average Memory Access Time The book's central analytical tool is an expected value, of the kind familiar from a first course in probability: the average cost of an access is the cost when the cache holds the data, plus the probability that it does not, times the extra cost when it does not. Writing hit time for the time to service a reference found in the cache, miss rate for the fraction of references not found there, and miss penalty for the additional time to fetch the block from the tier below, $$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}.$$ The numbers make the argument. Take a representative single-level configuration: a 1-cycle hit time, a 2 per cent miss rate, and a 100-cycle penalty to reach DRAM. Then $\text{AMAT} = 1 + 0.02 \times 100 = 3$ cycles: the occasional miss triples the average cost of memory access, even though 98 per cent of references hit. Now consider the naive remedy of doubling cache capacity. Across a wide range of workloads, the measured miss rate falls only as roughly the inverse square root of capacity — a power law documented empirically by Hartstein and colleagues, who asked in the title of their paper whether the folk "$\sqrt{2}$ rule" holds and found it approximately does for typical workloads. Doubling capacity therefore takes the miss rate from 2 per cent to about $2/\sqrt{2} \approx 1.4$ per cent, and the AMAT from 3 to about 2.4 cycles — a 20 per cent improvement in exchange for doubling the silicon area and the leakage power of the cache. Worse, a larger array is physically bigger, so its word lines and bit lines — the wires that address and read the cells — are longer; wire delay grows with length, so the hit time itself creeps up. If doubling pushes the hit time from 1 cycle to 1.3, the AMAT becomes $1.3 + 0.014 \times 100 = 2.7$: most of the theoretical gain has evaporated. This arithmetic, not any single benchmark, is the book's case for diminishing returns. Real machines mitigate the tension with multiple cache levels, and the equation composes: the penalty of a first-level miss is itself the AMAT of the second level, so $\text{AMAT} = \text{HT}_{L1} + \text{MR}_{L1} \times \left( \text{HT}_{L2} + \text{MR}_{L2} \times \text{MP}_{L2} \right)$. The design freedom this exposes is exactly the book's point: the L1 cache can stay small so its hit time matches the processor cycle, while the L2 and L3 absorb capacity misses at latencies that only the (rarer) L1 misses ever see. The book also inherits a classification, due to Mark Hill, of why misses happen, and the taxonomy explains why capacity is a blunt instrument. Compulsory misses occur on first touch of a block — no cache size prevents them, only fetching ahead of use. Capacity misses occur because the working set exceeds the cache — these are the only kind that more capacity directly removes. Conflict misses occur because a block was evicted not for lack of space but because the cache's indexing scheme forced two addresses into the same slot: in a direct-mapped cache, each memory block may live in exactly one location; a set-associative cache relaxes this by letting a block live in any of $w$ ways within its set, trading a slower, w