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 N22fca6c7b7e3412c805648fa0636aaab
    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 N48d67b7adc414afe9c605537113f95a4
    22 Nc3928adca3884b3cab01584458b0f75b
    23 sg:journal.1047644
    24 schema:name Algorithms for parallel memory, I: Two-level memories
    25 schema:pagination 110-147
    26 schema:productId N817e4eef278f4cd1ae51313ac450d461
    27 N9b2a997bfbe64a62a402dcde668bbe34
    28 Na05bbce2f43e46f6a9182876b89e4ee3
    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 Naae08957acac40eb8975aa1b9f765cca
    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 N22fca6c7b7e3412c805648fa0636aaab rdf:first sg:person.0613677314.28
    39 rdf:rest Naa6863a6be0743709da72ddb9c0e24d1
    40 N48d67b7adc414afe9c605537113f95a4 schema:issueNumber 2-3
    41 rdf:type schema:PublicationIssue
    42 N817e4eef278f4cd1ae51313ac450d461 schema:name readcube_id
    43 schema:value d747fa5bdf4579c89f85d81ab50a7cd453d8dc210da653bdd688aa7f9b0a3bc3
    44 rdf:type schema:PropertyValue
    45 N9b2a997bfbe64a62a402dcde668bbe34 schema:name doi
    46 schema:value 10.1007/bf01185207
    47 rdf:type schema:PropertyValue
    48 Na05bbce2f43e46f6a9182876b89e4ee3 schema:name dimensions_id
    49 schema:value pub.1045195394
    50 rdf:type schema:PropertyValue
    51 Naa6863a6be0743709da72ddb9c0e24d1 rdf:first sg:person.012542265705.61
    52 rdf:rest rdf:nil
    53 Naae08957acac40eb8975aa1b9f765cca schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 Nc3928adca3884b3cab01584458b0f75b schema:volumeNumber 12
    56 rdf:type schema:PublicationVolume
    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)


    ...