 |
|
|
|
|
|
 Title: |
US6996676:
System and method for implementing an adaptive replacement cache policy
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Megiddo, Nimrod; Palo Alto, CA, United States of America
Modha, Dharmendra Shantilal; San Jose, CA, United States of America
|
| Assignee: |
International Business Machines Corporation, Armonk, NY, United States of America
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
2006-02-07
/ 2002-11-14
|
| Application Number: |
US2002000295507
|
| IPC Code: |
Advanced:
G06F 12/00;
G06F 12/12;
Core:
more...
|
| ECLA Code: |
G06F12/12B6B;
|
| U.S. Class: |
711/129;
711/133;
711/170;
|
| Field of Search: |
711/129,133,170
|
| Priority Number: |
| 2002-11-14 |
US2002000295507 |
|
| 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.
|
| Attorney, Agent or Firm: |
Kassatly, Samuel A. ;
|
| Primary / Asst. Examiners: |
Lane, Jack;
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Family: |
Show 4 known family members
|
First Claim:
Show all 42 claims |
1. A method for adaptively managing pages in a cache memory with a variable workload, comprising: maintaining the cache memory into a first list L1 and a second list L2; wherein the cache memory has a capacity to store c pages; adaptively distributing the workload between the first list L1 and the second list L2, to a total capacity of c pages; and wherein maintaining the cache memory comprises dividing the first list L1 into two list portions T1 and B1.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 6 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
“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
CCA: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.
|
| Continuity Data: |
| Application Number | Filed | Notes |
|---|
|
|
US2002000295507 | 2002-11-14 | is a
related to the prior publication |
| |
US20040098541A1 issued 2004-05-20 System and method for implementing an adaptive replacement cache policy
|
|
|
|
US2002000295507 | 2002-11-14 | is a
related to the prior publication |
| |
US20050235114A1 issued 2005-10-20 System and method for adaptively managing pages in a memory
|
|
|
|
US2005000151363 | 2005-06-13 | is a
continuation of |
|
>US2002000295507<
| 2002-11-14 |
(pending)
[presumed granted]
|
| |
US6996676 issued 2006-02-07 System and method for implementing an adaptive replacement cache policy
|
|
|
|
11151363 | | is a
continuation of |
|
>US2002000295507<
| 2002-11-14 |
|
| |
US6996676 issued 2006-02-07 System and method for implementing an adaptive replacement cache policy
|
|
|
|
 Nominate this for the Gallery...
|
|
