FASTSLIM: Prefetch-Safe Trace Reduction for I/O Cache Simulation

Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Jin, W; Sun, X; Chase, JS

Published Date

  • April 1, 2001

Published In

Volume / Issue

  • 11 / 2

Start / End Page

  • 125 - 160

Electronic International Standard Serial Number (EISSN)

  • 1558-1195

International Standard Serial Number (ISSN)

  • 1049-3301

Digital Object Identifier (DOI)

  • 10.1145/384169.384170

Citation Source

  • Scopus