Journal of the ACM Bibliography

Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, F. Thomson Leighton, Bojana Obreni\'c, Arnold L. Rosenberg, and Eric J. Schwabe. Optimal emulations by butterfly-like networks. Journal of the ACM, 43(2):293-330, March 1996. [BibTeX entry]
Abstract

The power of butterfly-like networks as multicomputer interconnection networks is studied, by considering how efficiently the butterfly can emulate other networks. Emulations are studied formally via graph embeddings, so the topic here becomes: How efficiently can one embed the graph underlying a given interconnection network in the graph underlying the butterfly network? Within this framework, the slowdown incurred by an emulation is measured by the sum of the dilation and the congestion of the corresponding embedding (respectively, the maximum amount that the embedding stretches an edge of the guest graph, and the maximum traffic across any edge of the host graph); the efficiency of resource utilization in an emulation is measured by the expansion of the corresponding embedding (the ratio of the sizes of the host to guest graph).

Three main results expose a number of optimal emulations by butterfly networks. Call a family of graphs balanced if complete binary trees can be embedded in the family with simultaneous dilation, congestion, and expansion O(1).

  1. The family of butterfly graphs is balanced.
    1. Any graph G from a family of maxdegree-d graphs having a recursive separator of size S(x) can be embedded in any balanced graph family with simultaneous dilation O(log (d \sum_i S(2^{-i}|G|))) and expansion O(1).
    2. Any dilation-D embedding of a maxdegree-d graph in a butterfly graph can be converted to an embedding having simultaneous dilation O(D) and congestion O(dD).
  2. Any embedding of a planar graph G in a butterfly graph must have dilation Omega((log Sigma(G))/(Phi(G))), where: Sigma(G) is the size of the smallest (1/3, 2/3)-node-separator of G, and Phi(G) is the size of G's largest interior face.
Applications of these results include:
  1. The n-node X-tree network can be emulated by the butterfly network with slowdown O(log log n) and expansion O(1); no embedding has dilation smaller than Omega(log log n), independent of expansion.
  2. Every embedding of the n by n mesh in the butterfly graph has dilation Omega(log n); any expansion-O(1) embedding in the butterfly graph achieves dilation O(log n).
These applications provide the first examples of networks that can be embedded more efficiently in hypercubes than in butterflies.

We also show that analogues of these results hold for networks that are structurally related to the butterfly network. The upper bounds hold for the hypercube and the de Bruijn networks, possibly with altered constants. The lower bounds hold -- at least in weakened form -- for the de Bruijn network.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors) -- interconnection architectures; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- Computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms

General Terms: Algorithms, Design, Theory

Additional Key Words and Phrases: Embeddings, emulations, mapping algorithms, mapping problems, parallel architectures, processor arrays

Selected papers that cite this one

Selected references


Shortcuts:

  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database