Browse Prior Art Database

Cache Line Replacement Algorithm

IP.com Disclosure Number: IPCOM000062024D
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Pereira, LW: AUTHOR

Abstract

This invention relates to cache line replacement, and more particularly, to the election of multiple caches, replacement of a data line therein, and updating of its counterpart directory. Each directory entry includes control data. This consists of a validity/invalidity, recency of "hit" referencing, and line modification for each entry in the counterpart cache. The control data collectively governs the replacement ordering. Thus, upon a "miss" reference, if only one cache has lines therein labeled invalid, it is the replacement selection. If at least two caches have invalid lines, then the lowest ordered one of the two caches is chosen. A counter associated with each directory, incremented upon each "miss" and reset upon a "hit" measures recency of usage.

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

Page 1 of 1

Cache Line Replacement Algorithm

This invention relates to cache line replacement, and more particularly, to the election of multiple caches, replacement of a data line therein, and updating of its counterpart directory. Each directory entry includes control data. This consists of a validity/invalidity, recency of "hit" referencing, and line modification for each entry in the counterpart cache. The control data collectively governs the replacement ordering. Thus, upon a "miss" reference, if only one cache has lines therein labeled invalid, it is the replacement selection. If at least two caches have invalid lines, then the lowest ordered one of the two caches is chosen. A counter associated with each directory, incremented upon each "miss" and reset upon a "hit" measures recency of usage. The cache which has the highest "miss" number has its data line replaced in the event that all caches have only valid lines. It has been observed that least-recently-used (LRU) cache management methods require directory-to-directory communications which slow down cache speed. The selecting step in the above method permits address comparisons and controls to be executed on the same chip, thereby reducing the number of chips and chip crossings heretofore required in implementing function.

1