Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Hutchinson, David A.
Sanders, Peter
Vitter, Jeffrey Scott		dblp
dblp
dblp
Not MPG Author(s):
Hutchinson, David A.
Vitter, Jeffrey Scott

BibTeX cite key*:

Sanders2005

Title

Title*:

Duality Between Prefetching and Queued Writing with Parallel Disks

Journal

Journal Title*:

SIAM Journal on Computing
Journal's URL:


Download URL
for the article:

http://epubs.siam.org/fulltext/SICOMP/volume-34/43157.pdf
Language:

English

Publisher

Publisher's
Name:

SIAM
Publisher's URL:


Publisher's
Address:

Philadelphia, USA
ISSN:


Vol, No, pp, Date

Volume*:

34
Number:

6

Publishing Date:

2005

Pages*:

1443-1463
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(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
prefetching plus caching, where 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 had been open for some time.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

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


BibTeX Entry:

@ARTICLE{Sanders2005,
AUTHOR = {Hutchinson, David A. and Sanders, Peter and Vitter, Jeffrey Scott},
 TITLE = {Duality Between Prefetching and Queued Writing with Parallel Disks},
 JOURNAL = {SIAM Journal on Computing},
 PUBLISHER = {SIAM},
 YEAR = {2005},
 NUMBER = {6},
 VOLUME = {34},
 PAGES = {1443--1463},
 ADDRESS = {Philadelphia, USA},
}

Entry last modified by Christine Kiesel, 09/08/2006
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/27/2006 10:14:45
Revisions
4.
3.
2.
1.
0.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
08.09.2006 09:16:09
06.07.2006 09:08:53
19.06.2006 10:35:04
19.06.2006 10:18:53
01/27/2006 10:14:45 AM