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.

Address split for a 32 KiB 8-way cacheA 32-bit address splits into a 20-bit tag, a 6-bit index that picks one of 64 sets, and a 6-bit offset that picks a byte in the 64-byte line.Tagbits 31 to 12Index11 to 6Offset5 to 0Compare with 8 tagsSet 47Byte 13
0x1234ABCD: tag 0x1234A is compared with the 8 tags in set 47; the offset picks byte 13 of the line.
FieldBitsFor 0x1234ABCD
Tag31 to 12 (20 bits)0x1234A
Index11 to 6 (6 bits)0x2F, set 47
Offset5 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.

AddressDirect-mapped (set)Result2-way LRU (set)Result
0x000Miss0Miss
0x400, evicts 0x00Miss0, second wayMiss
0x000, evicts 0x40Miss0Hit
0x400, evicts 0x00Miss0Hit
0x040, evicts 0x40Miss0 (same line as 0x00)Hit
0x800, evicts 0x00Miss0, evicts 0x40 (LRU)Miss
0x000, evicts 0x80Miss0Hit

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.