On competitive online read-many parallel disks scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On competitive online read-many parallel disks scheduling

Full text

Pdf (43 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures table of contents

Las Vegas, Nevada, USA

SESSION: Brief announcements table of contents

Pages: 217 - 217

Year of Publication: 2005

ISBN:1-58113-986-1

Authors

Rahul Shah	Purdue University, West Lafayette, IN
Peter J. Varman	Rice University, Houston, TX
Jeffrey Scott Vitter	Purdue University, West Lafayatte, IN

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 8, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1073970.1074006 What is a DOI?

ABSTRACT

We consider the natural extension of the single disk caching problem to parallel disk I/O model. We close the existing gap between lower and upper bounds and achieve optimal competitive ratio of O(√D) when lookahead is more than the memory size M. When lookahead is smaller, we derive various upper bounds and lower bounds on the competitive ratio under various adversarial models.

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	David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter, Duality between Prefetching and Queued Writing with Parallel Disks, Proceedings of the 9th Annual European Symposium on Algorithms, p.62-73, August 28-31, 2001
	2	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 [doi>10.1145/301816.301835]
	3	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 [doi>10.1145/378580.378648]
	4	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 [doi>10.1145/1007912.1007950]