Cache mapping answers one question: when a block of main memory is pulled into the cache, *where is it allowed to sit*? The cache is tiny next to RAM, so many memory blocks must share each slot. The mapping rule fixes the trade-off between how fast a lookup is and how often two useful blocks fight over the same spot.
The address is the key
Every memory address is split into three fields — tag, index, and offset. The hardware never searches the whole cache: it uses the index to jump straight to one set, compares the tag to confirm the right block, then uses the offset to pick the byte.
Splitting the address
1Offset — the low bits pick a byte inside the block. offset bits = log2(block size in bytes).
2Index — the next bits choose which set to look in. index bits = log2(number of sets).
3Tag — the remaining high bits identify *which* block is parked there. tag bits = address bits - index bits - offset bits.
32-bit address, 16-byte blocks, 64 sets (direct-mapped):
offset = log2(16) = 4 bits
index = log2(64) = 6 bits
tag = 32 - 6 - 4 = 22 bits
| tag (22) | index (6) | offset (4) |
Three mapping schemes
1Direct-mapped — each block has *exactly one* slot it may use (set = block number mod number-of-sets). One tag compare, fastest lookup, but two hot blocks that map to the same set keep evicting each other.
2Set-associative — each set holds a few slots (ways). A 2-way cache gives every block two places to live; the hardware compares both tags. Far fewer collisions, slightly slower.
3Fully associative — a block may sit in *any* slot. Collisions essentially vanish, but every tag must be checked on each access, so it is the most expensive.
Conflict misses and thrashing
A conflict miss happens when the cache has room overall but too many blocks competed for one set. In a direct-mapped cache, alternating between two addresses that share an index makes them evict each other on every access — thrashing — even though the rest of the cache sits empty.
Worked example — when associativity wins
Take a cache with 16-byte blocks and 4 sets, so set = (address / 16) mod 4. Address 0 is in block 0 -> set 0. Address 64 is in block 4 -> 4 mod 4 = set 0 as well. A program that reads 0, 64, 0, 64, ... maps both to set 0.
1Direct-mapped: set 0 has one slot. Each access evicts the other block, so *every* access is a miss — pure thrashing.
22-way set-associative: set 0 has two slots, so block 0 and block 4 both stay resident. After the first two misses, every later access is a hit.
OperationTimeSpace
Direct-mapped · fast; most conflict misses1 tag compare1 slot/set
n-way set-assoc · balanced — the common choicen tag comparesn slots/set
Fully associative · fewest conflicts; costliestall tags compared1 big set
Check yourself
A 16-byte-block, 4-set direct-mapped cache is hit by the repeating pattern 0, 64, 0, 64, ... What happens?
