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
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.