Journal of the Association for Computing Machinery, Vol. 43, No. 2, March 1996, pp. 293–330.

Optimal Emulations by Butterfly-Like Networks

SANDEEP N. BHATT

FAN R. K. CHUNG

JIA-WEI HONG

F. THOMSON LEIGHTON

BOJANA OBRENIĆ

ARNOLD L. ROSENBERG

AND

ERIC J. SCHWABE

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.

2. (a) 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 ∑_{i} S(2^{−i}|G|))) and expansion O(1).

(b) 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).

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.

3. Any embedding of a planar graph G in a butterfly graph must have dilation Ω (\frac{log Σ(G)}{Φ(G)}),

where: Σ(G) is the size of the smallest (1/3, 2/3)-node-separator of G, and Φ(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 Ω(log log n), independent of expansion.

2. Every embedding of the n × n mesh in the butterfly graph has dilation Ω(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.

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