Minimizing stall time in single and parallel disk systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimizing stall time in single and parallel disk systems

Full text

Pdf (1.19 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 454 - 462

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Susanne Albers	Max-Planck-Institut für Informatik, Im Stadtwald, 66123 Saarbrücken, Germany
Naveen Garg	Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi 110016, India
Stefano Leonardi	Max-Planck-Institut für Informatik, Saarbrücken, Germany, Dipartimento di Informatica Sistemistica, Università di Roma 'La Sapienza', via Salaria 113, 00198-Roma, Italia

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276858 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L.A. Belad3: A stud), of replacement algorithms for virtual :;torage computers./BM Systems Journal, 5:78-101, 1966.
	2	Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
	3	Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, A study of integrated prefetching and caching strategies, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.188-197, May 15-19, 1995, Ottawa, Ontario, Canada
	4	Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
	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.
	6	Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
	7	Amos Fiat , Anna R. Karlin, Randomized and multipointer paging with locality of reference, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.626-634, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225280]
	8	Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
	9	A.R. Karlin, S. Phillips and P. Raghavan. Markov paging. Prec. 33rd Annual Symposium on Foundations of Computer Science, pages 208-217, 1992.
	10	Tracy Kimbrel, Parallel prefetching and caching, University of Washington, Seattle, WA, 1998
	11	Tracy Kimbrel , Andrew Tomkins , R. Hugo Patterson , Brian Bershad , Pei Cao , Edward W. Felten , Garth A. Gibson , Anna R. Karlin , Kai Li, A trace-driven comparison of algorithms for parallel prefetching and caching, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.19-34, October 29-November 01, 1996, Seattle, Washington, United States
	12	David Kotz , Carla Schlatter Ellis, Practical prefetching techniques for multiprocessor file systems, Distributed and Parallel Databases, v.1 n.1, p.33-51, Jan. 1993 [doi>10.1007/BF01277519]
	13	A. R. Karlin, Near-optimal parallel prefetching and caching, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.540, October 14-16, 1996
	14	P. Krishnan , Jeffrey Scott Vitter, Optimal prediction for prefetching in the worst case, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.392-401, January 23-25, 1994, Arlington, Virginia, United States
	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.
	16	Mark Palmer , Stanley B. Zdonik, Fido: A Cache That Learns to Fetch, Proceedings of the 17th International Conference on Very Large Data Bases, p.255-264, September 03-06, 1991
	17	R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
	18	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	19	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	20	Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.121-130, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185360]

CITED BY 9

	Mahesh Kallahalla , Peter J. Varman, Optimal read-once parallel disk scheduling, Proceedings of the sixth workshop on I/O in parallel and distributed systems, p.68-77, May 05-05, 1999, Atlanta, Georgia, United States
	Tracy Kimbrel, Interleaved prefetching, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.557-565, January 17-19, 1999, Baltimore, Maryland, United States
	Wei Jin , Xiaobai Sun , Jeffrey S. Chase, FastSlim: prefetch-sfe trace reduction for I/O cache simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.2, p.125-160, April 2001
	Mahesh Kallahalla , Peter J. Varman, Optimal prefetching and caching for parallel I/O sytems, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.219-228, July 2001, Crete Island, Greece
	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Approximating the throughput of multiple machines under real-time scheduling, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.622-631, May 01-04, 1999, Atlanta, Georgia, United States
	Mahesh Kallahalla , Peter J. Varman, Analysis of simple randomized buffer management for parallel I/O, Information Processing Letters, v.90 n.1, p.47-52, 15 April 2004
	Rahul Shah , Peter J. Varman , Jeffrey Scott Vitter, Online algorithms for prefetching and caching on parallel disks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Roman Dementiev , Peter Sanders, Asynchronous parallel disk sorting, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Wing-Kai Hon , Rahul Shah , Peter J. Varman , Jeffrey Scott Vitter, Tight competitive ratios for parallel disk prefetching and caching, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany