Browse Prior Art Database

One-Bit Cache Replacement Algorithm

IP.com Disclosure Number: IPCOM000043097D
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Cocke, J: AUTHOR [+6]

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

One-Bit Cache Replacement Algorithm

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. By replacing from the non-MRU half at random, the MRU lines and previous MRU lines are preserved. This bit per congruence class is flipped on each miss and also on in-cache hits to the non-MRU half of that congruence class.

1