Cache Memory: How Mapping, Replacement and Writes Work
A cache splits every address into a tag, an index and an offset. The index picks a set, the offset picks the byte within a line, and the tag, compared against every line in that set, says whether the data is there. Associativity sets how many lines a set holds, the replacement policy picks which to evict, and the write policy decides when memory is updated.
What you'll learn
- Lines, sets and ways
- Splitting an address, worked for a 32 KiB cache
- A direct-mapped and a 2-way cache on the same trace
- LRU replacement
- Write-back vs write-through, and allocate on write
- Average memory access time
Step 1: lines, sets and ways
Memory moves into a cache in fixed-size lines (blocks), commonly 64 bytes, so neighboring bytes come along for free. Lines are grouped into sets. In a direct-mapped cache each set has one line, so each address has exactly one possible place; in an N-way set-associative cache each set has N lines (ways) and the data can go in any of them; a fully associative cache is one set holding every line.
Step 2: splitting an address
Take a 32 KiB, 8-way cache with 64-byte lines and 32-bit addresses. There are 32,768 / (64 × 8) = 64 sets. The offset needs log2(64) = 6 bits, the index log2(64) = 6 bits, and the tag is what is left: 32 − 6 − 6 = 20 bits.
| Field | Bits | For 0x1234ABCD |
|---|---|---|
| Tag | 31 to 12 (20 bits) | 0x1234A |
| Index | 11 to 6 (6 bits) | 0x2F, set 47 |
| Offset | 5 to 0 (6 bits) | 0x0D, byte 13 of the line |
On an access, the cache reads all 8 tags in set 47 at once and compares each with 0x1234A. A match on a valid line is a hit. No match is a miss: the line is fetched from the next level and placed in one of the 8 ways.
Step 3: why associativity helps
Take a tiny cache: 4 lines of 16 bytes. Direct-mapped, it has 4 sets; 2-way, it has 2 sets of 2. Run the byte addresses 0x00, 0x40, 0x00, 0x40, 0x04, 0x80, 0x00 through both.
| Address | Direct-mapped (set) | Result | 2-way LRU (set) | Result |
|---|---|---|---|---|
| 0x00 | 0 | Miss | 0 | Miss |
| 0x40 | 0, evicts 0x00 | Miss | 0, second way | Miss |
| 0x00 | 0, evicts 0x40 | Miss | 0 | Hit |
| 0x40 | 0, evicts 0x00 | Miss | 0 | Hit |
| 0x04 | 0, evicts 0x40 | Miss | 0 (same line as 0x00) | Hit |
| 0x80 | 0, evicts 0x00 | Miss | 0, evicts 0x40 (LRU) | Miss |
| 0x00 | 0, evicts 0x80 | Miss | 0 | Hit |
Direct-mapped, all three blocks map to set 0 and keep evicting each other: 7 misses in 7 accesses, though the cache has 3 empty lines. These are conflict misses. With 2 ways the same capacity gets 4 hits. More ways cost more tag comparators and a little more hit time, which is why L1 caches typically use 4 to 12 ways rather than full associativity.
Step 4: replacement
When a set is full, something must go. Least recently used (LRU) evicts the line untouched for longest, as in the trace above, on the bet that recent use predicts future use. True LRU needs ordering state per set, so large-associativity caches use approximations such as tree pseudo-LRU. Random replacement is simple and, at high associativity, not much worse.
Step 5: writes
Write-through updates the next level on every write: simple and always consistent, but it generates heavy write traffic, so it is paired with a write buffer. Write-back updates only the cache and marks the line dirty; memory is written when a dirty line is evicted, so repeated writes to one line cost one write-back. On a write miss, write-allocate fetches the line and then writes it (the usual partner of write-back), while no-write-allocate sends the write straight on (common with write-through).
Step 6: average memory access time
AMAT = hit time + miss rate × miss penalty. With a 1-cycle L1, a 5% miss rate and a 100-cycle trip to memory, AMAT = 1 + 0.05 × 100 = 6 cycles. Add an L2 with a 10-cycle hit time that misses on 20% of the accesses reaching it: the L1 miss penalty becomes 10 + 0.2 × 100 = 30 cycles, and AMAT = 1 + 0.05 × 30 = 2.5 cycles.
Common mistakes
- Computing sets as size / line size, forgetting to divide by the number of ways.
- Taking the index from the low address bits. The lowest bits are the offset.
- Blaming capacity for misses that associativity would remove. Those are conflict misses.
- Counting the L2 miss rate against all accesses. A local miss rate applies only to accesses that reach L2.
- Assuming write-back means data is lost on eviction. Dirty lines are written back first.
Check your understanding
- Q1. A 64 KiB, 4-way cache with 64-byte lines: how many sets, and how many index bits? Answer: 65,536 / 256 = 256 sets, 8 index bits.
- Q2. Why did the direct-mapped cache above miss every time? Answer: all three blocks mapped to set 0 and evicted each other (conflict misses).
- Q3. L1 hit 2 cycles, miss rate 10%, penalty 50 cycles: AMAT? Answer: 2 + 0.1 × 50 = 7 cycles.
Related
Sources
Hennessy and Patterson, Computer Architecture: A Quantitative Approach, 6th edition, Appendix B (cache basics, AMAT and the three kinds of miss); Patterson and Hennessy, Computer Organization and Design RISC-V Edition, chapter 5.
Last verified
The address split, the trace results (from a small cache simulator) and the AMAT figures are computed in the site's tests (lib/memoryNumbers.test.js) on 16 November 2026.