Patent US5293609A successfully refreshed from Google Patents.
US5293609A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hit-density-based replacement for data cache with prefetching
Assignee: International Business Machines Corp
•
Filing: 1991-04-19
•
Granted: 1994-03-08
•
Expires: 2011-04-19
Abstract
Abstract A least recently used cache replacement system in which the data cache is logically partitioned into two separate sections, demand and prefetch. A cache directory table and a least recently used table are used to maintain the cache. When a new demand data page is added to the cache, a most recently used (MRU) pointer is updated and points to this new page. When a prefetch page is added to the cache, the least recently used pointer of the demand section is updated with its backward pointer pointing to this new page. A cache hit on a demand of prefetch page moves that page to the top of the least recently used table. When a free page is needed in the cache, it is selected from the demand or prefetch sections of the memory based on a comparison of the demand hit density and the prefetch hit density so to maintain a balance between these two hit densities.
Inventors
- 👤 Feng-Hsien W. Shih
- 👤 James F. Macon, Jr.
- 👤 Shauchi Ong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 19:50
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F12/0802; G06F12/0862; G06F12/0866; G06F12/126
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
207 words
A computer-implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; determining a prefetch hit probability for said prefetch section on the basis of a ratio of a number of hits in said prefetch section to a number of prefetch requests; determining a demand hit probability for said demand section on the basis of a ratio of a number of hits in said demand section to a number of demand requests; determining a prefetch hit density for said prefetch section on the basis of a ratio of prefetch hit probability to a number of data entries in said prefetch section; determining a demand hit density for said demand section on the basis of a ratio of the demand hit probability to a number of data entries in said demand section; and replacing an entry in said demand section or an entry in said prefetch section on the basis of a comparison of the demand hit density and the prefetch hit density.
Claim 2
Dependent Claim
207 words
A computer-implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; determining a prefetch hit probability for said prefetch section on the basis of a ratio of a number of hits in said prefetch section to a number of prefetch requests; determining a demand hit probability for said demand section on the basis of a ratio of a number of hits in said demand section to a number of demand requests; determining a prefetch hit density for said prefetch section on the basis of a ratio of prefetch hit probability to a number of data entries in said prefetch section; determining a demand hit density for said demand section on the basis of a ratio of the demand hit probability to a number of data entries in said demand section; and replacing an entry in said demand section or an entry in said prefetch section on the basis of a comparison of the demand hit density and the prefetch hit density.
Claim 3
Dependent Claim
35 words
A method for replacing data in a data cache store as in claim 1 wherein an entry from said prefetch section is replaced if said demand hit density is greater than the prefetch hit density.
Claim 4
Dependent Claim
35 words
A method for replacing data in a data cache store as in claim 1 wherein an entry from said prefetch section is replaced if said demand hit density is equal to the prefetch hit density.
Claim 5
Dependent Claim
36 words
A method for replacing data in a data cache store as in claim 1 wherein said prefetch hit density and the demand hit density are determined on the basis of a predetermined number of input/output requests.
Claim 6
Dependent Claim
35 words
A method for replacing data in a data cache store as in claim 4 wherein an entry from said prefetch section is replaced if said demand hit density is greater than the prefetch hit density.
Claim 7
Dependent Claim
35 words
A method for replacing data in a data cache store as in claim 2 wherein an entry from said prefetch section is replaced if said demand hit density is equal to the prefetch hit density.
Claim 8
Dependent Claim
54 words
A method for replacing data in a data cache store as in claim 1 further including the steps of determining the least recently used data in the demand section, determining the least recently used data in the prefetch section, and replacing the least recently used data in said demand section or said prefetch section.
Claim 9
Dependent Claim
34 words
A method for replacing data in a data cache store as in claim 7 wherein an entry from said prefetch section is replaced if said demand hit density is greater than prefetch hit density.
Claim 10
Dependent Claim
36 words
A method for replacing data in a data cache store as in claim 7 wherein said prefetch hit density and the demand hit density are determined on the basis of a predetermined number of input/output requests.
Claim 11
Dependent Claim
54 words
A method for replacing data in a data cache store as in claim 9 further including the steps of determining the least recently used data in the demand section, determining the least recently used data in the prefetch section, and replacing the least recently used data in said demand section or said prefetch section.
Claim 12
Dependent Claim
121 words
A computer implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; and adjusting the number of said demand data section entries by replacing data in said demand section or said prefetch section based on a comparison of a number of data requests hits in said demand section, a number of data request hits in said prefetch section, a number of entries in said demand section, and a number of entries in said prefetch section.
Claim 13
Dependent Claim
121 words
A computer implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; and adjusting the number of said demand data section entries by replacing data in said demand section or said prefetch section based on a comparison of a number of data requests hits in said demand section, a number of data request hits in said prefetch section, a number of entries in said demand section, and a number of entries in said prefetch section.
Claim 14
Dependent Claim
104 words
A computer implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; and adjusting the number of said demand data section entries relative to the number of said prefetch data section entries by replacing data in said demand section or said prefetch section based on a comparison of a number of data request hits in said prefetch section.
Claim 15
Dependent Claim
104 words
A computer implemented method for replacing data in a data cache store in which demand data is stored in a demand section of said data cache store and prefetch data is stored in a prefetch section of said data cache store, comprising in combination; storing demand data in said demand section; storing prefetch data in said prefetch section; and adjusting the number of said demand data section entries relative to the number of said prefetch data section entries by replacing data in said demand section or said prefetch section based on a comparison of a number of data request hits in said prefetch section.
Claim 16
Dependent Claim
55 words
A method for replacing data in a data cache store as in claim 12 further including the steps of determining to the least recently used data in the demand section, determining the least recently used data in the prefetch section, and replacing the least recently used data in said demand section or said prefetch section.
References Cited (Backward Citations)
US4489378A
Cited
US4466059A
Cited
US4807110A
Cited
US4928239A
Cited
EP0391871A2
Cited
US5146578A
Cited
US5150472A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-03-07 | 1997-09-06 | 1998-03-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-03-07 | 2001-09-06 | 2002-03-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-03-07 | 2005-09-06 | 2006-03-08 | $7700.00 | Window Closed / Lapsed |