A class of replacement policies for medium and high-associativity structures

The content of set associative and fully associative structures (such as cache memories, TLBs and main memories) is controlled by a replacement algorithm. Replacing the elements that have not been accessed for a long period yields high performance. This property has been used in the LRU policy, it is also used in this paper, in order to define a new class of replacement policies that provide two improvements over LRU : 1) they exhibit higher performance, 2) they have a lower complexity of implementation : when the associativity increases, their complexity remains unchanged while it increases very rapidly for LRU. Trace-driven simulations show that, in 4-way caches, the performance improvement of one of the proposed policies over LRU is similar to the improvement of LRU over random and FIFO (i.e. about 10 %). For higher associativities, the proposed policies yield much higher performance in a particular range of cache sizes. In fully associative TLBs, the performance improvement is smaller but they yield much simpler implementations.