Methods and apparatus for true least recently used (LRU) bit encoding for multi-way associative caches

摘要

Two techniques are provided for implementing a least recently used (LRU) replacement algorithm for multi-way associative caches. A first method uses a special encoding of the LRU list to allow write only update of the list. The LRU list need only be read when a miss occurs and a replacement is needed. In a second method, the LRU list is integrated into the tags for each "way" of the multi-way associative cache. Updating of the list is done by writing only the "way" of the cache that hits.