Journal of the ACM Bibliography

Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, and Eric J. Schwabe. Work-preserving emulations of fixed-connection networks. Journal of the ACM, 44(1):104-147, January 1997. [BibTeX entry]

In 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:

  1. 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,
  2. a proof that a butterfly can emulate a shuffle-exchange network in a real-time work-preserving fashion, and vice versa,
  3. 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
  4. 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 version

A 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

Selected references


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