Work-preserving emulations of fixed-connection networks

ABSTRACT

In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is &Ogr;(TGNG/NH) because then both the guest and host networks perform the same total work, &THgr;(TGNG), to within a constant factor. We say that an emulation is real-time if TH = &Ogr;(TG), because then the host emulates the guest with constant delay. Although many isolated emulation results have been proved for specific networks in the past, and measures such as dilation and congestion were known to be important, the field has lacked a model within which general results and meaningful lower bounds can be proved. We attempt to provide such a model, along with corresponding general techniques and specific results in this paper. 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 mesh can be emulated in real time in a work-preserving fashion on a butterfly, even though any &Ogr;(1)-to-1 embedding of a mesh in a butterfly has dilation &OHgr;(log N), a proof that an N log N-node butterfly can be emulated in a work-preserving fashion on an N-node shuffle-exchange graph, and vice-versa, simple &Ogr;(N2/log2 N)-area and &Ogr;(N3/2/log3/2 N)-volume layouts for the N-node shuffle-exchange graph, and an algorithm for sorting N-numbers in &Ogr;(log N) steps with high probability on an N-node shuffle-exchange graph with constant size queues.

REFERENCES

• 1: V. E. Benes, "Optimal rearrangeable multistage connecting networks," Bell System Technical Journal, Vol. 43, July 1964, pp. 1641-1656.
• 2: Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62229]
• 3: S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, "Optima} simulations of tree machines.'' Proceedings of the 27lh Annual Symposifim on Foundations of Computer Science, IEEE, October 1986, pp. 274-282.
• 4: S. N. Bhatt and I. Ipsen, Embedding Trees in the Hypercube, Yale Univ. Report RR-443.
• 5: D. S. Greenberg, L. S. Heath, and A. L. Rosenberg, "Optimal embeddings of the FFT graph in the hypercube," unpublished manuscript.
• 6: D. Hoey and C. E. Leiserson, "A layout for the shuffle-exchange network," Proceedings of the 1980 International Conference on Parallel Processing, IEEE, August 1980, pp. 329-336.
• 7: Daniel Kleitman , Frank Thomson Leighton , Margaret Lepley , Gary L. Miller, New layouts for the shuffle-exchange graph(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.278-292, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802480]
• 8: C. P. Kruskal, L. Rudolph, and M. Snir, "A complexity theory of efficient parallel algorithms," unpublished manuscript.
• 9: Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
• 10: Frank Thomson Leighton , Margaret Lepley , Gary L. Miller, Layouts for the shuffle-exchange graph based on the complex plane diagram, SIAM Journal on Algebraic and Discrete Methods, v.5 n.2, p.202-215, June 1984 [doi>10.1137/0605021]
• 11: T. Leighton, B. Maggs, and S. Rao, "Universal packet routing algorithms," Proceedings of lhe 29th Annual Symposium on Foundations of Computer Science, IEEE, October 1988, pp. 256-271.
• 12: F. T. Leighton and G. L. Miller, "Optimal layouts for small shuffle-exchange graphs," VL$I 81- Very Large Scale Integration, ed. J. Gray, Academic Press, London, 1981, pp. 289-299.
• 13: Friedhelm Meyer auf der Heide, Efficient simulations among several models of parallel computers, SIAM Journal on Computing, v.15 n.1, p.106-119, Feb. 1986 [doi>10.1137/0215008]
• 14: Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
• 15: N. Pippenger, "Parallel communication with limited buffers," Proceedings of the 25th Annual Symposium on Foundations of Computer Science, iEEE, October 1984, pp. 127-136.
• 16: A. Raghunathan and H. Saran, "Is the shuffleexchange better than the butterfly?," unpublished manuscript.
• 17: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
• 18: M. Sekanina, "On an ordering of the set of vertices of a connected graph," Pub. Faculty of $ci. Univ. Brno, Czechoslovakia, No. 412, 1960, pp. 137-142.
• 19: D. Steinberg and M. Rodeh, "A layout for the shuffle~exchange network with O(N2/loga/2N) area", IEEE Transaclions on Computers, Vol. C- 30, No. 12, December 1981, pp. 977-982.
• 20: D. S. Wise, "Compact layouts of banyan/FFT networks," VL$I Systems and Computations, H. T. Kung, B. Sproull and G. Steele, eds., 1981, pp. 186-195.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory