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), where n 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 is O(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.