MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Hutchinson, David A.
Sanders, Peter
Vitter, Jeffrey Scott		dblp
dblp
dblp
Editor(s):
Meyer auf der Heide, Friedhelmdblp
BibTeX cite key*:
HutSanVit2001
Title, Booktitle
Title*:
Duality Between Prefetching and Queued Writing with Parallel Disks
Booktitle*:
Proceedings of the 9th Annual European Symposium on Algorithms (ESA-01)
Event, URLs
Conference URL::
http://www.brics.dk/esa2001/
Downloading URL:
http://www.mpi-sb.mpg.de/~sanders/papers/
Event Address*:
Aarhus, Denmark
Language:
English
Event Date*
(no longer used):
August 28 - 31
Organization:
EATCS
Event Start Date:
28 August 2001
Event End Date:
31 August 2001
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2161
Number:
Month:
August
Pages:
62-73
Year*:
2001
VG Wort Pages:
31
ISBN/ISSN:
3-540-42493-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Parallel disks promise to be a cost effective means for achieving
high bandwidth in applications involving massive data sets, but
algorithms for parallel disks can be difficult to devise. To combat
this problem, we define a useful and natural duality between writing
to parallel disks and the seemingly more difficult problem of
prefetching. We first explore this duality for applications involving
read-once accesses using parallel disks. We get a simple linear time
algorithm for computing optimal prefetch schedules and analyze the
efficiency of the resulting schedules for randomly placed data and for
arbitrary interleaved accesses to striped sequences. Duality also
provides an optimal schedule for the integrated caching and
prefetching problem, in which blocks can be accessed multiple times.
Another application of this duality gives us the first parallel disk
sorting algorithms that are provably optimal up to lower order terms.
One of these algorithms is a simple and practical variant of multiway
merge sort, addressing a question that has been open for some time.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{HutSanVit2001,
AUTHOR = {Hutchinson, David A. and Sanders, Peter and Vitter, Jeffrey Scott},
 EDITOR = {Meyer auf der Heide, Friedhelm},
 TITLE = {Duality Between Prefetching and Queued Writing with Parallel Disks},
 BOOKTITLE = {Proceedings of the 9th Annual European Symposium on Algorithms (ESA-01)},
 PUBLISHER = {Springer},
 YEAR = {2001},
 ORGANIZATION = {EATCS},
 VOLUME = {2161},
 PAGES = {62--73},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Aarhus, Denmark},
 MONTH = {August},
 ISBN = {3-540-42493-8},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Peter Sanders		Created
01/21/2002 15:55:48
Revisions
7.
6.
5.
4.
3.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Uwe Brahm
Uwe Brahm		Edit Dates
30.05.2005 15:32:01
30.05.2005 15:31:42
30.05.2005 15:31:39
04/25/2002 09:49:08 PM
04/25/2002 09:45:15 PM