Routing multiple paths in hypercubes

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), wheren is the number of hypercube dimensions. The speedups are asymptotically the best possible.We obtain these speedups by mapping each edge of the guest graph onto short, edge-disjoint paths in the hypercube such that the maximum congestion on any hypercube edge isO(1). 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.This research was supported by NSF/DARRA Grant CCR-8908285, NSF Grant CCR-8807426, and AFOSR Grant 89-0382.