Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-11-16
2002-02-05
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000, C711S136000, C711S170000
Reexamination Certificate
active
06345337
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a computer memory cache and, more particularly, to determining a single reference residency time for data within the cache.
BACKGROUND OF THE INVENTION
Caching is a technique used to improve computer performance at all levels of the computer storage hierarchy. When a central processing unit (CPU) requests data for processing, the data is often moved from a slower, less costly memory to a high speed, more costly, memory that can be accessed directly by the CPU. The higher speed memory is generically referred to as a cache. In some data processing systems, the cache is housed within a cache control unit (CCU).
A typical caching algorithm permits data staged to the cache to remain in the cache for some indeterminate interval of time. If the CPU re-references the data while the data is still in the cache, then the caching algorithm allows the data to continue to remain in the cache. On the other hand, the caching algorithm will “age out” old data and overwrite the old data with new data if the old data is not timely re-referenced by the CPU.
Most cache management systems are based on a least recently used (LRU) algorithm. The LRU algorithm uses a stack of a limited size. A most recently used data request is placed on the top of the stack. Consequently, a least recently used data request is at the bottom of the stack. If a new request arrives when the stack is full, the least recently used request is removed from the bottom of the stack, and the new request is placed on the top of the stack.
The LRU caching algorithm is effective due to a characteristic of computer system operation called locality of reference. During any interval of time, data references are concentrated on a relatively small set of the elements assigned to the cache. Also, once a data element is referenced, the probability of it being re-referenced is highest soon after it is first referenced, with the probability of re-referencing diminishing as the time interval since the first reference increases.
A processor can access data from a cache in considerably less time than it can access data that is not in the cache. The satisfactory performance of the cache system depends, in part, on whether a desired item of data is in the cache at the time of re-referencing the data. Performance is therefore affected by the length of time for which the data is permitted to remain in the cache. When accessing data, if the data is in cache, the access is called a “cache it.” If the data is not in cache, the access is called a “cache miss.”
A single reference residency time (SRRT) of a storage subsystem cache is the length of time that passes between staging an item of data into the cache and aging it out, assuming that no reference to the data occurs after it is staged. The SRRT is an important indicator of cache performance. Generally, the longer the SRRT, i.e., the longer a unit of data remains in cache, the lesser the apparent demand on the cache. In contrast, a shorter SRRT indicates that the unit of data is overwritten sooner, and that the demand for cache resources is greater.
U.S. Pat. No. 5,452,440 to Salsburg, entitled “Method And Structure For Evaluating And Enhancing The Performance Of Cache Memory Systems” describes a method for determining which data should be placed into cache. However, the method does not determine the amount of time that the data remains in the cache.
U.S. Pat. No. 5,787,471 to Inoue et al., entitled “Cache Memory Management Apparatus Having A Replacement Method Based On The Total Data Retrieval Time And The Data Size” describes a cache memory management device. The device measures a time period required to obtain data from a database, and it also considers which data should be moved into the cache and which data should be removed from the cache. The device does not determine the amount of time that the data remains in the cache.
U.S. Pat. No. 5,606,688 to McNutt et al., entitled “Method And Apparatus For Dynamic Cache Memory Allocation Via Single-Reference Residency Times”, describes a method for managing a cache that includes measuring SRRT. However, the method requires access to an LRU list from the CCU. Consequently, this method can be used only in a system in which the CCU provides access to the LRU list.
U.S. Pat. No. 5,590,308 to Shih, entitled “Method And Apparatus For Reducing False Invalidations In Distributed Systems” describes a method for managing an LRU stack. The method considers a data residency time, but the time is determined by, and obtained from within, a CCU. Consequently, this method can be used only in a system in which the CCU is capable of reporting the data residency time.
Another approach to determining SRRT is offered by the Astex software product, available from Computer Associates, Inc. of Islandia, N.Y. Astex uses an input/output disconnect time to determine whether a data access is a cache hit or a cache miss, and thereafter estimates SRRT. A disconnect time of 0 corresponds to a cache hit, and a disconnect time of greater than 0 indicates a cache miss. The disconnect time cannot readily be obtained in all systems, so consequently, this method is limited to use with systems that report the disconnect time.
Accordingly, it is an object of the present invention to provide a method of determining the SRRT of a cache without requiring access to any information maintained within the CCU.
It is a second object of the present invention to provide a method for determining the SRRT of a cache that can be used generically, that is, independent of the platform upon which the method is employed.
SUMMARY OF THE INVENTION
In accordance with the invention, a method is provided for determining a single reference residency time of a cache. The method comprises the steps of causing test data to be staged to the cache and measuring a response time after a wait time has elapsed. The measuring step is repeated for a plurality of values of wait time. The method also includes the step of determining a boundary value of the wait time. A wait time of less than or equal to the boundary value yields a corresponding response time representing a cache hit and a wait time of greater than the boundary value yields a corresponding response time representing a cache miss. The boundary value is an estimate of the single reference residency time of the cache.
REFERENCES:
patent: 4920478 (1990-04-01), Furuya et al.
patent: 5452440 (1995-09-01), Salsburg
patent: 5590308 (1996-12-01), Shih
patent: 5606688 (1997-02-01), McNutt et al.
patent: 5787471 (1998-07-01), Inoue et al.
IBM Technical Disclosure Bulletin, vol. 37, No. 06B, Jun. 1994, pp. 465-468, “Hit Ratio Estimates for Non-Cached Volumes”.
McNutt Bruce
Short David Alastair
Smith Brian Jay
Bluestone Randall J.
International Business Machines - Corporation
Ohlandt Greeley Ruggiero & Perle LLP
Song Jasmine
Yoo Do Hyun
LandOfFree
Method and system for determining a cache single reference... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for determining a cache single reference..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for determining a cache single reference... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973861