Cache Block Replacement Policy
Random Replacement:
- Hardware randomly selects a cache item and throw it out
Least Recently Used:
- Hardware keeps track of the access history
- Replace the entry that has not been used for the longest time.
- For two way set associative cache one needs one bit for LRU replacement.
Example of a Simple “Pseudo” Least Recently Used Implementation:
- Assume 64 Fully Associative Entries
- Hardware replacement pointer points to one cache entry
- Whenever an access is made to the entry the pointer points to:
- Move the pointer to the next entry
- Otherwise: do not move the pointer