Dynamic Embedding of Trees in Hypercubes with Constant Dilation and Load
Abstract
Parallel computations often yield computation structures which are trees; the shape of such a tree evolves over time as the computation progresses. However, parallel computers are usually designed as networks of processors with fixed connections; it is therefore important to embed the dynamic structure of a computation efficiently in a fixed network. We consider the problem of dynamically embedding an evolving binary tree with at most N nodes in an N-node hypercube. We present a simple randomized algorithm which uses only local control and guarantees constant dilation, while maintaining constant load with high probability; this is the first load-balancing algorithm which achieves constant dilation. We also prove that random solutions to this problem are highly desirable, by demonstrating that any deterministic embedding algorithm which maintains constant load must have omega (square root of log N) dilation.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA211884
Entities
People
- Eric Schwabe
- M. E. J. Newman
- Tom Leighton
Organizations
- Massachusetts Institute of Technology