AbstractIn this paper, we study the problem of emulating T_G steps of an N_G-node guest network, G, on an N_G-node host network, H. We call an emulation work-preserving if the time required by the host, T_H, is O(T_G N_G/N_H), because then both the guest and host networks perform the same total work (i.e., processor-time product), Theta(T_G N_G), to within a constant factor. We say that an emulation occurs in real-time if T_H = O(T_G), because then the host emulates the guest with constant slowdown. In addition to describing several work-preserving and real-time emulations, we also provide a general model in which lower bounds can be proved. Some of the more interesting and diverse consequences of this work include:
- a proof that a linear array can emulate a (much larger) butterfly in a work-preserving fashion, but that a butterfly cannot emulate an expander (of any size) in a work-preserving fashion,
- a proof that a butterfly can emulate a shuffle-exchange network in a real-time work-preserving fashion, and vice versa,
- a proof that a butterfly can emulate a mesh (or an array of higher, but fixed, dimension) in a real-time work-preserving fashion, even though any O(1)-to-1 embedding of an N-node mesh in an N-node butterfly has dilation Omega(log N), and
- simple O(N^2/log^2 N)-area and O(N^{3/2}/log^{3/2} N)-volume layouts for the N-node shuffle-exchange network.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Preliminary versionA preliminary version of these results was presented in: 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.
Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors) -- parallel processors; C.2.1 [Computer-Communication Networks]: Network Architecture and Design -- network topology; F.1.1 [Computation by Abstract Devices]: Models of Computation -- networks of machines; 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: Graph embeddings, network emulations, parallel architectures, processors arrays
Selected papers that cite this one
- F. Thomson Leighton, Bruce M. Maggs, and Ramesh K. Sitaraman. On the fault tolerance of some popular bounded-degree networks. SIAM Journal on Computing, 27(5):1303-1333, October 1998.
- Bruce M. Maggs, Friedhelm Meyer auf der Heide, and and Berthold Vöcking. Exploiting locality for data management in systems of limited bandwidth. In 38th Annual Symposium on Foundations of Computer Science, pages 284-293, Miami Beach, Florida, 20-22 October 1997. IEEE.
- Bruce M. Maggs and Eric J. Schwabe. Real-time emulations of bounded-degree networks. Information Processing Letters, 66(5):269-276, 16 June 1998.
Selected references
- Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, F. Thomson Leighton, and Arnold L. Rosenberg. Optimal simulations by butterfly networks (preliminary version). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 192-204, Chicago, Illinois, 2-4 May 1988.
- 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.
- 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.
- Friedhelm Meyer auf der Heide. Efficient simulations among several models of parallel computers. SIAM Journal on Computing, 15(1):106-119, February 1986.
- Friedhelm Meyer auf der Heide. Efficiency of universal parallel computers. Acta Informatica, 19:269-296, 1983.
- Daniel Kleitman, Frank Thomson Leighton, Margaret Lepley, and Gary L. Miller. New layouts for the shuffle-exchange graph (extended abstract). In Conference Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computation, pages 278-292, Milwaukee, Wisconsin, 11-13 May 1981.
- Tom Leighton, Bruce Maggs, and Satish Rao. Universal packet routing algorithms (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 256-269, White Plains, New York, 24-26 October 1988. IEEE.
- F. T. Leighton, Bruce M. Maggs, Abhiram G. Ranade, and Satish B. Rao. Randomized routing and sorting on fixed-connection networks. Journal of Algorithms, 17(1):157-205, July 1994.
- P. M. Lewis II, R. E. Stearns, and J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 191-202. IEEE, 1965.
- Christos H. Papadimitriou and Mihalis Yannakakis. Towards an architecture-independent analysis of parallel algorithms (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 510-513, Chicago, Illinois, 2-4 May 1988.
- M. S. Paterson, W. L. Ruzzo, and L. Snyder. Bounds on minimax edge length for complete binary trees (extended abstract). In Conference Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computation, pages 293-299, Milwaukee, Wisconsin, 11-13 May 1981.
- Nicholas Pippenger. Parallel communication with limited buffers (preliminary version). In 25th Annual Symposium on Foundations of Computer Science, pages 127-136, Singer Island, Florida, 24-26 October 1984. IEEE.
- John H. Reif and Leslie G. Valiant. A logarithmic time sort for linear size networks. Journal of the ACM, 34(1):60-76, January 1987.
- Abraham Waksman. Corrigendum: ``A permutation network''. Journal of the ACM, 15(2):340, April 1968.