The memory hierarchy
Why caches exist
A modern core can start several instructions every nanosecond, but a trip to DRAM takes around 80 to 100 ns. Memory that is both large and fast does not exist: fast SRAM needs six transistors per bit and must sit close to the core, while dense DRAM is slow to access and lives off-chip. The answer is a hierarchy: a few small, fast levels near the processor that hold copies of the data in use, backed by larger, slower, cheaper levels.
Maurice Wilkes proposed the idea in 1965 as a "slave memory." The goal is a memory that runs almost as fast as the top level while holding as much as the bottom level, at close to the bottom level's cost per byte.
| Level | Typical size | Typical latency | Built from | Managed by |
|---|---|---|---|---|
| Registers | 32 × 64 bits | < 1 cycle | Flip-flops | Compiler |
| L1 cache | 32–128 KB | 4–5 cycles | SRAM | Hardware |
| L2 cache | 0.5–2 MB | 12–16 cycles | SRAM | Hardware |
| L3 cache | 8–128 MB | 40–70 cycles | SRAM | Hardware |
| Main memory | 8 GB–2 TB | 300+ cycles | DRAM | Operating system |
| Storage | TBs | ≈ 100,000 cycles | Flash | Operating system |
Representative values for a desktop or server processor near 4 GHz; exact figures vary by product.
Locality
Caches work because programs do not touch memory at random. Denning called this the principle of locality:
- Temporal locality: data used recently is likely to be used again soon.
- Spatial locality: data near something just used is likely to be used soon.
long sum = 0;
for (int i = 0; i < n; i++)
sum += a[i];
The loop's instructions and the variables sum, i and n are reused on every iteration (temporal locality). The elements a[i] are read in address order, so fetching a whole 64-byte block brings in the next seven long values at once (spatial locality).
Where caches sit
Each core typically has separate L1 instruction and data caches, so an instruction fetch and a load can proceed in the same cycle. A larger, unified L2 is usually private to each core. The last-level cache, often L3, is shared by all cores on the chip and split into slices connected by an on-chip network. Caches are managed entirely by hardware and are invisible to the instruction set: a program sees only faster or slower memory.
Organization and mapping
Blocks, sets and ways
Caches move data in fixed-size blocks (also called lines), almost always 64 bytes in current processors. The cache is divided into sets, and each set holds a fixed number of blocks called ways. A given memory block can live only in one set, but in any way of that set.
The hardware finds a block by splitting its address into three fields. The offset selects the byte within the block. The index selects the set. The tag is the rest of the address; it is stored alongside the block and compared on every lookup to confirm that the block really is the one requested. Each entry also has a valid bit, and write-back caches add a dirty bit.
Anatomy of a lookup
A 2-way set-associative cache with four sets, looking up an address that maps to set 2:
- Index. The index bits select one set; both ways of that set are read at once.
- Compare. Each way's stored tag is compared with the address tag, in parallel, one comparator per way.
- Decide. A way hits if its tag matches and its valid bit is set. If neither way hits, the access is a miss.
- Select. On a hit, a multiplexer passes the matching way's block, and the offset picks the requested bytes from it. On a miss, the block is fetched from the next level and placed in one of the set's ways, evicting the block already there.
Mapping techniques
| Direct-mapped | n-way set associative | Fully associative | |
|---|---|---|---|
| Where a block can go | Exactly one place | Any of n ways in one set | Anywhere |
| Tag comparators | 1 | n | One per block |
| Index bits | log₂(blocks) | log₂(blocks / n) | None |
| Hit time | Fastest; data can be used before the tag check finishes | Slightly longer: compare, then select a way | Slowest, and power-hungry for large sizes |
| Conflict misses | Most | Fewer as n grows | None |
| Replacement choice | None needed | Pick a victim among n ways | Pick among all blocks |
| Typical use | Some embedded caches; large off-chip caches | L1 (8–12 ways), L2 and L3 (8–16 ways) | TLBs, small victim caches |
Direct-mapped and fully associative caches are just the two ends of set associativity: 1 way, or as many ways as blocks. Hill's analysis showed that direct-mapped caches can win on overall speed when their faster hit time outweighs their extra misses, which is why the choice depends on the level. Seznec's skewed-associative caches hash each way's index differently, getting fewer conflict misses from the same number of ways.
Address calculator
Try doubling the ways at a fixed size: the index loses a bit and the tag gains one. Fully associative caches have no index at all.
Writes
| Situation | Options | Trade-off |
|---|---|---|
| Write hit | Write-through: update the cache and the next level. Write-back: update only the cache and set the dirty bit; write the block down when it is evicted | Write-through is simple and keeps levels consistent but sends every store down; write-back saves bandwidth and power and is the norm for L2 and L3 |
| Write miss | Write-allocate: fetch the block, then write it. No-write-allocate: send the write to the next level only | Write-allocate pairs naturally with write-back; no-write-allocate with write-through |
| Write buffer | Queue outgoing writes so the processor does not wait for them | Hides write latency; later loads must check the buffer for newer data |
Measuring cache performance
Performance metrics
| Metric | Definition | Notes |
|---|---|---|
| Hit rate | Hits / accesses | Often above 95% for L1 data caches |
| Miss rate | Misses / accesses = 1 − hit rate | Easy to measure, but ignores how long each access takes |
| Hit time | Time to access the cache on a hit | Set by size, associativity and wire lengths |
| Miss penalty | Extra time to fetch a block from the next level | Includes the next level's own hits and misses |
| AMAT | Hit time + miss rate × miss penalty | Average memory access time: the metric that combines all three |
| MPKI | Misses per 1,000 instructions | Compares workloads with different numbers of memory accesses per instruction |
A cache with a 1-cycle hit time, a 5% miss rate and a 100-cycle miss penalty has an AMAT of 1 + 0.05 × 100 = 6 cycles. Halving the miss rate to 2.5% brings it to 3.5 cycles. Doubling the hit time to 2 cycles to get that lower miss rate would still win (4.5 cycles), but only because the miss penalty is large. Neither metric alone settles the question; AMAT does.
Caches and CPU time
Suppose a processor has a CPI of 2 with a perfect cache. Every instruction is fetched (1 instruction access), and 36% of instructions are loads or stores. The instruction cache misses on 2% of fetches, the data cache misses on 4% of accesses, and each miss costs 100 cycles:
Instruction-miss stalls = 1 × 0.02 × 100 = 2.0 cycles. Data-miss stalls = 0.36 × 0.04 × 100 = 1.44 cycles. CPI = 2 + 2.0 + 1.44 = 5.44, and a machine with a perfect cache would be 5.44 / 2 = 2.72× faster.
Making the core faster without fixing memory makes this worse. If CPIperfect cache drops to 1, the stalls stay at 3.44 cycles, so memory now accounts for 3.44 / 4.44 = 77% of execution time.
Why caches miss
Hill and Smith's "three Cs" model sorts misses by cause, which points to the fix:
| Miss type | Definition | Reduced by |
|---|---|---|
| Compulsory | First access to a block. It would miss even in an infinite cache | Larger blocks, prefetching |
| Capacity | Would also miss in a fully associative cache of the same size: the working set does not fit | A larger cache; better locality in the code |
| Conflict | Would hit in a fully associative cache of the same size; too many blocks compete for one set | More ways; changing data layout or loop order |
Multiprocessors add a fourth C, coherence misses, when another core's write invalidates a cached copy.
Cache simulator
Pick an access pattern and a cache configuration, or paste your own addresses. Each square is one access, in order. The simulator uses LRU replacement and classifies each miss by comparing against a fully associative cache of the same size.
Things to try. "Two arrays 1 KB apart" misses on every access in a 1 KB direct-mapped cache, because both arrays map to the same sets; two ways remove every conflict miss. "Array sweep, twice" shows spatial locality: with 16-byte blocks and 4-byte elements, three of every four first-pass accesses hit, and the whole second pass hits. Change the block size to see the hit rate move. "Matrix, column order" stays at 0% hits even at 8 ways, because its 128-byte row stride lands on only a few sets, yet the same data in row order hits half the time.
Size, block and ways
| Increase | Helps | Hurts |
|---|---|---|
| Cache size | Capacity misses | Hit time, area, power, cost |
| Block size | Compulsory misses, through spatial locality | Miss penalty (more bytes to move). With too few blocks, conflict and capacity misses rise, so the miss rate curve is U-shaped |
| Associativity | Conflict misses | Hit time and energy (more tags compared); diminishing returns beyond about 8 ways |
Przybylski, Horowitz and Hennessy showed that these choices must be made together, judged by total execution time rather than miss rate alone, because a change that lowers the miss rate can still slow the machine through a longer hit time or cycle time.
Resources
Interactive tools and references
Peer-reviewed reading
- Wilkes, M. V. (1965). Slave memories and dynamic storage allocation. IEEE Transactions on Electronic Computers, EC-14(2), 270–271.The two-page origin of the cache.doi.org/10.1109/PGEC.1965.264263
- Denning, P. J. (1968). The working set model for program behavior. Communications of the ACM, 11(5), 323–333.Locality made precise.doi.org/10.1145/363095.363141
- Denning, P. J. (2005). The locality principle. Communications of the ACM, 48(7), 19–24.A short history of the idea behind every cache.doi.org/10.1145/1070838.1070856
- Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970). Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 78–117.Stack distance: simulating every cache size in one pass.doi.org/10.1147/sj.92.0078
- Smith, A. J. (1982). Cache memories. ACM Computing Surveys, 14(3), 473–530.The classic survey of cache design choices.doi.org/10.1145/356887.356892
- Hill, M. D. (1988). A case for direct-mapped caches. IEEE Computer, 21(12), 25–40.When faster hits beat fewer misses.doi.org/10.1109/2.16187
- Hill, M. D., & Smith, A. J. (1989). Evaluating associativity in CPU caches. IEEE Transactions on Computers, 38(12), 1612–1630.The three-Cs miss model used in the simulator.doi.org/10.1109/12.40842
- Przybylski, S., Horowitz, M., & Hennessy, J. (1988). Performance tradeoffs in cache design. Proc. ISCA, 290–298.Size, block size and associativity judged by execution time.doi.org/10.1109/ISCA.1988.5239
- Agarwal, A., Horowitz, M., & Hennessy, J. (1989). An analytical cache model. ACM Transactions on Computer Systems, 7(2), 184–215.Predicting miss rates from program behavior without full simulation.doi.org/10.1145/63404.63407
- Seznec, A. (1993). A case for two-way skewed-associative caches. Proc. ISCA, 169–178.Fewer conflicts from the same number of ways.doi.org/10.1145/165123.165152
- Lam, M. D., Rothberg, E. E., & Wolf, M. E. (1991). The cache performance and optimizations of blocked algorithms. Proc. ASPLOS IV, 63–74.How data layout and access order create conflict misses.doi.org/10.1145/106972.106981
- Wulf, W. A., & McKee, S. A. (1995). Hitting the memory wall: Implications of the obvious. ACM SIGARCH Computer Architecture News, 23(1), 20–24.Why the gap between processor and memory speed keeps growing.doi.org/10.1145/216585.216588