Duality between Prefetching and Queued Writing with Parallel Disks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001

AUTHORS

David A. Hutchinson , Peter Sanders , Jeffrey Scott Vitter

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. More... »

PAGES

62-73

Book

TITLE

Algorithms — ESA 2001

ISBN

978-3-540-42493-2
978-3-540-44676-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44676-1_5

DOI

http://dx.doi.org/10.1007/3-540-44676-1_5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1028937373


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, Durham, NC, 27708-0129"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hutchinson", 
        "givenName": "David A.", 
        "id": "sg:person.010524541157.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010524541157.97"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Society", 
          "id": "https://www.grid.ac/institutes/grid.4372.2", 
          "name": [
            "Max-Planck-Institute for Computer Science, Stuhlsatzenhausweg 85, 66123\u00a0Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sanders", 
        "givenName": "Peter", 
        "id": "sg:person.016457635157.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016457635157.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, Durham, NC, 27708-0129"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/48529.48535", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014013712"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-8191(97)00015-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023784729"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01185207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045195394", 
          "https://doi.org/10.1007/bf01185207"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01185207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045195394", 
          "https://doi.org/10.1007/bf01185207"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539797326976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880213"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/sj.52.0078", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063185080"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "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.", 
    "editor": [
      {
        "familyName": "auf der Heide", 
        "givenName": "Friedhelm Meyer", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44676-1_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3468508", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3469763", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3012024", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3742908", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-42493-2", 
        "978-3-540-44676-7"
      ], 
      "name": "Algorithms \u2014 ESA 2001", 
      "type": "Book"
    }, 
    "name": "Duality between Prefetching and Queued Writing with Parallel Disks", 
    "pagination": "62-73", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44676-1_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "89d98d8043b767af55232043fb969553bb483fc12155643a92ff82710a7956d2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028937373"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44676-1_5", 
      "https://app.dimensions.ai/details/publication/pub.1028937373"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8697_00000261.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44676-1_5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-44676-1_5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-44676-1_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44676-1_5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44676-1_5'


 

This table displays all metadata directly associated to this object as RDF triples.

106 TRIPLES      23 PREDICATES      32 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44676-1_5 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N0fa5a4ff1b0c409f9cbcd1be3e347ce1
4 schema:citation sg:pub.10.1007/bf01185207
5 https://doi.org/10.1016/s0167-8191(97)00015-x
6 https://doi.org/10.1137/s0097539797326976
7 https://doi.org/10.1145/48529.48535
8 https://doi.org/10.1147/sj.52.0078
9 schema:datePublished 2001
10 schema:datePublishedReg 2001-01-01
11 schema:description 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.
12 schema:editor N450b3d44439144eabd0dfc306a52ebe1
13 schema:genre chapter
14 schema:inLanguage en
15 schema:isAccessibleForFree true
16 schema:isPartOf Nb0c7e07fa3a444768fe15e994cf5553b
17 schema:name Duality between Prefetching and Queued Writing with Parallel Disks
18 schema:pagination 62-73
19 schema:productId N3c518efc230e429c947c813290931e3f
20 Nb71bc57f41374ede9adc5fcb11c02f06
21 Nb9c2339efb8d4353adaa593a08497531
22 schema:publisher N00246ceb2ee044a8a0c68533196a09d2
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028937373
24 https://doi.org/10.1007/3-540-44676-1_5
25 schema:sdDatePublished 2019-04-15T23:52
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher N9fbf16e20538429e92a8d0ed44dd8096
28 schema:url http://link.springer.com/10.1007/3-540-44676-1_5
29 sgo:license sg:explorer/license/
30 sgo:sdDataset chapters
31 rdf:type schema:Chapter
32 N00246ceb2ee044a8a0c68533196a09d2 schema:location Berlin, Heidelberg
33 schema:name Springer Berlin Heidelberg
34 rdf:type schema:Organisation
35 N0fa5a4ff1b0c409f9cbcd1be3e347ce1 rdf:first sg:person.010524541157.97
36 rdf:rest Ncf043a4368b449b195123a0560e15a03
37 N3c518efc230e429c947c813290931e3f schema:name doi
38 schema:value 10.1007/3-540-44676-1_5
39 rdf:type schema:PropertyValue
40 N450b3d44439144eabd0dfc306a52ebe1 rdf:first Nb2efffd810ed42e1aa2a636b54648db1
41 rdf:rest rdf:nil
42 N9fbf16e20538429e92a8d0ed44dd8096 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 Nb0c7e07fa3a444768fe15e994cf5553b schema:isbn 978-3-540-42493-2
45 978-3-540-44676-7
46 schema:name Algorithms — ESA 2001
47 rdf:type schema:Book
48 Nb2efffd810ed42e1aa2a636b54648db1 schema:familyName auf der Heide
49 schema:givenName Friedhelm Meyer
50 rdf:type schema:Person
51 Nb71bc57f41374ede9adc5fcb11c02f06 schema:name readcube_id
52 schema:value 89d98d8043b767af55232043fb969553bb483fc12155643a92ff82710a7956d2
53 rdf:type schema:PropertyValue
54 Nb9c2339efb8d4353adaa593a08497531 schema:name dimensions_id
55 schema:value pub.1028937373
56 rdf:type schema:PropertyValue
57 Ncf043a4368b449b195123a0560e15a03 rdf:first sg:person.016457635157.18
58 rdf:rest Nfd3517a969704cf583018e2a89907668
59 Nfd3517a969704cf583018e2a89907668 rdf:first sg:person.0613677314.28
60 rdf:rest rdf:nil
61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
62 schema:name Information and Computing Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
65 schema:name Artificial Intelligence and Image Processing
66 rdf:type schema:DefinedTerm
67 sg:grant.3012024 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-44676-1_5
68 rdf:type schema:MonetaryGrant
69 sg:grant.3468508 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-44676-1_5
70 rdf:type schema:MonetaryGrant
71 sg:grant.3469763 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-44676-1_5
72 rdf:type schema:MonetaryGrant
73 sg:grant.3742908 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-44676-1_5
74 rdf:type schema:MonetaryGrant
75 sg:person.010524541157.97 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
76 schema:familyName Hutchinson
77 schema:givenName David A.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010524541157.97
79 rdf:type schema:Person
80 sg:person.016457635157.18 schema:affiliation https://www.grid.ac/institutes/grid.4372.2
81 schema:familyName Sanders
82 schema:givenName Peter
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016457635157.18
84 rdf:type schema:Person
85 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
86 schema:familyName Vitter
87 schema:givenName Jeffrey Scott
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
89 rdf:type schema:Person
90 sg:pub.10.1007/bf01185207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045195394
91 https://doi.org/10.1007/bf01185207
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1016/s0167-8191(97)00015-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023784729
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1137/s0097539797326976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880213
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1147/sj.52.0078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063185080
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
102 schema:name Department of Computer Science, Duke University, Durham, NC, 27708-0129
103 rdf:type schema:Organization
104 https://www.grid.ac/institutes/grid.4372.2 schema:alternateName Max Planck Society
105 schema:name Max-Planck-Institute for Computer Science, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany
106 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...