System and method for implementing an adaptive replacement cache policy
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
-
-
39. An apparatus for adaptively managing pages in a cache memory with a variable workload, comprising:
-
the cache memory maintaining a first list L1 and a second list L2;
wherein the cache memory has a capacity to store c pages;
means for adaptively distributing the workload between the first list L1 and the second list L2, to a total capacity of c pages;
wherein the first list L1 is comprised of two list portions T1 and B1; and
wherein the second list L2 is comprised of two list portions T2 and B2. - View Dependent Claims (40)
-
-
41. A computer program product that adaptively manages pages in a cache memory with a variable workload, comprising:
-
the cache memory maintaining a first list L1 and a second list L2;
wherein the cache memory has a capacity to store c pages;
a set of instruction codes that adaptively distributes the workload between the first list L1 and the second list L2, to a total capacity of c pages;
wherein the first list L1 is comprised of two list portions T1 and B1; and
wherein the second list L2 is comprised of two list portions T2 and B2. - View Dependent Claims (42)
-
Specification