Day 49: Cache mechanics: mapping, replacement, write policy, AMAT
Cache mechanics and AMAT
A cache splits an address into tag, index, and block offset. The index picks a set; the tag confirms the right block is present; the offset selects the byte within the block. Direct-mapped caches give each block exactly one home (simple, fast, but conflicts thrash). Set-associative caches offer N homes per set (fewer conflicts, more compare hardware). Fully associative allows any slot (fewest misses, most expensive).
AMAT = hit_time + miss_rate * miss_penalty
Example: hit_time = 1 cycle, miss_rate = 5%, miss_penalty = 100 cycles
AMAT = 1 + 0.05 * 100 = 6 cycles
Levers: lower miss_rate (bigger/associative cache),
lower miss_penalty (add an L2),
lower hit_time (smaller/simpler cache) -- often in tension.On a write, policy matters: write-through updates cache and memory together (simple, more traffic); write-back updates only the cache and marks the block dirty, writing to memory on eviction (less traffic, more complex). Replacement (which block to evict on a miss) is typically LRU or an approximation. These knobs — associativity, block size, write and replacement policy — are the whole design space.
AMAT arithmetic is guaranteed interview fodder
Cache AMAT numericals and 'direct-mapped vs set-associative trade-offs' appear in essentially every architecture loop and government written exam. Practice a few by hand: change miss rate or penalty and predict AMAT. It's cheap points you should never drop.
Key terms
- Tag / index / offset
- The three parts of an address a cache uses to locate a block and byte.
- Associativity
- How many slots a block may occupy: direct-mapped (1), N-way, or fully associative.
- AMAT
- Average memory access time = hit_time + miss_rate × miss_penalty.
- Write-through / write-back
- Update memory on every write vs only on eviction of a dirty block.
- Replacement policy
- Which block to evict on a miss (LRU, pseudo-LRU, random).
Before moving on, you should be able to
A cache has hit time 2 cycles, miss rate 10%, and miss penalty 80 cycles. What is its AMAT?
