Routing multiple paths in hypercubes
- Creators
- Greenberg, David S.
- Bhatt, Sandeep N.
- Other:
- Leighton, F. T.
Abstract
We present new techniques for mapping computations onto hypercubes. Our methods speed up classical implementations of grid and tree communications by a factor of θ(n), where la is the number of hypercube dimensions. The speed-ups are the best possible. We obtain these speed-ups by mapping each edge of the guest graph onto short, edge-disjoint paths in the hypercube. These multiple-path embeddings can be used to reduce communication time for large grid-based scientific computations, to increase tolerance to link faults, and for fast routing of large messages. We also develop a general technique for deriving multiple-path embeddings from multiple-copy embeddings. Multiple-copy embeddings are one-to-one maps of independent copies of the guest graph within the hypercube. We present an efficient multiple-copy embedding of the cube-connected-cycles network within the hypercube. This embedding is used to derive efficient multiple-path embeddings of trees and butterfly networks in hypercubes.
Additional Information
© 1990 ACM. Charles Leiserson helped simplify an earlier, and weaker, version of Theorem 1. We thank him for his suggestions. We thank Arny Rosenberg and Lennart Johnsson for helpful discussions and for pointing out fruitful avenues. We also thank Ajit Agrawal and Ching-Tien Ho for illuminating discussions. The authors were supported by NSF/DARPA grant CCR-8908285, NSF grant CCR-8807426, and AFOSR grant 89-0382.Additional details
- Eprint ID
- 71553
- Resolver ID
- CaltechAUTHORS:20161027-132750508
- CCR-8908285
- NSF
- CCR-8807426
- NSF
- 89-0382
- Air Force Office of Scientific Research (AFOSR)
- Defense Advanced Research Projects Agency (DARPA)
- Created
-
2016-10-27Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field