Routing multiple paths in hypercubes

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.