Patent US5043885A successfully refreshed from Google Patents.
US5043885A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data cache using dynamic frequency based replacement and boundary criteria
Assignee: International Business Machines Corp
•
Filing: 1989-08-08
•
Granted: 1991-08-27
•
Expires: 2009-08-08
Abstract
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.
Inventors
- 👤 John T. Robinson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 15:14
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F12/124; G06F12/122
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
135 words
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.
Claim 2
Independent Claim
135 words
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.
Claim 3
Independent Claim
200 words
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.
Claim 4
Independent Claim
200 words
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.
Claim 5
Dependent Claim
57 words
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.
Claim 6
Dependent Claim
43 words
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.
Claim 7
Dependent Claim
40 words
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.
Claim 8
Dependent Claim
33 words
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.
Claim 9
Independent Claim
268 words
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.
Claim 10
Independent Claim
268 words
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.
Claim 11
Dependent Claim
72 words
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.
Claim 12
Dependent Claim
163 words
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.
Claim 13
Dependent Claim
163 words
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.
Claim 14
Dependent Claim
72 words
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.
Claim 15
Dependent Claim
54 words
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.
Claim 16
Dependent Claim
66 words
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.
References Cited (Backward Citations)
US3964028A
Cited
US4168541A
Cited
US4322795A
Cited
US4458310A
Cited
US4463420A
Cited
US4530054A
Cited
US4835686A
Cited
US4920478A
Cited
US4833642A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-08-26 | 1995-02-25 | 1995-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-08-26 | 1999-02-25 | 1999-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-08-26 | 2003-02-25 | 2003-08-27 | $7700.00 | Window Closed / Lapsed |