More Web Proxy on the site http://driver.im/

Article

Optimal prefetching and caching for parallel I/O sytems

Authors:

Mahesh Kallahalla,

Peter J. VarmanAuthors Info & Claims

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

Pages 219 - 228

https://doi.org/10.1145/378580.378648

Published: 03 July 2001 Publication History

Abstract

We address the problem of prefetching and caching in a parallel I/O system and present a new algorithm for optimal parallel-disk scheduling. Traditional buffer management algorithms that minimize the number of I/O disk accesses, are substantially suboptimal in a parallel I/O system where multiple I/Os can proceed simultaneously.

We present a new algorithm SUPERVISOR for parallel-disk I/O scheduling. We show that in the off-line case, where apriori knowledge of all the requests is available, SUPERVISOR performs the minimum number of I/Os to service the given I/O requests. This is the first parallel I/O scheduling algorithm that is provably offline optimal. In the on-line case, we study SUPERVISOR in the context of global L-block lookahead, which gives the buffer management algorithm a lookahead consisting of L distinct requests. We show that the competitive ratio of SUPERVISOR, with global L-block lookahead, is Θ(M - L + D), when L ≤ M, and Θ(MD/L), when L > M, where the number of disks is D and buffer size is M.

References

[1]

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, Sept. 1988.

Digital Library

[2]

S. Albers. On the in uence of lookahead in competitive paging algorithms. Algorithmica, 18(3):283-305, July 1997.

[3]

S. Albers, N. Garg, and S. Leonardi. Minimizing stall time in single and parallel disk systems. In Proc. of 30th Annual ACM Symp. on Theory of Computer Science, pages 454-462. ACM Press, May 1998.

Digital Library

[4]

L. M. Baptist and T. H. Cormen. Multidimensional, multiprocessor, out-of-core FFTs with distributed memory and parallel disks. In Proc. of the 11th Annual ACM Symp. on Parallel Algorithms and Architectures, June 1999.

Digital Library

[5]

R. D. Barve, E. F. Grove, and J. S. Vitter. Simple randomized mergesort on parallel disks. Parallel Computing, 23(4):601-631, June 1996.

Digital Library

[6]

R. D. Barve, M. Kallahalla, P. J. Varman, and J. S. Vitter. Competitive parallel disk prefetching and buffer management. Journal of Algorithms, 36(2):152-181, Aug. 2000.

Digital Library

[7]

L. A. Belady. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5(2):78-101, 1966.

Digital Library

[8]

D. Breslauer. On competitive on-line paging with lookahead. In Proc. of the 13th Annual Symp. on Theoretical Aspects of Computer Science, volume 1046 of LNCS, pages 593-603. Springer Verlag, Feb. 1996.

Digital Library

[9]

P. Cao, E. W. Felten, A. R. Karlin, and K. Li. A study of integrated prefetching and caching strategies. In Proc. of the Joint Intl. Conf. on Measurement and Modeling of Computer Systems, pages 188-197. ACM Press, May 1995.

Digital Library

[10]

F. Chang and G. A. Gibson. Automatic I/O hint generation through speculative execution. In Operating Systems Design and Implementation (OSDI '99), pages 1- 14, 1999.

Digital Library

[11]

A. Fiat, R. Karp, M. Luby, L. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, Dec. 1991.

Digital Library

[12]

M. Kallahalla. Scheduling and Buffer Management for Parallel I/O Systems. PhD thesis, Rice University, 2000.

Digital Library

[13]

M. Kallahalla and P. J. Varman. Optimal read-once parallel disk scheduling. In Proc. of Sixth ACM Wkshp. on I/O in Parallel and Distributed Systems, pages 68- 77, Atlanta, GA, 1999. ACM Press.

Digital Library

[14]

A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 5(3):79-119, Mar. 1988.

Digital Library

[15]

T. Kimbrel and A. R. Karlin. Near-optimal parallel prefetching and caching. SIAM J. of Computing, 29(4):1051-1082, 2000.

Digital Library

[16]

L. A. McGeoch and D. D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816- 825, 1991.

Digital Library

[17]

V. S. Pai, A. A. Schaffer, and P. J. Varman. Markov analysis of multiple-disk prefetching strategies for external merging. Theoretical Computer Science, 128(1- 2):211-239, June 1994.

Digital Library

[18]

R. H. Patterson, G. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. In Proc. of the 15th ACM Symp. on Operating Systems Principles, pages 79-95, Dec. 1995.

Digital Library

[19]

P. Sanders, S. Egner, and J. H. M. Korst. Fast concurrent access to parallel disks. In Proc. of the SIAM Symposium on Discrete Algorithms, Jan.2000.

Digital Library

[20]

D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, Feb. 1985.

Digital Library

[21]

P. J. Varman and R. M. Verma. Tight bounds for prefetching and buffer management algorithms for parallel I/O systems. IEEE Trans. on Parallel and Distributed Systems, 10:1262-1275, Dec. 1999.

Digital Library

[22]

J. S. Vitter and E. A. M. Shriver. Optimal algorithms for parallel memory, I: Two-level memories. Algorithmica, 12(2-3):110-147, 1994.

Digital Library

Cited By

Sanders PSingler JStee R(2013)Real-time integrated prefetching and cachingJournal of Scheduling10.1007/s10951-012-0301-116:1(47-58)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10951-012-0301-1
Uppal AChiang RHuang H(2012)Flashy prefetching for high-performance flash drives012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST)10.1109/MSST.2012.6232367(1-12)Online publication date: Apr-2012
https://doi.org/10.1109/MSST.2012.6232367
He JSun XThakur R(2012)KNOWACProceedings of the 2012 IEEE International Conference on Cluster Computing10.1109/CLUSTER.2012.83(429-437)Online publication date: 24-Sep-2012
https://dl.acm.org/doi/10.1109/CLUSTER.2012.83
Show More Cited By

