In a set-associative cache with E-way associativity, when there is a miss and all the blocks in the set are valid, we have to choose one out of the E blocks to replace. Which one do we choose? One idea is random replacement i.e. use a pseudo-random number generator to pick a block between 0 and E-1 and replace that one. Another is least-recently-used replacement or LRU. That is, choose the block that was used least recently on the theory that it will be least likely to be used in the future. This requires keeping track of the relative times of access of each block. That could be done by keeping a timestamp associated with each block that's updated when the block is accessed, or by keeping the position of each block, 0 through E-1, in the ordering of accesses, e.g. 0 is the most recently used, 1 is the next most recently used, and so forth, while E-1 is the least recently used.
Modern replacement algorithms are complicated, but you can assume they behave more-or-less like LRU.
LRU Cache Replacement Animation
Hit
Miss
Eviction
Cache Demonstration
This code demonstrates a blocking algorithm that makes good use of the cache.
A naïve version of the Sieve of Eratosthenes sieve.cc
A blocked version of the Sieve of Eratosthenes sieve2.cc
Hit
Miss
Eviction
