Algorithms for parallel memory, I: Two-level memories View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-09

AUTHORS

J. S. Vitter, E. A. M. Shriver

ABSTRACT

We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than ι times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size. More... »

PAGES

110-147

References to SciGraph publications

  • 1972. Permuting Information in Idealized Two-Level Storage in COMPLEXITY OF COMPUTER COMPUTATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01185207

    DOI

    http://dx.doi.org/10.1007/bf01185207

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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, Box 90129, 27708-0129, Durham, NC, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vitter", 
            "givenName": "J. S.", 
            "id": "sg:person.0613677314.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Courant Institute of Mathematical Sciences", 
              "id": "https://www.grid.ac/institutes/grid.482020.c", 
              "name": [
                "Courant Institute, New York University, 251 Mercer Street, 10012, New York, NY, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Shriver", 
            "givenName": "E. A. M.", 
            "id": "sg:person.012542265705.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012542265705.61"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0022-0000(73)80033-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005427103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/48529.48535", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014013712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/165231.165247", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028273198"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/b978-0-444-88071-0.50014-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029548357"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040405414", 
              "https://doi.org/10.1007/978-1-4684-2001-2_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(79)90044-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049707404"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/t-c.1971.223205", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061455418"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1981.1675790", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532562"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.1676565", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.1676584", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.5009385", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533266"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1994-09", 
        "datePublishedReg": "1994-09-01", 
        "description": "We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than \u03b9 times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01185207", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2-3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "12"
          }
        ], 
        "name": "Algorithms for parallel memory, I: Two-level memories", 
        "pagination": "110-147", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d747fa5bdf4579c89f85d81ab50a7cd453d8dc210da653bdd688aa7f9b0a3bc3"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01185207"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045195394"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01185207", 
          "https://app.dimensions.ai/details/publication/pub.1045195394"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:34", 
        "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/0000000370_0000000370/records_46769_00000002.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01185207"
      }
    ]
     

    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/bf01185207'

    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/bf01185207'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01185207'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01185207'


     

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

    105 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01185207 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N05633933ae934243b1b635e7d4f49322
    4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_10
    5 https://doi.org/10.1016/0022-0000(79)90044-8
    6 https://doi.org/10.1016/b978-0-444-88071-0.50014-x
    7 https://doi.org/10.1016/s0022-0000(73)80033-9
    8 https://doi.org/10.1109/t-c.1971.223205
    9 https://doi.org/10.1109/tc.1981.1675790
    10 https://doi.org/10.1109/tc.1985.1676565
    11 https://doi.org/10.1109/tc.1985.1676584
    12 https://doi.org/10.1109/tc.1985.5009385
    13 https://doi.org/10.1145/165231.165247
    14 https://doi.org/10.1145/48529.48535
    15 schema:datePublished 1994-09
    16 schema:datePublishedReg 1994-09-01
    17 schema:description We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than ι times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size.
    18 schema:genre research_article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N3a35be68a2f34ac0963d7b2cf09ce0b7
    22 Ne9b14f57ed18436bbcee4228d2101dd3
    23 sg:journal.1047644
    24 schema:name Algorithms for parallel memory, I: Two-level memories
    25 schema:pagination 110-147
    26 schema:productId N4dc6e6af61f343f283d162ea732e3e46
    27 N648904e4b483430ca1f05f20fb68cf89
    28 Nd5ebf2676f2342c2afe20e759c1d3e13
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045195394
    30 https://doi.org/10.1007/bf01185207
    31 schema:sdDatePublished 2019-04-11T13:34
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher N056e6b857c9e4bd4baf5bb43e911d89f
    34 schema:url http://link.springer.com/10.1007/BF01185207
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset articles
    37 rdf:type schema:ScholarlyArticle
    38 N05633933ae934243b1b635e7d4f49322 rdf:first sg:person.0613677314.28
    39 rdf:rest N058ac9ce00b348ae8ca89590bdb68513
    40 N056e6b857c9e4bd4baf5bb43e911d89f schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N058ac9ce00b348ae8ca89590bdb68513 rdf:first sg:person.012542265705.61
    43 rdf:rest rdf:nil
    44 N3a35be68a2f34ac0963d7b2cf09ce0b7 schema:volumeNumber 12
    45 rdf:type schema:PublicationVolume
    46 N4dc6e6af61f343f283d162ea732e3e46 schema:name readcube_id
    47 schema:value d747fa5bdf4579c89f85d81ab50a7cd453d8dc210da653bdd688aa7f9b0a3bc3
    48 rdf:type schema:PropertyValue
    49 N648904e4b483430ca1f05f20fb68cf89 schema:name doi
    50 schema:value 10.1007/bf01185207
    51 rdf:type schema:PropertyValue
    52 Nd5ebf2676f2342c2afe20e759c1d3e13 schema:name dimensions_id
    53 schema:value pub.1045195394
    54 rdf:type schema:PropertyValue
    55 Ne9b14f57ed18436bbcee4228d2101dd3 schema:issueNumber 2-3
    56 rdf:type schema:PublicationIssue
    57 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Information and Computing Sciences
    59 rdf:type schema:DefinedTerm
    60 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Computation Theory and Mathematics
    62 rdf:type schema:DefinedTerm
    63 sg:journal.1047644 schema:issn 0178-4617
    64 1432-0541
    65 schema:name Algorithmica
    66 rdf:type schema:Periodical
    67 sg:person.012542265705.61 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
    68 schema:familyName Shriver
    69 schema:givenName E. A. M.
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012542265705.61
    71 rdf:type schema:Person
    72 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    73 schema:familyName Vitter
    74 schema:givenName J. S.
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    76 rdf:type schema:Person
    77 sg:pub.10.1007/978-1-4684-2001-2_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040405414
    78 https://doi.org/10.1007/978-1-4684-2001-2_10
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1016/0022-0000(79)90044-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049707404
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/b978-0-444-88071-0.50014-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1029548357
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/s0022-0000(73)80033-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005427103
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1109/t-c.1971.223205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061455418
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1109/tc.1981.1675790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532562
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1109/tc.1985.1676565 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533195
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1109/tc.1985.1676584 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533210
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1109/tc.1985.5009385 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533266
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1145/165231.165247 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028273198
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
    99 rdf:type schema:CreativeWork
    100 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    101 schema:name Department of Computer Science, Duke University, Box 90129, 27708-0129, Durham, NC, USA
    102 rdf:type schema:Organization
    103 https://www.grid.ac/institutes/grid.482020.c schema:alternateName Courant Institute of Mathematical Sciences
    104 schema:name Courant Institute, New York University, 251 Mercer Street, 10012, New York, NY, USA
    105 rdf:type schema:Organization
     




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


    ...