Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Hutchinson, David A.
Sanders, Peter
Vitter, Jeffrey Scott

dblp
dblp
dblp



Editor(s):

Meyer auf der Heide, Friedhelm

dblp



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

URL of the conference:

http://www.brics.dk/esa2001/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 03:55:48 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section