Article

Free access

Minimizing stall time in single and parallel disk systems

Authors:

Susanne Albers,

Naveen Garg,

Stefano LeonardiAuthors Info & Claims

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

Pages 454 - 462

https://doi.org/10.1145/276698.276858

Published: 23 May 1998 Publication History

PDF eReader

References

[1]

L.A. Belad3: A stud), of replacement algorithms for virtual :;torage computers./BM Systems Journal, 5:78-101, 1966.

Google Scholar

[2]

A. Borodin, S. Irani, P. Raghavan and B. Schieber. Competitive paging with locality of reference. Journal on Computer and System Sciences, 50:24,1-258, 1995.

Digital Library

Google Scholar

[3]

P. Cao, E.W. Felten, A.R. Karlin and K. Li. A study of integrated prefetching and caching strategies. In Prec. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pages 188-196,1995.

Digital Library

Google Scholar

[4]

K.M. Curewith, P. Krishnan and J.S. Vitten Practical prefetching via data compression. In Prec. 1993 ACM SIGMOD inter. national Conference on Management of Data, pages 257-266, 1993.

Crossref

Google Scholar

[5]

C.S. Ellis and D. Kotz. Prefetching in file systems for M~ID multiprocessors. In Prec. 1989 International Conference on Parallel Processing, pages I306-314, 1989.

Google Scholar

[6]

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

Digital Library

Google Scholar

[7]

A. Fiat and A.R. Karlin. Randomized and multiprocessor paging v.,ith locality of reference. In Prec. 27th Annual ACM Symposium on Theory of Computing, pages 626-634,1995.

Digital Library

Google Scholar

[8]

A. Fiat and Z. Rosen. Experimental studies of access graph based heuristics. Beating the LRU standard. In Prec. 8th ACM-SIAM Symposium on Discrete Algorithms, pages 63- 72, 1997.

Digital Library

Google Scholar

[9]

A.R. Karlin, S. Phillips and P. Raghavan. Markov paging. Prec. 33rd Annual Symposium on Foundations of Computer Science, pages 208-217, 1992.

Digital Library

Google Scholar

[10]

Tracy Kimbrel. Parallel pret~tching and caching (PhD thesis). Technical report 97-07-03, Department of Computer Science and Engineering, University of Washington, 1997.

Digital Library

Google Scholar

[11]

T. Kimbrel, A. Tomkins, R.H. Patterson, B. Bershad, P. Cao, E.W. Felten, G.A. Gibson, A.R. Karlin and K. Li. A tracedriven comparison of algorithms for parallel prefetching and caching. In Proceedings of the ACM SIGOPS/USENIX As. soeiafion Symposium on Operating System Design and Implementation (OSDI), October 1996.

Digital Library

Google Scholar

[12]

D. Kotz and C.$. Ellis. Practical prefetehing techniques for mulitprocessor file systems. Journal of Distributed and Fatal. 1el Databases, 1:33-51, 1993.

Digital Library

Google Scholar

[13]

T. Kimbrel and A.R. Karlin. Near-optimal parallel prefetch. ing anch caching. In Prec. 37th iEEE Annual Symposium on Foundations of Computer Science, pages 540--549, 1996.

Crossref

Google Scholar

[14]

P. Krishnan and J.S. Vitter. Optimal prediction for prefetching in the worst case. In Prec. 5th ACM-SIAM Symposium on Discrete Algorithms, pages 392--401, 1994.

Digital Library

Google Scholar

[15]

K.-K. Lee and P. Varman. Prefetching and I/O parallelism in multiple disk systems. In Prec. 1995 international Conference on Parallel Processing, pages IiI160-163, 1995.

Google Scholar

[16]

M. Palmer and S.B. Zdonik. Fide: A cache that learns to fetch. In Prec. 17th International Conference on V'eo' Large Data Bases, pages 255-264, 1991.

Digital Library

Google Scholar

[17]

R.H. Patterson, G.A. Gibson, E. Ginfing, D. Stodolsky and J. Zelenka. Informed prefetching and caching. In Free, 15th Symposium on Operating Systems Principles, pages 79-95, 1995.

Digital Library

Google Scholar

[18]

