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 Nd06afa74fd6c4a8491930676bc6477fe
    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 N839504d2f47440d4ada6f0bae315762b
    29 Nfc3168985bdd4338b9d036b6a3f7961e
    30 sg:journal.1047644
    31 schema:name Communication-efficient parallel algorithms for distributed random-access machines
    32 schema:pagination 53-77
    33 schema:productId N8ad4c5098a4d4e3a88073c3952869ff1
    34 N9474fe0b1d2747a6b67a0628952826f2
    35 Nd7ab965b315a40f4acc919d2a226925f
    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 N5b17f2386ade43eeab668963322fabab
    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 N5b17f2386ade43eeab668963322fabab schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N839504d2f47440d4ada6f0bae315762b schema:issueNumber 1-4
    48 rdf:type schema:PublicationIssue
    49 N8ad4c5098a4d4e3a88073c3952869ff1 schema:name dimensions_id
    50 schema:value pub.1031777105
    51 rdf:type schema:PropertyValue
    52 N9474fe0b1d2747a6b67a0628952826f2 schema:name doi
    53 schema:value 10.1007/bf01762110
    54 rdf:type schema:PropertyValue
    55 Nc6e1d4340a044802baed2a762c9d1b50 rdf:first sg:person.013520454035.81
    56 rdf:rest rdf:nil
    57 Nd06afa74fd6c4a8491930676bc6477fe rdf:first sg:person.015544476571.16
    58 rdf:rest Nc6e1d4340a044802baed2a762c9d1b50
    59 Nd7ab965b315a40f4acc919d2a226925f schema:name readcube_id
    60 schema:value 97613bd8511e4c7e325e6c5b2863dfe3b3565bb4e26b291181e62ad59f559c65
    61 rdf:type schema:PropertyValue
    62 Nfc3168985bdd4338b9d036b6a3f7961e 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)


    ...