Greenberg, David S. and Bhatt, Sandeep N. (1990) Routing multiple paths in hypercubes. In: SPAA '90 Proceedings of the second annual ACM symposium on Parallel algorithms and architectures. ACM , New York, NY, pp. 45-54. ISBN 0-89791-370-1. https://resolver.caltech.edu/CaltechAUTHORS:20161027-132750508
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161027-132750508
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.
Item Type: | Book Section | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||
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. | ||||||||||
Funders: |
| ||||||||||
DOI: | 10.1145/97444.97457 | ||||||||||
Record Number: | CaltechAUTHORS:20161027-132750508 | ||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20161027-132750508 | ||||||||||
Official Citation: | D. Greenberg and S. Bhatt. 1990. Routing multiple paths in hypercubes. In Proceedings of the second annual ACM symposium on Parallel algorithms and architectures (SPAA '90). ACM, New York, NY, USA, 45-54. DOI=http://dx.doi.org/10.1145/97444.97457 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 71553 | ||||||||||
Collection: | CaltechAUTHORS | ||||||||||
Deposited By: | Kristin Buxton | ||||||||||
Deposited On: | 27 Oct 2016 20:45 | ||||||||||
Last Modified: | 11 Nov 2021 04:47 |
Repository Staff Only: item control page