In the Least Recently Used (LRU) Cache replacement policy, the cache block which has been unused for the longest time is replaced. In this way, LRU exploits temporal locality – a data location that is currently referenced will tend to be referenced again soon.

Procedure

Each block in an -way set associative cache will have its own LRU counter. This counter can take any value from to . At any given time, all LRU counter values are distinct within a set. The value corresponds to the LRU (Least Recently Used) block. The value corresponds to the MRU(Most Recently Used) block.

Block Type	Counter Value
Most Recently Used (MRU)
Least Recently Used (LRU)

During block replacement, the block that is replaced becomes the MRU block and thus its counter value becomes . Only those counter values greater than the counter value of the block that is accessed get decremented by . All other blocks remain unchanged.

Consider a set with blocks with the following counter values.

Cache Miss

In case of a cache miss, the Least Recently Used block needs to be replaced. This is indicated by the red block below.

The counter value of the block that has to be replaced is . So, all blocks with counter values greater than have to be decremented by . The block that gets replaced will have the counter value . All counter values have to be distinct.

Another cache miss will replace the following red block

After replacement, the counter values will be

Another cache miss will replace the following red block

After replacement, the counter values will be

Cache Hit

In the case of a cache hit, the block that is hit will become the Most Recently Used. This is indicated by the blue block below

The counter value of the block that is hit is . So, all blocks with counter values greater than (of which there are none) have to be decremented by . The block that is hit is updated with the counter value of . All counter values have to be distinct.

Another cache hit on the blue block.

The counter value of the block that is hit is . So, all blocks with counter values greater than have to be decremented by . The block that is hit is updated with the counter value of . All counter values have to be distinct.

Another cache hit on the blue block.

The counter value of the block that is hit is . So, all blocks with counter values greater than have to be decremented by . The block that is hit is updated with the counter value of . All counter values have to be distinct.

Cost and Energy Factor

A set of size will require bits to keep track of all the counter values. In the above case, bits to track counter values. Each set has its own list of counter values. Thus, a set associative cache with sets, will require counters each of size bits.

For each cache access, in the worst case, upto counters need to be changed.