Communication-efficient parallel algorithms for distributed random-access machines


Journal Article

This paper introduces a model for parallel computation, called the distributed 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 a conservative 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 give O(lg n)-step, linear-processor, linear-space, conservative algorithms for a variety of problems on n-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We give O(lg2n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of size n, 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 such treefix computation can be performed in O(lg n) steps using a conservative variant of Miller and Reif's tree-contraction technique. © 1988 Springer-Verlag New York Inc.

Full Text

Duke Authors

Cited Authors

  • Leiserson, CE; Maggs, BM

Published Date

  • March 1, 1988

Published In

Volume / Issue

  • 3 / 1

Start / End Page

  • 53 - 77

Electronic International Standard Serial Number (EISSN)

  • 1432-0541

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/BF01762110

Citation Source

  • Scopus