Data cache using dynamic frequency based replacement and boundary criteria

• US 5,043,885 A
• Filed: 08/08/1989
• Issued: 08/27/1991
• Est. Priority Date: 08/08/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Robinson, John T.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Ray, Gopal C.
• Application Number:
  US07/391,220
• Time in Patent Office: 749 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/, 365/49
• US Class Current: 711/133
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU

Abstract

A cache directory keeps track of which blocks are in the cache, the number of times each block in the cache has been referenced after aging at least a predetermined amount (reference count), and the age of each block since the last reference to that block, for use in determining which of the cache blocks is replaced when there is a cache miss. At least one preselected age boundary threshold is utilized to determine when to adjust the reference count for a given block on a cache hit and to select a cache block for replacement as a function of reference count value and block age.

Claims

1. A method, for use with a cache memory resource, that includes a plurality of cache blocks for storing data, and a cache directory, for keeping track of which of said blocks are in use, the number of times each block is referenced and block age, for determining which of said plurality of cache blocks is to be replaced with data to be stored in said memory on a cache miss, comprising, when implemented by a computer, the steps of:

(a) maintaining a reference count, for each cache block, in said cache directory;

(b) utilizing at least one preselected age boundary threshold to determine when to adjust a reference count for a given block on a cache hit; and

(c) selecting a cache block for replacement as a function of reference count value and block age.

2. A method, for use with a cache memory resource, that includes a plurality of cache blocks for storing data, and a cache directory, for keeping track of which of said blocks are in use, the number of times each block is referenced and block age, for determining which of said plurality of cache blocks is to be replaced with data to be stored in said memory on a cache miss, comprising, when implemented by a computer, the steps of:

(a) maintaining a reference count, for each cache block, in said cache directory;

initializing the reference count associated with a given block whenever the given block is used to store data from outside the cache on a cache miss;

(c) stacking block reference counts, with the block count associated with the most recently used block being placed at the top of the stack;

(d) maintaining an aging factor in said cache directory, for each block, for use in determining if a block has aged beyond a preselected age boundary threshold; and

(e) adjusting the reference count assoicated with a given block whenever a cache hit occurs on the given block and the block has aged beyond said preselected age boundary threshold.

3. A method as set forth in claim 2 further comprising, when implemented by a computer, the step of selecting, on a cache miss, the block to be replaced from the set of blocks whose reference counts are below a preselected reference count threshold value thereby allowing for the possibility of non least recently used block replacement choices.

4. A method as set forth in claim 2 further comprising, when implemented by a computer, the step of maintaining a chain of blocks whose reference counts are below said preselected reference count threshold value to facilitate rapid identification of possible block replacement choices.

5. A method as set forth in claim 2 further comprising, when implemented by a computer, the step of periodically reducing said reference count by a reduction factor in order to adapt the count to changes in the underlying frequency distribution.

6. A method as set forth in claim 2 further comprising, when implemented by a computer, the step of limiting said reference count to a predefined maximum count to avoid indefinite reference count increases.

7. A method, for use with a cache memory resource, that includes a plurality of cache blocks for storing data, and a cache directory, for keeping track of which of said blocks are in use, the number of times each block is referenced and block age, for determining which of said plurality of cache blocks is to be replaced with data to be stored in said memory on a cache miss, comprising, when implemented by a computer, the steps of:

(a) maintaining a reference count, for each cache block, in said cache directory;

(b) initializing the reference count associated with a given block whenever the given block is used to store data from outside the cache on a cache miss;

(c) stacking block reference counts, with the block count associated with the most recently used block being placed at the top of the stack;

(d) maintaining an aging factor in said cache directory, for each block, for use in determining if a block has aged beyond first and second preselected age boundary thresholds;

(e) adjusting the reference count associated with a given block whenever a cache hit occurs on the given block and the block has aged beyond said first preselected age boundary threshold, as indicated by the value of a block'"'"'s aging factor; and

(f) selecting, on a cache miss, the block to be replaced from the set of blocks aged beyond said second preselected age boundary threshold, as indicated by the value of a block'"'"'s aging factor, whose reference counts are below a preselected reference count threshold value, thereby facilitating non least recently used block replacement choices.

8. A method as set forth in claim 7 further comprising, when implemented by a computer, the steps of:

(a) maintaining multiple separate chains of blocks (a) maintaining multiple whose reference counts are below said preselected reference count threshold value and are of equal value in each chain; and

(b) scanning each of said chains of blocks to identify and replace a block that has aged beyond said second preselected age boundary threshold.

9. Apparatus for use with a cache memory resource, that includes a plurality of cache blocks for storing data, and a cache directory for keeping track of which of said blocks are in use, the number of times each block is referenced, block age, and at least one preselected age boundary threshold value, for determining which of said plurality of cache blocks is to be replaced with data to be stored in said memory on a cache miss, comprising:

(a) first means, coupled to said cache directory, for selectively adjusting the reference count maintained in said directory for each cache block;

(b) second means, coupled to said first means, for selectively enabling reference count adjustment, on a cache hit, as a function of cache block age and the value of at least one preselected age boundary threshold value; and

(c) third means, coupled to said cache directory, for selecting a cache block for replacement as a function of reference count value and block age.

10. Apparatus as set forth in claim 9 further comprising:

(a) means, coupled to said directory, for initializing the reference count associated with a given block whenever the given block is used to store data from outside the cache on a cache miss; and

means, coupled to said directory, for stacking block reference counts, with the block count associated with the most recently used block being placed at the top of the stack.

11. Apparatus as set forth in claim 10 further comprising means, coupled to said directory, for selecting, on a cache miss, the block to be replaced from the set of blocks whose reference counts are below a preselected reference count threshold value thereby allowing for the possibility of non least recently used block replacement choices.

12. Apparatus as set forth in claim 11 further comprising:

(a) means, coupled to said directory, for maintaining multiple separate chains of blocks whose reference counts are below said preselected reference count threshold value and are of equal value in each chain; and

(b) for scanning each of said chains of blocks to identify and replace a block that has aged beyond said preselected age boundary threshold.