CaltechAUTHORS
  A Caltech Library Service

Routing multiple paths in hypercubes

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:
URLURL TypeDescription
http://dx.doi.org/10.1145/97444.97457DOIPaper
http://dl.acm.org/citation.cfm?doid=97444.97457PublisherPaper
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:
Funding AgencyGrant Number
NSFCCR-8908285
NSFCCR-8807426
Air Force Office of Scientific Research (AFOSR)89-0382
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
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:03 Oct 2019 16:08

Repository Staff Only: item control page