Patent US5452440A successfully refreshed from Google Patents.
US5452440A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and structure for evaluating and enhancing the performance of cache memory systems
Assignee: GLENRIDGE COMMERCIAL Inc
•
Filing: 1993-07-16
•
Granted: 1995-09-19
•
Expires: 2013-07-16
Abstract
Abstract Method and structure for collecting statistics for quantifying locality of data and thus selecting elements to be cached, and then calculating the overall cache hit rate as a function of cached elements. LRU stack distance has a straight-forward probabilistic interpretation and is part of statistics to quantify locality of data for each element considered for caching. Request rates for additional slots in the LRU are a function of file request rate and LRU size. Cache hit rate is a function of locality of data and the relative request rates for data sets. Specific locality parameters for each data set and arrival rate of requests for data-sets are used to produce an analytical model for calculating cache hit rate for combinations of data sets and LRU sizes. This invention provides algorithms that can be directly implemented in software for constructing a precise model that can be used to predict cache hit rates for a cache, using statistics accumulated for each element independently. The model can rank the elements to find the best candidates for caching. Instead of considering the cache as a whole, the average arrival rates and re-reference statistics for each element are estimated, and then used to consider various combinations of elements and cache sizes in predicting the cache hit rate. Cache hit rate is directly calculated using the to-be-cached files' arrival rates and re-reference statistics and used to rank the elements to find the set that produces the optimal cache hit rate.
Inventors
- 👤 Michael A. Salsburg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:18
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/123; G06F11/00; G06F11/30; G06F11/34; G06F11/3447; G06F12/0802; G06F12/0888; G06F11/3452; G06F2201/00; G06F2201/805; G06F2201/885
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
145 words
A method for operating a computer system including a mass memory, and a plurality of independent elements stored in said mass memory, for determining performance of said computer system should one or more of said elements be cached in a cache memory using a Least Recently Used (LRU) algorithm, said method comprising the steps of: utilizing said computer system to collect a set of re-reference statistics and arrival rate statistics for said plurality of independent elements, said re-reference and arrival rate statistics pertaining to each element independently; using said computer system to create a probabilistic model based upon said set of re-reference and arrival rate statistics; and using said computer system to manipulate said probabilistic model to predict cache hit rate of one or both alterations consisting of including or excluding one or more of said independent elements from cache memory, and cache memory size.
Claim 2
Independent Claim
145 words
A method for operating a computer system including a mass memory, and a plurality of independent elements stored in said mass memory, for determining performance of said computer system should one or more of said elements be cached in a cache memory using a Least Recently Used (LRU) algorithm, said method comprising the steps of: utilizing said computer system to collect a set of re-reference statistics and arrival rate statistics for said plurality of independent elements, said re-reference and arrival rate statistics pertaining to each element independently; using said computer system to create a probabilistic model based upon said set of re-reference and arrival rate statistics; and using said computer system to manipulate said probabilistic model to predict cache hit rate of one or both alterations consisting of including or excluding one or more of said independent elements from cache memory, and cache memory size.
Claim 3
Dependent Claim
30 words
A method as in claim 1 which further comprises the step of manipulating said model and thereby determining which one or more of said independent elements should preferably be cached.
Claim 4
Dependent Claim
41 words
A method as in claim 1 which further comprises the step of ranking said one or more independent elements which should preferably be cached, based upon a predicted improvement in computer system operating performance upon caching each of said independent elements.
Claim 5
Dependent Claim
30 words
A method as in claim 1 wherein said step of collecting is performed during normal operation of said computer system, based upon usage of said one or more independent elements.
Claim 6
Dependent Claim
23 words
A method as in claim 1 wherein said mass memory has a size greater than and an operating speed less than said cache.
Claim 7
Dependent Claim
20 words
A method as in claim 1 wherein said mass memory comprises a disk and said cache comprises solid state memory.
Claim 8
Dependent Claim
20 words
A method as in claim 1 wherein said mass memory comprises a tape library and said cache comprises tape drives.
Claim 9
Dependent Claim
21 words
A method as in claim 1 wherein said mass memory comprises CPU memory pages, and said cache comprises CPU memory cache.
Claim 10
Dependent Claim
66 words
A method as in claim 1 wherein for each independent element for which said statistics are determined: said arrival rate statistics define a fraction of accesses for said independent element with respect to total number of accesses for all independent elements; and said re-reference statistics define a fraction of re-reference accesses of each independent element with respect to total number of accesses for said independent element.
Claim 11
Dependent Claim
47 words
A method as in claim 1 wherein said step of gathering statistics comprises the step of utilizing a Least Recently Used (LRU) stack for each said independent element, said LRU stack containing a plurality of positions indicating recency of use of various portions of said independent element.
Claim 12
Dependent Claim
21 words
A method as in claim 1 wherein an overall cache hit rate is calculated using said re-reference statistics and arrival rate.
Claim 13
Dependent Claim
20 words
A method as in claim 1 wherein said selection of independent elements for caching is determined using said re-reference statistics.
Claim 14
Dependent Claim
16 words
A method as in claim 4 wherein said step of collecting is performed in real time.
Claim 15
Dependent Claim
27 words
A method as in claim 4 wherein said step of collecting is performed utilizing an I/O trace of a previous period of operation of said computer system.
Claim 16
Dependent Claim
24 words
A method as in claim 1 wherein said step of predicting comprises the step of modelling a plurality of cache sizes, using said statistics.
Claim 17
Dependent Claim
48 words
A method as in claim 3 wherein the ranks of said independent elements are determined by: using said re-reference statistics, select all independent elements having rank greater than the rank of the mass memory; and re-ranking said selected independent elements using a ranking function times said arrival rate.
Claim 18
Dependent Claim
17 words
A method as in claim 3 wherein said independent elements are ranked based upon said re-reference statistics.
Claim 19
Dependent Claim
46 words
A method as in claim 17 wherein said independent elements are ranked based upon a ranking function defined as ##EQU26## where: R i =the ranking of ith element; t=the index of the summation; T=the number of LRU slots; and γ it =re-reference statistics for element i.
Claim 20
Independent Claim
35 words
A method as in claim. 17 wherein said independent elements are ranked based upon a probability that an independent element is occupying other LRU slots given that the independent element occupies the last LRU slot.
References Cited (Backward Citations)
US4490782A
Cited
US4669043A
Cited
US4835686A
Cited
US4920478A
Cited
US5241640A
Cited
US5359713A
Cited
US5133060A
Cited
US5043885A
Cited
US5335317A
Cited
US5325509A
Cited
US5353430A
Cited
US5325504A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-18 | 1999-03-20 | 1999-09-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-18 | 2003-03-20 | 2003-09-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-18 | 2007-03-20 | 2007-09-19 | $7700.00 | Window Closed / Lapsed |