An approximate or replacement algorithm performs nearly as well as the LRU algorithm but requires fewer bits and less complexity. It is employed in some Intel processor caches and is illustrated in Figure below. You can find more details on this algorithm - Pseudo-LRU.

Pseudo-LRU or PLRU is a family of cache algorithms which improve on the performance of the Least Recently Used (LRU) algorithm by replacing values using approximate measures of age rather than maintaining the exact age of every value in the cache.

PLRU usually refers to two cache replacement algorithms: tree-PLRU and bit-PLRU.

In the example above, a 4-way set associative cache that would require a minimum of 5 bits for true LRU (and 8 bits if using the counter method) would require only three bits for each set using approximate (or pseudo) LRU. Moreover, the algorithm for maintaining the approximate LRU bits is much simpler. The four ways are partitioned into two halves, each half consisting of two ways {0,1} and {2,3}. One bit is allocated to each half to indicate which of the two ways in that half was most recently accessed. A third bit is used to indicate which was the most recently used of the two halves.

a.) The AMD Opteron uses a 16-way set associative 1MB unified L2 cache with 64 byte lines and approximated LRU replacement. How many total LRU bits would be required for this cache?

b.) How many bits would a true LRU replacement policy using the counter implementation require for this cache?

c.) In the worst case, what would be the position (from least recently used to most recently used) of a line that would be evicted instead of the true least recently used line. Hint: consider the case where the approximate LRU bits for a line are {0,0,0}. When would the approximate LRU and the true LRU algorithms indicate different victims?

All four lines Yes: LD or L1 least recenty used