The InnovationQ application will be updated on Sunday, May 31st from 10am-noon ET. You may experience brief service interruptions during that time.
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

Publishing Venue


Related People

Cocke, J Pomerene, JH Puzak, TR Rechtschaffen, RN So, K Sparacio, FJ [+details]


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.