A. Schrijver. Linear and Integer Programming. Wiley, Chichester, 1986.

Digital Library

Google Scholar

[19]

D.D. $1eator and R.E. Tarjan. Amortized efficiency of list up. date and paging rules. Communication of the ACM, 28:202- 208, 1985.

Digital Library

Google Scholar

[20]

J. Vitter and P. Krishnan. Optimal prefetching via data compression. In Proc. 32rid Annual Symposium on Foundations of Computer Science, pages 121-130, 1991.

Digital Library

Google Scholar

Cited By

View all

Zhao DQiao KRaicu IReed DSun XFoster I(2014)HyCache+Proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2014.11(267-276)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1109/CCGrid.2014.11
Hon WShah RVarman PVitter JMeyer auf der Heide FShavit N(2008)Tight competitive ratios for parallel disk prefetching and cachingProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378593(352-361)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1145/1378533.1378593
Dementiev RKettner LSanders P(2007) S TXXL : standard template library for XXL data sets Software: Practice and Experience10.1002/spe.84438:6(589-637)Online publication date: 6-Aug-2007
https://doi.org/10.1002/spe.844
Show More Cited By

Index Terms

Minimizing stall time in single and parallel disk systems
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Mathematical optimization
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization

Recommendations

Minimizing stall time in single and parallel disk systems

We study integrated prefetching and caching problems following the work of Cao et al. [1995] and Kimbrel and Karlin [1996]. Cao et al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk ...
Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows
APPROX '01/RANDOM '01: Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization

We study integrated prefetching and caching in single and parallel disk systems. Arecen t approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow ...
Integrated prefetching and caching in single and parallel disk systems
SPAA '03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures

We study integrated prefetching and caching in single and parallel disk systems. There exist two very popular approximation algorithms called Aggressive and Conservative for minimizing the total elapsed time in the single disk problem. For D parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)6

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhao DQiao KRaicu IReed DSun XFoster I(2014)HyCache+Proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2014.11(267-276)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1109/CCGrid.2014.11
Hon WShah RVarman PVitter JMeyer auf der Heide FShavit N(2008)Tight competitive ratios for parallel disk prefetching and cachingProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378593(352-361)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1145/1378533.1378593
Dementiev RKettner LSanders P(2007) S TXXL : standard template library for XXL data sets Software: Practice and Experience10.1002/spe.84438:6(589-637)Online publication date: 6-Aug-2007
https://doi.org/10.1002/spe.844
Shah RVarman PVitter JGibbons PAdler M(2004)Online algorithms for prefetching and caching on parallel disksProceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1007912.1007950(255-264)Online publication date: 27-Jun-2004
https://dl.acm.org/doi/10.1145/1007912.1007950
Dementiev RSanders PRosenberg AMeyer auf der Heide F(2003)Asynchronous parallel disk sortingProceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures10.1145/777412.777435(138-148)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/777412.777435
Wei Jin Barve RTrivedi K(2002)A simple characterization of provably efficient prefetching algorithmsProceedings International Conference on Dependable Systems and Networks10.1109/DSN.2002.1029003(571-580)Online publication date: 2002
https://doi.org/10.1109/DSN.2002.1029003
Kallahalla MVarman PRosenberg A(2001)Optimal prefetching and caching for parallel I/O sytemsProceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures10.1145/378580.378648(219-228)Online publication date: 3-Jul-2001
https://dl.acm.org/doi/10.1145/378580.378648
Hutchinson DSanders PVitter J(2001)Duality between Prefetching and Queued Writing with Parallel DisksAlgorithms — ESA 200110.1007/3-540-44676-1_5(62-73)Online publication date: 17-Aug-2001
https://doi.org/10.1007/3-540-44676-1_5
Albers SWitt C(2001)Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network FlowsApproximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques10.1007/3-540-44666-4_6(12-24)Online publication date: 17-Aug-2001
https://doi.org/10.1007/3-540-44666-4_6
Kimbrel TTarjan RWarnow T(1999)Interleaved prefetchingProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314877(557-565)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314877
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Minimizing stall time in single and parallel disk systems

Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows

Integrated prefetching and caching in single and parallel disk systems