Chapter 4: Caches and Virtual Memory¶
A processor core can retire several instructions per cycle, but a trip to DRAM costs hundreds of cycles. The entire memory hierarchy exists to hide that gap. This chapter takes the microarchitect's view of a single core's memory system: how a cache finds a block and where it may put one, why caches miss and what cures each kind of miss, how to judge a design with one formula (average memory access time), what happens on stores, which helpers keep an out-of-order core fed, and how virtual memory and the TLB fit in front of the cache. The next chapter takes up the problem that arises when many cores each have a cache: coherence and consistency.
You should already know the memory wall of Chapter 1; Chapter 3 helps for the sections on non-blocking caches.
4.1 Why caches work¶
A student writing an essay keeps the three books in use open on the desk, a dozen on the shelf behind, the city library across town, and the national warehouse for anything else. Nearly every look-up hits the desk.
A cache is a small, fast memory that keeps copies of recently used data close to the processor. If the data is there, it is a cache hit; if not, a cache miss, and the request goes one level down. Caches are invisible to programs: they never change an answer, only how long it takes.
Fast memory is small and costly, and big memory is slow and cheap, so memories are stacked: the top is fast, the bottom is big.
| Level | Typical size | Typical access time |
|---|---|---|
| Registers | about 100 B | under 1 cycle |
| L1 cache | 32 to 64 KB | about 4 cycles |
| L2 cache | about 1 MB | about 12 cycles |
| L3 cache | 8 to 64 MB | about 40 cycles |
| DRAM | gigabytes | about 200 or more cycles |
| SSD | terabytes | about 100 000 cycles |
It works because real programs show locality.
- Temporal locality: something used now will probably be used again soon (a loop counter, the top of the stack, a popular variable). So keep recently used data.
- Spatial locality: if address \(A\) is used, addresses near \(A\) probably will be too (walking through an array, running instructions in sequence). So fetch a whole neighbourhood at once.
That neighbourhood is a cache line or block, the unit a cache moves and stores. Today it is typically 64 bytes.
4.2 How a cache finds things¶
Every address is cut into three pieces that tell the cache where to look and what to check.
- The offset picks the byte within a block. A 64-byte block needs 6 offset bits.
- The index picks which set of the cache to look in.
- The tag is the rest of the address. It is stored with the block and compared, to tell which of the many possible blocks is actually there.
Where may a block live?¶
- Direct-mapped: each block has exactly one possible place. It is simple and fast, but two blocks wanting the same place keep evicting each other.
- Set-associative: each block may go in any of \(N\) places in its set (2-way, 4-way, 8-way, ...). It is a good compromise and the usual choice.
- Fully associative: a block may go anywhere. There are no collisions, but every tag must be checked on every access, so it is used only for tiny caches.
Car parking is the picture: an assigned bay (direct-mapped), any bay on your floor (set-associative), any bay in the building (fully associative). The number of sets is capacity divided by (block size × associativity). When a set is full, one block must be evicted; the usual rule is LRU, least recently used: evict the block that has been untouched the longest.
Example 4.1: simulating a tiny cache
A cache has 4 blocks of 4 bytes each. The byte addresses referenced are 0, 4, 16, 0, 20, 4, 32, 0. With 4-byte blocks, the block number of an address is the address divided by 4: 0, 1, 4, 0, 5, 1, 8, 0. The offset has 2 bits.
Direct-mapped (4 sets, so the index is the block number mod 4):
| Access | Address | Block | Set | Result | Why |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | miss | compulsory |
| 2 | 4 | 1 | 1 | miss | compulsory |
| 3 | 16 | 4 | 0 | miss | compulsory; evicts block 0 |
| 4 | 0 | 0 | 0 | miss | conflict: block 4 evicted it |
| 5 | 20 | 5 | 1 | miss | compulsory; evicts block 1 |
| 6 | 4 | 1 | 1 | miss | conflict: block 5 evicted it |
| 7 | 32 | 8 | 0 | miss | compulsory; evicts block 0 |
| 8 | 0 | 0 | 0 | miss | conflict |
Zero hits: 5 compulsory misses and 3 conflict misses (0 and 16 fight over set 0; 4 and 20 fight over set 1).
2-way set-associative (2 sets of 2 ways, LRU; the set is the block number mod 2). Set 0 sees blocks 0, 4, 0, 8, 0: miss, miss, hit, miss (it evicts block 4, the least recently used), hit. Set 1 sees blocks 1, 5, 1: miss, miss, hit. That is 3 hits (the second 0, the second 4, the last 0) and 5 compulsory misses.
Fully associative (one set of 4 ways, LRU). The five distinct blocks 0, 1, 4, 5, 8 each miss once, compulsory. When block 8 arrives the cache holds 0, 1, 4 and 5, and block 4 is the least recently used, so it is evicted. The result is again 3 hits and 5 misses, all compulsory.
A conflict miss is exactly a miss that a fully associative cache of the same size would have avoided: here, the three extra misses of the direct-mapped cache.
Spatial locality in action¶
Take an array of four 4-byte words at addresses 0, 4, 8, 12, read twice in a cache of 16 bytes. With 4-byte blocks (4 blocks) the first pass misses on every word and the second pass hits every time: 4 misses in 8 accesses. With 8-byte blocks (2 blocks) the first access to each block brings in its neighbour: access 0 misses, 4 hits, 8 misses, 12 hits, and the second pass hits entirely: 2 misses in 8 accesses. Spatial locality halves the misses.
4.3 Why misses happen¶
Every miss has one of three causes, and each has its own cure. (The classification is due to Mark Hill.)
| Kind | Cause | Cure |
|---|---|---|
| Compulsory (cold) | The first touch of a block: it was never in the cache | Bigger blocks; fetching ahead (prefetching) |
| Capacity | The program's working data simply does not fit | A bigger cache |
| Conflict | Too many busy blocks map to the same set, though the cache has room elsewhere | More associativity |
Multicore adds a fourth C, coherence, treated in Chapter 5: a block is invalidated because another core wrote it.
Two experiments make the difference concrete. In a direct-mapped cache of 4 blocks of 4 bytes, addresses 0 and 16 fall into the same set (blocks 0 and 4, both set 0), so alternating between them misses on every access. Switch to 2-way and, after the first two misses, every access hits. Now cycle through five blocks (addresses 0, 4, 8, 12, 16, repeatedly) in a four-block cache with LRU. Even a fully associative cache misses every time, because each block is evicted just before it is needed again; only a bigger cache helps. That is a capacity problem, not a conflict problem.
Every knob has a price.
| Turn up... | Compulsory | Capacity | Conflict | Price |
|---|---|---|---|---|
| Cache size | none | fewer | fewer | Slower hits, more area and power |
| Associativity | none | none | many fewer | Slower hits (more tags to compare) |
| Block size | fewer | can rise | can rise | Each miss fetches more bytes (higher miss penalty and bandwidth) |
Block size has a sweet spot: too small wastes spatial locality, too big drags in bytes nobody uses and evicts useful ones. Sixty-four bytes is the near-universal choice. Associativity has diminishing returns, summarised in a rule of thumb: a direct-mapped cache of size \(N\) misses about as often as a 2-way cache of size \(N/2\).
4.4 Average memory access time¶
One formula judges any cache design:
Every term is a design knob. Lowering the hit time favours small, simple, low-associativity L1 caches; lowering the miss rate favours big, associative caches; lowering the miss penalty is what the deeper levels are for. The terms trade against one another, so no one can be optimised alone.
Example 4.2: one level
An L1 hit takes 1 cycle, the miss rate is 4%, and going to DRAM costs 200 cycles. $\(\text{AMAT} = 1 + 0.04 \times 200 = 1 + 8 = 9 \text{ cycles}\)$ The 4% of accesses that miss cost eight times more than the 96% that hit. Shrinking the penalty is what further levels are for.
With several levels the miss penalty of one level is the AMAT of the next:
Example 4.3: three levels
L1: hit 1 cycle, miss rate 5%. L2: hit 12 cycles, miss rate 40%. L3: hit 40 cycles, miss rate 50%. DRAM: 200 cycles. Work from the inside out.
- L3 level: \(40 + 0.50 \times 200 = 140\)
- L2 level: \(12 + 0.40 \times 140 = 68\)
- L1 level: \(1 + 0.05 \times 68 = 4.4\) cycles
That is 4.4 cycles instead of 9. The miss rates here are local: the misses at that level divided by the accesses reaching that level. A global miss rate divides by all accesses made by the CPU. Mixing the two is a classic mistake.
How the levels are arranged¶
- Contents. L1 is almost always split into an instruction cache and a data cache, so that the fetch engine and the load/store unit never contend; L2 and L3 are unified, one pool shared by instructions and data.
- Placement. Each core usually has private L1 and L2 caches, for low latency; all cores share the last-level cache, which is the capacity and coherence backstop for the whole socket.
- Inclusion. An inclusive cache keeps a copy of everything in the level above (simpler bookkeeping: to know what any core caches, snoop only the last level), at the price of duplicated capacity. An exclusive cache keeps each block in one level only (more total capacity, at the price of more careful handling when blocks move between levels). A non-inclusive, non-exclusive (NINE) design makes no promise either way.
4.5 Writes, and other tricks¶
Stores need rules of their own.
- Write-through: every store updates the cache and the next level. It is simple and always up to date, but generates a lot of traffic, and needs a write buffer so that the core does not stall.
- Write-back: a store updates only the cache and marks the block dirty. It is written down only when evicted. There is far less traffic, and it is the norm for L1 data caches and below. It needs a dirty bit and a write-back path.
- Write-allocate: on a store miss, fetch the block first (the usual partner of write-back).
- No-write-allocate: on a store miss, write straight to the next level without caching (the usual partner of write-through; good for streaming stores).
Several helpers keep an out-of-order core fed.
- The write (store) buffer is a small FIFO that holds retired stores, so the core need not wait for them to reach memory. Loads must look inside it (store-to-load forwarding), and its draining behaviour is central to the memory-consistency model of Chapter 5.
- A victim cache is a tiny fully associative buffer for recently evicted blocks. It catches conflict misses in a low-associativity L1 cheaply, adding a bit of associativity for the hot sets.
- Prefetching brings blocks in before they are demanded, attacking compulsory misses. Hardware prefetchers (next-line, stride and stream) detect patterns such as "every 64 bytes" and run ahead; software prefetch hints (for example x86
PREFETCHT0or the RISC-V Zicbop instructions) are precise but need their distance tuned. Too eager a prefetcher pollutes the cache and wastes bandwidth. - Non-blocking (lock-up-free) caches keep serving hits while a miss is pending ("hit under miss") and track several outstanding misses ("miss under miss") with MSHRs, the miss status handling registers. Each MSHR records the pending block's address and which loads are waiting; when the fill returns, it wakes them. The number of MSHRs caps the memory-level parallelism, the essential partner of an out-of-order core's ability to have many loads in flight.
4.6 Virtual memory and the TLB¶
Every program believes it has the whole memory to itself. A translation step makes that true. With virtual memory, programs use virtual addresses and the hardware translates each one to a physical address in real memory. Translation works in chunks called pages, commonly 4 KiB. A page table in memory lists where each virtual page really lives. This gives isolation (programs cannot see each other), freedom of placement, and the ability to keep rarely used pages on disk. It is like flat numbers in two buildings: "Flat 1" exists in both, and the postal service knows which street each building is on.
A flat page table would be enormous, so architectures use a multi-level (radix) table: the virtual address is split into fields that index successive levels. RISC-V Sv39, for example, uses three 9-bit levels above a 12-bit page offset.
A full walk is one memory read per level, three extra reads for every access, which is far too slow to do each time. The TLB (translation lookaside buffer) is a small, fast, highly associative cache of recent translations (virtual page number to physical page number, plus permission bits). A TLB hit translates in about a cycle; a miss triggers a page-table walk, by a hardware walker or on some ISAs by software. TLBs are split for instructions and data, often have two levels, and are tagged with an address-space identifier (ASID) so that a context switch need not flush them.
The VIPT trick¶
If the L1 cache must be looked up after translation (physically indexed, physically tagged, PIPT), the TLB sits on the critical path and slows every access. If it is indexed by the virtual address (VIVT) there are aliasing problems. The compromise is VIPT: virtually indexed, physically tagged. Use the untranslated page-offset bits to index the cache set in parallel with the TLB look-up, then compare the physical tag once translation completes. The overlap is free, provided that
so that the index and offset bits come entirely from the page offset, which translation does not change. This constraint is one reason so many L1 caches are 32 KiB, 8-way, with 64-byte lines: \(32\ \text{KiB}/8 = 4\ \text{KiB}\), exactly one page, and the 6 index bits plus 6 offset bits of Figure 4.2 make exactly the 12-bit page offset.
4.7 Summary¶
- Caches exploit temporal and spatial locality; data moves in cache lines, typically 64 bytes.
- An address splits into tag, index and offset. Direct-mapped, set-associative and fully associative caches trade speed against collisions; LRU picks the victim.
- Misses are compulsory, capacity or conflict (and, with several cores, coherence). Size cuts capacity misses, associativity cuts conflict misses, bigger blocks cut compulsory misses up to a point.
- \(\text{AMAT} = \text{hit time} + \text{miss rate} \times \text{miss penalty}\), applied level by level with local miss rates.
- Write-back with write-allocate is the norm; write buffers, victim caches, prefetching and non-blocking caches with MSHRs keep an out-of-order core fed.
- Virtual memory translates pages through multi-level tables; the TLB caches translations; VIPT overlaps translation with the cache index.
4.8 Exercises¶
Exercise 4.1. An L1 cache has a hit time of 2 cycles, a miss rate of 10% and a miss penalty of 100 cycles. What is the AMAT?
Answer
\(2 + 0.10 \times 100 = 12\) cycles.
Exercise 4.2. Two blocks keep evicting each other in a direct-mapped cache that is mostly empty. Which kind of miss is this, and what fixes it?
Answer
Conflict misses. More associativity fixes them (2-way would do here).
Exercise 4.3. Take the addresses 0, 4, 16, 0, 20, 4, 32, 0 for a cache of 4 blocks of 4 bytes, but now with 8-byte blocks (the cache is then 2 blocks of 8 bytes: direct-mapped means 2 sets). Simulate the direct-mapped cache and count hits.
Answer
With 8-byte blocks, the block number is the address divided by 8: 0, 0, 2, 0, 2, 0, 4, 0. The index is the block number mod 2: 0, 0, 0, 0, 0, 0, 0, 0, so every access falls in set 0.
| Access | Address | Block | Result |
|---|---|---|---|
| 1 | 0 | 0 | miss |
| 2 | 4 | 0 | hit (same 8-byte block) |
| 3 | 16 | 2 | miss, evicts block 0 |
| 4 | 0 | 0 | miss, evicts block 2 |
| 5 | 20 | 2 | miss, evicts block 0 |
| 6 | 4 | 0 | miss, evicts block 2 |
| 7 | 32 | 4 | miss, evicts block 0 |
| 8 | 0 | 0 | miss |
One hit in eight accesses. The larger block gave one spatial-locality hit but the cache has only two sets, so conflicts dominate; compare the zero hits of Example 4.1.
Exercise 4.4. A two-level cache has: L1 hit 1 cycle, miss rate 8%; L2 hit 10 cycles, local miss rate 25%; memory 150 cycles. Find the AMAT with and without the L2.
Answer
With the L2: \(1 + 0.08 \times (10 + 0.25 \times 150) = 1 + 0.08 \times 47.5 = 4.8\) cycles. Without it: \(1 + 0.08 \times 150 = 13\) cycles.
Exercise 4.5. A cache is 32 KiB, 8-way set-associative, with 64-byte blocks, and addresses are 32 bits. (a) How many sets does it have? (b) Split the address 0x00012345 into tag, index and offset. (c) Is the cache usable as VIPT with 4 KiB pages?
Answer
(a) \(32\,768/(64 \times 8) = 64\) sets, so 6 index bits; the offset has 6 bits and the tag has \(32 - 12 = 20\) bits.
(b) The offset is the low 6 bits. \(0x345 = 837\) and \(837 \bmod 64 = 5\), so the offset is 5. The index is the next 6 bits: \(\lfloor 837/64 \rfloor = 13\), so the index is 13. The tag is the address shifted right by 12: \(0x00012345 \gg 12 = 0x12\).
(c) Sets × block size \(= 64 \times 64 = 4096\) bytes = 4 KiB, which equals the page size, so the index and offset bits come entirely from the page offset: yes, it can be VIPT.
Exercise 4.6. Why is a 16 KiB, 4-way cache with 64-byte blocks also VIPT-friendly with 4 KiB pages, but a 64 KiB, 4-way cache with 64-byte blocks is not?
Answer
The number of sets times the block size is the cache size divided by the associativity. For 16 KiB, 4-way this is \(16/4 = 4\) KiB, which fits in one page. For 64 KiB, 4-way it is \(64/4 = 16\) KiB, so 2 index bits would lie above the page offset and would be changed by translation: the cache cannot be indexed before the TLB answers without aliasing problems.
Exercise 4.7. A cache is direct-mapped with 4 blocks of 4 bytes. Addresses 0 and 16 are accessed alternately: 0, 16, 0, 16, 0, 16. How many hits? How many with a 2-way cache of the same size?
Answer
Direct-mapped: blocks 0 and 4 both map to set 0, so each access evicts the other: 0 hits in 6 accesses. 2-way: the two blocks sit in the two ways of the same set; after the first two compulsory misses all four remaining accesses hit: 4 hits in 6.
Exercise 4.8. With Sv39 paging and no TLB hit, how many memory reads does one load need in total, assuming the page-table reads and the data read all go to memory? Why does the TLB matter?
Answer
Three reads to walk the three table levels plus one read for the data itself: four. With a TLB hit the translation takes about a cycle and the load needs only the data access (and perhaps a cache hit), so the TLB removes the three extra reads from nearly every access.
Exercise 4.9. State one benefit and one cost of doubling the block size of a cache.
Answer
Benefit: fewer compulsory misses on code and data with spatial locality, since each miss brings in more neighbouring bytes. Cost: each miss fetches more bytes (a higher miss penalty and more bandwidth), fewer blocks fit so conflict and capacity misses can rise, and false sharing between cores becomes more likely.