A Summary (Cont.)
How Is a Block Found? (Cont.)
The choice among direct-mapped, set-associative, or fully associative mapping depends on the cost of a miss versus the cost of implementing associativity, both in time and in extra hardware.
Virtual memory systems always use fully associative placement because of the factors:
- Full associativity is beneficial, since misses are very expensive.
- Full associativity allows software to use sophisticated replacement schemes that are designed to reduce the miss rate.
- The full map can be easily indexed with no extra hardware and no searching required.
Which Block Should Be Replaced on a Cache Miss?
There are the two primary strategies for replacement in set-associative or fully associative caches:
- Random:
Candidate blocks are randomly selected, possibly using some hardware assistance.
For example, MIPS supports random replacement for
| TLB | misses.
- Least recently used (LRU):
The block replaced is the one that has been unused for the longest time.
The following two observations are noticed:
- In practice, LRU is too costly to implement for memory hierarchies with more than a small degree of associativity, since tracking the usage information is costly.
Therefore, LRU is often approximated.
- In fact, random replacement, which is simple to build in hardware, can sometimes be better than the simple LRU approximations that can also be implemented in hardware.