**Charles E. Leiserson
Bruce M. Maggs
M.I.T. Laboratory for Computer Science
545 Technology Square
Cambridge, MA 02139**

*This paper introduces a model for parallel
computation, called the distributed random-access 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 -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 -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 steps using a conservative variant of
Miller and Reif's tree-contraction technique.
*

*
*

- 1 Introduction
- 2 The DRAM model
- 3 Conservative algorithms
- 4 List contraction
- 5 Tree contraction
- 6 Treefix computations
- 7 Graph algorithms
- 8 Conclusion
- References
- About this document ...

Thu Jul 25 19:12:36 EDT 1996