Cache Line Replacement Algorithm
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
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.