Communication-efficient parallel algorithms for distributed random-access machines
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 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(lg^ 2 n)\)-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.
- Publication:4942231
- Efficient Schemes for Parallel Communication
- scientific article; zbMATH DE number 1333604
- Parallel-algorithm communication operations generated by uniform dependences
- Parallel Talbot's algorithm for distributed memory machines
- Parallelization of sequential programs: distribution of arrays among processors and structurization of communications
- Algorithms for the parallel alternating direction access machine
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A Regular Layout for Parallel Adders
- A Scheme for Fast Parallel Communication
- A Separator Theorem for Planar Graphs
- An O(logn) parallel connectivity algorithm
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3628373 (Why is no real title available?)
- scientific article; zbMATH DE number 3214539 (Why is no real title available?)
- Parallel Prefix Computation
- The Parallel Evaluation of General Arithmetic Expressions
- Three-Dimensional Circuit Layouts
- Efficient delay routing
- More general parallel tree contraction: Register allocation and broadcasting in a tree
- Methods for message routing in parallel machines
- Data independence of read, write, and control structures in PRAM computations
- Parallel algorithms for tree accumulations
- A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
- Improving multicut in directed trees by upgrading nodes
- UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS
- Randomized parallel communications on an extension of the omega network
- scientific article; zbMATH DE number 4035123 (Why is no real title available?)
- Performance analysis of wormhole routed k-ary n-trees
- Parallelism in random access machines
- COMMUNICATION BALANCING IN THE PARALLEL GÖTTFERT ALGORITHM
- The power of multimedia: Combining point-to-point and multi-access networks
- More general parallel tree contraction: register allocation and broadcasting in a tree
- Communication complexity of PRAMs
This page was built for publication: Communication-efficient parallel algorithms for distributed random-access machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104096)
