Communication-Efficient Parallel Graph Algorithms.
Abstract
Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. This thesis shows that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with efficient communication at each step of the computation. The communication requirements of an algorithm are measured in a restricted PRAM model called the distributed random-access machine (DRAM), which can be viewed as an abstraction of volume-universal networks such as fat-trees. In this model, communication cost is measured in terms of the congestion of memory accesses across cuts of the machine. It is demonstrated that the recursive doubling technique frequently used in PRAM algorithms is wasteful of communication resources, and that recursive pairing can be used to perform many of the same functions more efficiently. We generalize the prefix computation on linear lists to trees and show that these treefix computations, which can be performed in a communication-efficient fashion using a variant of the tree contraction technique of Miller and Reif, simplify many parallel graph algorithms in the literature.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1986
- Accession Number
- ADA176651
Entities
People
- Bruce M. Maggs
Organizations
- Massachusetts Institute of Technology