System and method for dynamic sizing of cache sequential list
AssigneeInternational Business Machines Corporation
InventorsBinny Gill, Dharmendra Modha
Life of this patent
Estimating the term…
Abstract
A self-tuning, low overhead, simple to implement, locally adaptive, novel cache management policy that dynamically and adaptively partitions the cache space amongst sequential and random streams so as to reduce read misses.
Claims32
A method for caching data, comprising:
- maintaining a random data list and a sequential data list;
- dynamically establishing a desired size for the sequential data list.
A data system using a least recently used (LRU) caching scheme using synchronous and asynchronous prefetch of data from a data storage device, the system avoiding violation of stack property substantially without incurring additional sequential misses from cache.
A computer program product comprising:
- means for maintaining a random list;
- means for maintaining a sequential list;
- means for synchronous and asynchronous prefetching of sequential data;
- means for computing a marginal utility of adding space to the sequential list in terms of a rate of sequential misses;
- means for empirically determining a marginal utility of adding space to the random list;
- and
- means for, responsive to the computing and determining means, establishing a desired size of the sequential list.
In a processor associated with at least one cache having a sequential list and a random list, both lists defining respective least recently used (LRU) portions each of which is associated with a respective marginal utility that changes during operation, logic including, during operation, attempting to equalize the marginal utilities.
A processor associated with a cache and executing logic to:
- move at least one newly prefetched group of units of data along with an asynchronous trigger unit of data in the group of units of data to a most recently used (MRU) portion of a sequential cache list;
- and
- move at least some unaccessed units of data in the group of units of data to the MRU portion of the sequential cache list.
A processor associated with a cache and executing logic for:
- determining whether the size of at least a portion of a sequential cache list exceeds a desired size;
- and
- replacing at least one cache element, based on the result of determining whether the size of at least a portion of the sequential cache list exceeds the desired size.
Dependencies are inferred from the claim text.