|
USENIX 2005 Annual Technical Conference, General Track — Abstract
Pp. 293–308 of the Proceedings
SARC: Sequential Prefetching in Adaptive Replacement Cache
Binny S. Gill and Dharmendra S. Modha, IBM Almaden Research Center
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-theart
LRU variants on hardware for IBM's flagship storage
controller Shark. On Shark hardware with 8 GB cache and
16 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 5.18ms as compared to
33.35ms and 8.92ms for the two LRU variants.
- View the full text of this paper in HTML and PDF.
Until April 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
