EP0509231A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method of replacing data in a cache
Assignee: International Business Machines Corp
•
Filing: 1992-03-11
•
Granted: —
•
Expires: 2012-03-11
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 lease 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 Warren Shih
- 👤 James Franklin Macon, Jr.
- 👤 Shauchi Ong
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 15:52
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: 8
Claim 1
Independent Claim
198 words
Method for replacing data in a data cache store in which demand data and prefetch data are stored, characterized by the steps of dividing said cache store into a prefetch section and a demand section; storing demand data in said demand section; storing prefetch data in said prefetch section; determining a prefetch 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 of the basis of a comparison of the prefetch hit density and the prefetch hit density.
Claim 2
Dependent Claim
37 words
Method for replacing data in a data cache store as in claim 1, characterized in that said prefetch hit density and the demand hit density are determined on the basis of a predetermined number of input/output requests.
Claim 3
Dependent Claim
58 words
Method for replacing data in a data cache store as in claim 1 or 2, characterized in that an entry from said prefetch section is replaced if said demand hit density is greater than the prefetch density, and that an entry from said prefetch section is replaced if said demand hit density is equal to the prefetch density.
Claim 4
Dependent Claim
77 words
Method for replacing data in a data cache store as in claim 1, characterized by 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, and wherein said prefetch hit density and the demand hit density are determined on the basis of a predetermined number of input/output requests.
Claim 5
Dependent Claim
32 words
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 prefetch density.
Claim 6
Dependent Claim
120 words
Method for replacing data in a data cache store in which demand data and prefetch data are stored, characterized by the steps of dividing said cache store into a prefetch section and a demand section; storing demand data in said demand section; storing prefetch data in said prefetch section; 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 as a function 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 7
Dependent Claim
104 words
Method for replacing data in a data cache store in which demand data and prefetch data are stored, characterized by the steps of dividing said cache store into a prefetch section and a demand section; storing demand data in said demand section; storing prefetch data in said prefetch section; 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 as a function of a number of data requests hits in said demand section and a number of data request hits in said prefetch section.
Claim 8
Dependent Claim
56 words
Method for replacing data in a data cache store as in claim 6 or 7, characterized by 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)
EP0391871A2
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.