| Publications [#236672] of Bruce Maggs
Journal articles or Book chapters PUBLISHED
- Leiserson, CE; Maggs, BM, COMMUNICATION-EFFICIENT PARALLEL ALGORITHMS FOR DISTRIBUTED RANDOM-ACCESS MACHINES.,
Algorithmica (New York), vol. 38 no. 9
(January, 2003),
pp. 53-77
(last updated on 2024/04/23)
Abstract: This paper introduces a model for parallel computation, called the distributed random-assess machine (DRAM), inwhich 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 message 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.
|