Partial Least-Recently-Used Cache Replacement Mechanism
Original Publication Date: 1988-Aug-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby a partial least-recently-used (LRU) algorithm is implemented by utilizing a hybrid approach to implement the LRU replacement algorithm in the congruence classes of a cache. The concept improves the efficiency, which is critical for caches with large set associativities. In a cache-based computer system, the use of a Partitioned LRU can be quite effective for replacement in cache congruence classes. However, as set associativities increase, typically from a size of 16 to 32, the number of bits that is required to implement the status of partitioned LRU grows very fast. For example, the figure is a binary tree of bits which represents the replacement status of a set of 16. In the tree, the leaves represent the lines in a congruence classes.