FASTSLIM: Prefetch-Safe Trace Reduction for I/O Cache Simulation
Trace-driven simulation is a valuable tool for evaluating I/O systems. This article presents a new algorithm, called FASTSLIM, that reduces the size of I/O traces and improves simulation performance without compromising simulation accuracy. FASTSLIM is more general than existing trace reduction algorithms in two ways. First, it is prefetch-safe: traces reduced by FASTSLIM yield provably exact simulations of I/O systems that use prefetching, a key technique for improving I/O performance. Second, FASTSLIM is compatible with a wide range of replacement policies, including common practical approximations to LRU. FASTSLIM-reduced traces are safe for simulations of storage hierarchies and systems with parallel disks. This article gives a formal treatment of prefetching and replacement issues for trace reduction, introduces the FASTSLIM algorithm, proves that FASTSLIM and variants are safe for a broad range of I/O caching and prefetching systems, and presents empirical results comparing FASTSLIM to competing trace reduction algorithms. © 2001, ACM. All rights reserved.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 4602 Artificial intelligence
- 0806 Information Systems
- 0802 Computation Theory and Mathematics
Citation
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Operations Research
- 4901 Applied mathematics
- 4602 Artificial intelligence
- 0806 Information Systems
- 0802 Computation Theory and Mathematics