Index Terms

Recommendations

Parallel prefetching and caching
Near-optimal parallel prefetching and caching
FOCS '96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science

The authors consider algorithms for integrated prefetching and caching in a model with a fixed-size cache and any number of backing storage devices (disks). Previously, the single disk case was considered by Cao et al. (1995). They show that the natural ...
Near-Optimal Parallel Prefetching and Caching

Recently there has been a great deal of interest in the operating systems research community in prefetching and caching data from parallel disks, as a technique for enabling serial applications to improve input--output (I/O) performance. In this paper, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

July 2001

340 pages

ISBN:1581134096

DOI:10.1145/378580

Chairman:
Arnold Rosenberg
Univ. of Massachusetts

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA01

Sponsor:

SPAA01: 13th ACM Symposium on Parallel Algorithms and Architectures

Crete Island, Greece

Acceptance Rates

SPAA '01 Paper Acceptance Rate 34 of 93 submissions, 37%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
445
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sanders PSingler JStee R(2013)Real-time integrated prefetching and cachingJournal of Scheduling10.1007/s10951-012-0301-116:1(47-58)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s10951-012-0301-1
Uppal AChiang RHuang H(2012)Flashy prefetching for high-performance flash drives012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST)10.1109/MSST.2012.6232367(1-12)Online publication date: Apr-2012
https://doi.org/10.1109/MSST.2012.6232367
He JSun XThakur R(2012)KNOWACProceedings of the 2012 IEEE International Conference on Cluster Computing10.1109/CLUSTER.2012.83(429-437)Online publication date: 24-Sep-2012
https://dl.acm.org/doi/10.1109/CLUSTER.2012.83
Kandemir MYemliha TPrabhakar RJung M(2012)On Urgency of I/O OperationsProceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)10.1109/CCGrid.2012.40(188-195)Online publication date: 13-May-2012
https://dl.acm.org/doi/10.1109/CCGrid.2012.40
Rafique M(2010)A Capabilities-Aware Programming Model for Asymmetric High-End SystemsProceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing10.1109/CCGRID.2010.131(844-849)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/CCGRID.2010.131
Ozturk OSon SKandemir MKarakoy MTeller P(2008)Prefetch throttling and data pinning for improving performance of shared cachesProceedings of the 2008 ACM/IEEE conference on Supercomputing10.5555/1413370.1413430(1-12)Online publication date: 15-Nov-2008
https://dl.acm.org/doi/10.5555/1413370.1413430
Kandemir MSon SKarakoy M(2008)Improving I/O performance of applications through compiler-directed code restructuringProceedings of the 6th USENIX Conference on File and Storage Technologies10.5555/1364813.1364824(1-16)Online publication date: 26-Feb-2008
https://dl.acm.org/doi/10.5555/1364813.1364824
Li MVarki EBhatia SMerchant A(2008)TaPProceedings of the 6th USENIX Conference on File and Storage Technologies10.5555/1364813.1364819(1-16)Online publication date: 26-Feb-2008
https://dl.acm.org/doi/10.5555/1364813.1364819
Vitter J(2008)Algorithms and data structures for external memoryFoundations and Trends® in Theoretical Computer Science10.1561/04000000142:4(305-474)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1561/0400000014
Son SMuralidhara SOzturk OKandemir MKolcu IKarakoy MMoshovos ATarditi DOlukotun K(2008)Profiler and compiler assisted adaptive I/O prefetching for shared storage cachesProceedings of the 17th international conference on Parallel architectures and compilation techniques10.1145/1454115.1454133(112-121)Online publication date: 25-Oct-2008
https://dl.acm.org/doi/10.1145/1454115.1454133
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents