One-Bit Cache Replacement Algorithm
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
Current cache directory size involves a significant number of bits to maintain the least recently used (LRU) status of cache lines in a congruence class. With the algorithm disclosed in this article, one bit is sufficient to achieve approximately the same hit ratio of a full LRU managed cache. The majority of all accesses to the cache are the most recently used (MRU) lines, and of the remainder, the most popular line is the previous MRU line. Since successive MRU hits do not impact replacement, the previous MRU line is the current MRU line at the time of the miss. To assure a high hit ratio, it is only essential that the current MRU line within each congruence class not be replaced. One bit per congruence class is used to identify the half of the lines which do not contain the current MRU line.