AbstractThe power of butterfly-like networks as multicomputer interconnection networks is studied, by considering how efficiently the butterfly can

emulateother 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, theslowdownincurred by an emulation is measured by the sum of thedilationand thecongestionof 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); theefficiency of resource utilizationin an emulation is measured by theexpansionof 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

balancedif complete binary trees can be embedded in the family with simultaneous dilation, congestion, and expansionO(1).Applications of these results include:

- The family of butterfly graphs is balanced.

- Any graph
Gfrom a family of maxdegree-dgraphs having a recursive separator of sizeS(x) can be embedded in any balanced graph family with simultaneous dilationO(log (d\sum_iS(2^{-i}|G|))) and expansionO(1).- Any dilation-
Dembedding of a maxdegree-dgraph in a butterfly graph can be converted to an embedding having simultaneous dilationO(D) and congestionO(dD).- Any embedding of a planar graph
Gin 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 ofG, and Phi(G) is the size ofG's largest interior face.These applications provide the first examples of networks that can be embedded more efficiently in hypercubes than in butterflies.

- The
n-node X-tree network can be emulated by the butterfly network with slowdownO(log logn) and expansionO(1); no embedding has dilation smaller than Omega(log logn), independent of expansion.- Every embedding of the
nbynmesh in the butterfly graph has dilation Omega(logn); any expansion-O(1) embedding in the butterfly graph achieves dilationO(logn).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

- A. Avior, T. Calamoneri, S. Even, A. Litman, and A. L. Rosenberg. A tight layout of the butterfly network. Theory of Computing Systems, 31(4):475-488, July/August 1998.

- L. S. Heath. Graph embeddings and simplicial maps. Theory of Computing Systems, 30(1):51-65, January/February 1997.

- F. Meyer auf der Heide, M. Storch, and R. Wanka. Optimal tradeoffs between size and slowdown for universal parallel networks. Theory of Computing Systems, 30(6):627-644, November/December 1997.

- Bruce M. Maggs and Eric J. Schwabe. Real-time emulations of bounded-degree networks. Information Processing Letters, 66(5):269-276, 16 June 1998.

- Bojana Obreni\'c. An approach to emulating separable graphs. Mathematical Systems Theory, 27(1):41-63, January/February 1994.

Selected references

- Alok Aggarwal. A comparative study of X-tree, pyramid and related machines. In 25th Annual Symposium on Foundations of Computer Science, pages 89-99, Singer Island, Florida, 24-26 October 1984. IEEE.

- Fred Annexstein, Marc Baumslag, and Arnold L. Rosenberg. Group action graphs and parallel architectures. SIAM Journal on Computing, 19(3):544-569, June 1990.

- Sandeep Bhatt, Fan Chung, Tom Leighton, and Arnold Rosenberg. Optimal simulations of tree machines (preliminary version). In 27th Annual Symposium on Foundations of Computer Science, pages 274-282, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.

- Sandeep N. Bhatt, Fan R. K. Chung, F. Thomson Leighton, and Arnold L. Rosenberg. Efficient embeddings of trees in hypercubes. SIAM Journal on Computing, 21(1):151-162, February 1992.

- Sandeep N. Bhatt and Frank Thomson Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28(2):300-343, April 1984.

- Mee Yee Chan. Embedding of grids into optimal hypercubes. SIAM Journal on Computing, 20(5):834-864, October 1991.

- David S. Greenberg, Lenwood S. Heath, and Arnold L. Rosenberg. Optimal embeddings of butterfly-like graphs in the hypercube. Mathematical Systems Theory, 23(1):61-77, 1990.

- Jia-Wei Hong and Arnold L. Rosenberg. Graphs that are almost binary trees. SIAM Journal on Computing, 11(2):227-242, May 1982.

- Richard Koch, Tom Leighton, Bruce Maggs, Satish Rao, and Arnold Rosenberg. Work-preserving emulations of fixed-connection networks (extended abstract). In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 227-240, Seattle, Washington, 15-17 May 1989.

- Clyde P. Kruskal and Marc Snir. A unified theory of interconnection network structure. Theoretical Computer Science, 48(1):75-94, 1986.

- Bojana Obreni\'c. An approach to emulating separable graphs. Mathematical Systems Theory, 27(1):41-63, January/February 1994.

- Franco P. Preparata and Jean Vuillemin. The cube-connected cycles: A versatile network for parallel computation. Communications of the ACM, 24(5):300-309, May 1981.