Communication-efficient parallel algorithms for distributed random-access machines View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1988-11

AUTHORS

Charles E. Leiserson, Bruce M. Maggs

ABSTRACT

This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network. We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to “shortcut” pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg2n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique. More... »

PAGES

53-77

References to SciGraph publications

  • 1985-06. Computer Recreations in SCIENTIFIC AMERICAN
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "Massachusetts Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Leiserson", 
            "givenName": "Charles E.", 
            "id": "sg:person.015544476571.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015544476571.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Massachusetts Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Maggs", 
            "givenName": "Bruce M.", 
            "id": "sg:person.013520454035.81", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013520454035.81"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/28395.28397", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000963194"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/12130.12146", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004659632"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/12130.12144", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006695235"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/12130.12151", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011503507"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/7902.7903", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018353266"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aoms/1177729330", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020657190"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322217.322232", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026733562"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321812.321815", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046664876"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(82)90008-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048349711"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/scientificamerican0685-18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1056556574", 
              "https://doi.org/10.1038/scientificamerican0685-18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1982.1675982", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532726"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.6312192", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533294"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.6312198", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533300"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0136016", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062839808"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0211027", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841643"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215057", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841919"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1985.43", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086225904"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611970265", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098556619"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1988-11", 
        "datePublishedReg": "1988-11-01", 
        "description": "This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network. We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to \u201cshortcut\u201d pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg2n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01762110", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "3"
          }
        ], 
        "name": "Communication-efficient parallel algorithms for distributed random-access machines", 
        "pagination": "53-77", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "97613bd8511e4c7e325e6c5b2863dfe3b3565bb4e26b291181e62ad59f559c65"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01762110"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1031777105"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01762110", 
          "https://app.dimensions.ai/details/publication/pub.1031777105"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:55", 
        "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/0000000347_0000000347/records_89801_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01762110"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    123 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01762110 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4716edfd514d43d0aaeeaacae9891b9d
    4 schema:citation sg:pub.10.1038/scientificamerican0685-18
    5 https://doi.org/10.1016/0196-6774(82)90008-6
    6 https://doi.org/10.1109/sfcs.1985.43
    7 https://doi.org/10.1109/tc.1982.1675982
    8 https://doi.org/10.1109/tc.1985.6312192
    9 https://doi.org/10.1109/tc.1985.6312198
    10 https://doi.org/10.1137/0136016
    11 https://doi.org/10.1137/0211027
    12 https://doi.org/10.1137/0215057
    13 https://doi.org/10.1137/1.9781611970265
    14 https://doi.org/10.1145/12130.12144
    15 https://doi.org/10.1145/12130.12146
    16 https://doi.org/10.1145/12130.12151
    17 https://doi.org/10.1145/28395.28397
    18 https://doi.org/10.1145/321812.321815
    19 https://doi.org/10.1145/322217.322232
    20 https://doi.org/10.1145/7902.7903
    21 https://doi.org/10.1214/aoms/1177729330
    22 schema:datePublished 1988-11
    23 schema:datePublishedReg 1988-11-01
    24 schema:description This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network. We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to “shortcut” pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg2n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree true
    28 schema:isPartOf N9f4cee4c10b44ca3a89f982e4736c43e
    29 Na7244f9664874da5b5f04bb73dbcbaef
    30 sg:journal.1047644
    31 schema:name Communication-efficient parallel algorithms for distributed random-access machines
    32 schema:pagination 53-77
    33 schema:productId N26224de0ab2248d5a7ca099f508ec1d3
    34 N2ff565bf05ab404483c7e4e0519417c1
    35 N5d847b45eef142f7bb79ba4ceec1f026
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031777105
    37 https://doi.org/10.1007/bf01762110
    38 schema:sdDatePublished 2019-04-11T09:55
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N8161396ef2d6465f9b55289b288bd3bb
    41 schema:url http://link.springer.com/10.1007/BF01762110
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N26224de0ab2248d5a7ca099f508ec1d3 schema:name dimensions_id
    46 schema:value pub.1031777105
    47 rdf:type schema:PropertyValue
    48 N2ff565bf05ab404483c7e4e0519417c1 schema:name doi
    49 schema:value 10.1007/bf01762110
    50 rdf:type schema:PropertyValue
    51 N4716edfd514d43d0aaeeaacae9891b9d rdf:first sg:person.015544476571.16
    52 rdf:rest Na43ae7c8cbbd45b39e1e4c91eb8ed297
    53 N5d847b45eef142f7bb79ba4ceec1f026 schema:name readcube_id
    54 schema:value 97613bd8511e4c7e325e6c5b2863dfe3b3565bb4e26b291181e62ad59f559c65
    55 rdf:type schema:PropertyValue
    56 N8161396ef2d6465f9b55289b288bd3bb schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 N9f4cee4c10b44ca3a89f982e4736c43e schema:issueNumber 1-4
    59 rdf:type schema:PublicationIssue
    60 Na43ae7c8cbbd45b39e1e4c91eb8ed297 rdf:first sg:person.013520454035.81
    61 rdf:rest rdf:nil
    62 Na7244f9664874da5b5f04bb73dbcbaef schema:volumeNumber 3
    63 rdf:type schema:PublicationVolume
    64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Information and Computing Sciences
    66 rdf:type schema:DefinedTerm
    67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Computation Theory and Mathematics
    69 rdf:type schema:DefinedTerm
    70 sg:journal.1047644 schema:issn 0178-4617
    71 1432-0541
    72 schema:name Algorithmica
    73 rdf:type schema:Periodical
    74 sg:person.013520454035.81 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
    75 schema:familyName Maggs
    76 schema:givenName Bruce M.
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013520454035.81
    78 rdf:type schema:Person
    79 sg:person.015544476571.16 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
    80 schema:familyName Leiserson
    81 schema:givenName Charles E.
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015544476571.16
    83 rdf:type schema:Person
    84 sg:pub.10.1038/scientificamerican0685-18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1056556574
    85 https://doi.org/10.1038/scientificamerican0685-18
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1016/0196-6774(82)90008-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048349711
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1109/sfcs.1985.43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086225904
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/tc.1982.1675982 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532726
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1109/tc.1985.6312192 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533294
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1109/tc.1985.6312198 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533300
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1137/0136016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839808
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1137/0211027 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841643
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1137/0215057 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841919
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/1.9781611970265 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098556619
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/12130.12144 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006695235
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1145/12130.12146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004659632
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/12130.12151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011503507
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1145/28395.28397 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000963194
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/321812.321815 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046664876
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/322217.322232 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026733562
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/7902.7903 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018353266
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1214/aoms/1177729330 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020657190
    120 rdf:type schema:CreativeWork
    121 https://www.grid.ac/institutes/grid.116068.8 schema:alternateName Massachusetts Institute of Technology
    122 schema:name Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA
    123 rdf:type schema:Organization
     




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


    ...