| ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
USENIX '05 Paper
[USENIX '05 Technical Program]
SARC: Sequential Prefetching in Adaptive Replacement Cache Binny S. Gill and Dharmendra S. Modha
Abstract:
Sequentiality of reference is an ubiquitous access pattern dating
back at least to Multics. Sequential workloads lend themselves to
highly accurate prediction and prefetching. In spite of the
simplicity of the workload, design and analysis of a good
sequential prefetching algorithm and associated cache replacement
policy turns out to be surprisingly intricate. As first
contribution, we uncover and remedy an anomaly (akin to famous
Belady's anomaly) that plagues sequential prefetching when
integrated with caching. Typical workloads contain a mix of
sequential and random streams. As second contribution, we design a
self-tuning, low overhead, simple to implement, locally adaptive,
novel cache management policy SARC that dynamically and
adaptively partitions the cache space amongst sequential and
random streams so as to reduce the read misses. As third
contribution, we implemented SARC along with two popular
state-of-the-art LRU variants on hardware for IBM's flagship
storage controller Shark. On Shark hardware with
 GB cache and
 RAID-5 arrays that is serving a workload akin to Storage
Performance Council's widely adopted SPC-1 benchmark, SARC
consistently and dramatically outperforms the two LRU
variants shifting the throughput-response time curve to the right
and thus fundamentally increasing the capacity of the system. As
anecdotal evidence, at the peak throughput, SARC has average
response time of  ms as compared to  ms and  ms
for the two LRU variants.
Next: Introduction Binny Gill 2005-02-14 |
|
This paper was originally published in the
Proceedings of the 2005 USENIX Annual Technical Conference,
April 10–15, 2005, Anaheim, CA, USA Last changed: 2 Mar. 2005 aw |
|
