The problem › The wall needs a workaround
A small, fast memory that remembers
Chapter 0.4 left you in a bind: the CPU wants an answer every fraction of a nanosecond, and DRAM takes ~90 ns to produce one. Chapter 0.2 told you why you can't just build faster DRAM: fast memory (SRAM) can't be big, big memory (DRAM) can't be fast. The escape hatch is not to choose. Build both: keep the big slow array, and put a small, fast storage device that acts as a staging area for the data objects stored in a larger, slower device next to the core. That is the textbook definition of a cache, and the process of using one is caching.
The whole memory system is organized this way, level serving level: registers cache words from L1, L1 caches lines from L2, L2 from L3, L3 from DRAM, DRAM caches pages from disk: a pyramid where each level is smaller, faster, and costlier per byte than the one below it. The prices CS:APP quotes for its reference machine: registers 0 cycles, L1 ~4 cycles, L2 ~10, L3 ~50, main memory ~200.
The bet a cache makes is statistical: programs reuse what they just touched, and touch what sits next to it (chapter 0.6 names these habits and prices them). When the bet pays off (a hit), the answer comes from level k; when it doesn't (a miss), the block is fetched from level k+1, possibly evicting a resident block (the victim), and only then served. Your Intel Core i9-12900K carries three levels of this bet: a 48 KB L1 (~1 ns), a 1.25 MB L2 (~3 ns), and a 30 MB L3 (~11 ns) shared by all cores: the trade-off triangle from 0.2 stacked three deep.
SourcesCS:APP 3e §6.3 · pp. 645–650
The mechanism › The atom of memory traffic
You never fetch a byte. You fetch a line.
Data always moves between levels in fixed-size blocks, the transfer unit. The cache slot that holds a block, plus its bookkeeping bits, is a line. (Practitioners say "line" for both, and so will we.) On essentially every CPU you will touch, the L1/L2/L3 block is 64 bytes, aligned: ask for one byte and the cache fetches the entire 64-byte aligned chunk containing it. Bigger blocks would exploit more spatial locality but raise the miss penalty and starve temporal locality of slots; 64 bytes is the compromise modern designs settled on.
This is a gamble on adjacency, and it cuts both ways. Read a 4-byte intand its 15 neighbors ride along free: touch them next and they're already here. Never touch them and you paid to move 64 bytes and used 4, 94% of the traffic wasted. Ostrovsky's first cache experiment makes this brutal: a loop touching every element of a 64 MB array and a loop touching every 16th element run in essentially the same time (~80 ms vs ~78 ms): the second does 6% of the arithmetic but fetches the same lines, and lines are what you pay for. Hold that thought: in Topic 2 it returns with a different name (coalescing, chapter 2.4).
Predict first
Address 0x1000 and address 0x103F are 63 bytes apart. Address 0x103F and 0x1040 are 1 byte apart. Which pair lands in the same cache line?
The mechanism › (S, E, B, m)
Four numbers describe every cache ever built
CS:APP's §6.4 model, the one our simulator will implement literally, describes any cache with four parameters. The cache is an array of S = 2s sets. Each set holds E lines. Each line holds a block of B = 2b bytes, plus a valid bit and a tag. Addresses are mbits. Total capacity: C = S × E × B (tags and valid bits don't count).
Where does a line go? The hardware slices the address into three fields, right to left: the low b bits are the block offset (which byte within the block), the next s bits are the set index (which set the line must live in), and the remaining t = m − (s + b) bits are the tag: the line's identity, checked against the stored tag to confirm a hit. The book's phrase is exact: the cache finds your word "similar to a hash table with an extremely simple hash function." It's the a[17] arithmetic from chapter 0.1, done in binary, by wires.
E is the interesting dial. E = 1 is a direct-mapped cache: each line has exactly one legal slot, and a lookup is three steps, namely set selection, line matching, and word extraction. Simple and fast, but fragile: two hot blocks that share a set index evict each other forever even while the rest of the cache sits empty. CS:APP builds a dot-product where every x[i] and y[i] map to the same set; the arrays take turns evicting each other on every single access (thrashing), a slowdown of 2–3× from pure bad luck of placement. The fix in that example is comedy: pad one array by 16 bytes so the sets no longer collide.
A set associativecache blunts this by making each set hold E lines (1 < E < C/B): a block still maps to exactly one set, but may sit in any of that set's E ways, so E hot blocks per set coexist peacefully. Your L1 is (S, E, B) = (64, 12, 64): C = 64 × 12 × 64 = 48 KB, twelve ways deep. At the far end, E = C/B is a fully associativecache: one set, any block anywhere. It is too expensive to search at size, so it's reserved for small, critical caches like the TLB you'll meet in chapter 0.8. When a full set takes a new line, a replacement policy picks the victim: random is legal; least recently used (LRU)-style policies spend hardware to approximate the locality bet.
The taxonomy of failure, which you'll use for the rest of this course: a cold miss (the cache is empty; transient, gone once warmed up), a conflict miss (room exists, but placement rules force hot blocks into the same set), and a capacity miss (the working set of the current program phase is simply bigger than the cache).
SourcesCS:APP 3e §6.4.1–6.4.4 · pp. 650–664COD RISC-V §5.4, Fig. 5.14–5.15 · pp. 417–418
The number › Your turn
Decompose an address, then price the average access
Compute the number › where does 0x12345678 live in L1?
| B = 64 → b = 6 offset bits | S = 64 → s = 6 set bits |
| low 12 bits of 0x12345678 | 0x678 = 0b011001_111000 |
| offset (low 6) | 0b111000 = byte 56 |
| set index (next 6) | 0b011001 = set 25 |
| tag (bits above) | 0x12345 |
| lookup | set 25: compare 12 tags, valid bits on |
| Result | line tagged 0x12345 → set 25, byte 56 |
Now price the machinery with COD's formula: AMAT = time for a hit + miss rate × miss penalty. Take the single-level model CS:APP uses to teach (one L1 backed by memory): at a 95% hit rate, AMAT ≈ 1 ns + 0.05 × 90 ns ≈ 5.5 ns, a 90 ns memory masquerading as a ~5 ns one. Every percentage point of miss rate adds ~0.9 ns. The miss rate, not the hit time, is the lever. And miss rate, CS:APP shows later, predicts real program performance better than the raw number of memory accesses does.
interactive · coming soon
CacheSim: step-through address trace
Planned interactive: feed an address trace through a live tag/set/offset decomposition, watch lines land in sets, hits glow, misses fetch, and LRU evict, validated against CS:APP §6.4's practice problems.
The full story › writes, real hierarchies, and what our model simplifies away
Writes complicate the story, and the design space is a 2×2. On a write hit: write-through pushes the block to the next level immediately (simple, but bus traffic on every write); write-back marks the line dirty and writes it down only on eviction (less traffic, more bookkeeping). On a write miss: write-allocate fetches the block first (yes, a write triggers a read), while no-write-allocatebypasses the cache. The typical pairings: write-through with no-write-allocate, write-back with write-allocate. CS:APP's advice to programmers is to assume write-back, write-allocate: it's what modern hierarchies do at every level, and it's symmetric with how reads exploit locality. Our simulator will model exactly that.
Real hierarchies also split instruction from data at L1 (i-cache / d-cache, so a fetch and a load proceed in parallel and don't evict each other), and the textbook's own worked example, the Core i7, looks strikingly like your machine: L1 d-cache 32 KB, 8-way, ~4 cycles; L2 256 KB, 8-way, ~10 cycles; L3 8 MB, 16-way, 40–75 cycles; every block 64 bytes. Two more honest footnotes. First, caches index with the middlebits, not the high bits, precisely so that a sequential scan spreads across sets instead of piling into one. That choice is why chapter 0.6's row walk works at all.Second, associativity is finite: march through memory at a large power-of-two stride and you can force more than E hot lines into one set: Ostrovsky's example 5 shows a 16-way 4 MB L2 falling over at strides of 256 and 512 for exactly this reason.Victim buffers, hardware prefetchers, and multi-core coherence traffic we leave to CAQA (App. B): they shave the constants; they don't change the arithmetic you just did.
A cache is a small SRAM bet that the recent past predicts the near future, described by (S, E, B, m) and placed one 64-byte line at a time. Hits cost ~1 ns, misses cost ~90 ns, misses come in three kinds (cold, conflict, capacity), and the line, not the byte, is the unit you pay for. From here on, performance analysis is miss counting.