MPI-INF D1 Publications: Proceedings Article: Duality Between Prefetching and Queued Writing with Parallel Disks

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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:


(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

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

Attachment Section