Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2006-02-07
2006-02-07
Lane, Jack (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S170000
Reexamination Certificate
active
06996676
ABSTRACT:
An adaptive replacement cache policy dynamically maintains two lists of pages, a recency list and a frequency list, in addition to a cache directory. The policy keeps these two lists to roughly the same size, the cache size c. Together, the two lists remember twice the number of pages that would fit in the cache. At any time, the policy selects a variable number of the most recent pages to exclude from the two lists. The policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time. It achieves such online, on-the-fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively. This allows the policy to balance between recency and frequency in an online and self-tuning fashion, in response to evolving and possibly changing access patterns. The policy is also scan-resistant. It allows one-time-only sequential read requests to pass through the cache without flushing pages that have temporal locality. The policy is extremely simple to implement and requires only constant-time overhead per request. The policy has negligible space overhead.
REFERENCES:
patent: 4463424 (1984-07-01), Mattson et al.
patent: 4464712 (1984-08-01), Fletcher
patent: 4503501 (1985-03-01), Coulson et al.
patent: 4780815 (1988-10-01), Shiota
patent: 5481691 (1996-01-01), Day, III et al.
patent: 5752255 (1998-05-01), Jarvis
patent: 6041390 (2000-03-01), Liu et al.
patent: 6154813 (2000-11-01), Martin et al.
patent: 6209062 (2001-03-01), Boland et al.
patent: 6327643 (2001-12-01), Egan
patent: 6408368 (2002-06-01), Parady
“Least-Recently-Used-Page-Replacement Algorithm For Cache Memories,” IBM Technical Disclosure Bulletin, vol. 25 No. 3A, Aug. 1982.
S. Kim et al., “Area Efficient Architectures for Information Integrity in Cache Memories,” IEEE-CS\TCCA:TC on Computer Architecture, 1999.
F. Mounes et al. ,“The Effect of Using State-Based Priority In formation in a Shared-Memory Multiprocessor Cache Replacement Policy,” Technical Report No: HPPC-97-11, Nov. 1997.
J. Peir et al., “Capturing Dynamic Memory Reference Behavior with Adaptive Cache Topology,” 1998.
K. Psounis et al., “Efficient Randomized Web-Cache Replacement Schemes Usin Samples From Past Eviction Times,” IEEE/ACM Transactions On Networking, vol. 10, No. 4, Aug. 2002.
J. Choi et al., “Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement Scheme,” IEEE Transactions On Computers, vol. 51, No. 7, Jul. 2002.
D. Lee et al., “LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies,” IEEE Transactions On Computers, vol. 50, No. 12, Dec. 2001.
J. Robinson et al., “ Data Cache Management Using Frequency-Based Replacement,” pp. 134-142, 1990.
S. Jiang et al., “LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance,” in Proc. ACM Sigmetrics Conf., 2002.
T. Johnson et al., “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” in Proc. VLDB Conf., pp 297-306, 1994.
E. O'Neil et al., “An Optimality Proof of the LRU-K Page Replacement Algorithm,” Journal of the ACM, vol. 46, No. 1, Jan. 1999, pp. 92-112.
Megiddo Nimrod
Modha Dharmendra Shantilal
International Business Machines - Corporation
Kassatly Samuel A.
Lane Jack
LandOfFree
System and method for implementing an adaptive replacement... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for implementing an adaptive replacement..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for implementing an adaptive replacement... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3694035