Routing multiple paths in hypercubes

David S. Greenberg, Sandeep Bhatt

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 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.

Original languageEnglish (US)
Pages (from-to)295-321
Number of pages27
JournalMathematical Systems Theory
Volume24
Issue number1
DOIs
StatePublished - Dec 1 1991
Externally publishedYes

Fingerprint

Hypercube
Routing
Path
Communication
Grid
Edge-disjoint Paths
Graph in graph theory
Congestion
Regular hexahedron
Tolerance
Speedup
Fault
Cycle

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics

Cite this

Greenberg, David S. ; Bhatt, Sandeep. / Routing multiple paths in hypercubes. In: Mathematical Systems Theory. 1991 ; Vol. 24, No. 1. pp. 295-321.
@article{fc3914649a994d2aba72a1caf801b2c3,
title = "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 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.",
author = "Greenberg, {David S.} and Sandeep Bhatt",
year = "1991",
month = "12",
day = "1",
doi = "https://doi.org/10.1007/BF02090404",
language = "English (US)",
volume = "24",
pages = "295--321",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York",
number = "1",

}

Routing multiple paths in hypercubes. / Greenberg, David S.; Bhatt, Sandeep.

In: Mathematical Systems Theory, Vol. 24, No. 1, 01.12.1991, p. 295-321.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Routing multiple paths in hypercubes

AU - Greenberg, David S.

AU - Bhatt, Sandeep

PY - 1991/12/1

Y1 - 1991/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34249918639&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249918639&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/BF02090404

DO - https://doi.org/10.1007/BF02090404

M3 - Article

VL - 24

SP - 295

EP - 321

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 1

ER -