• Work-preserving emulations of fixed-connection networks. R. R. Koch, F. T. Leighton, B. M. Maggs, S. B. Rao, A. L. Rosenberg, and E. J. Schwabe, Journal of the ACM, Vol. 44, No. 1, January 1997, pp. 104--147.

  This paper presents several algorithms for emulating a guest network G on a host network H. It shows that an N-node butterfly network can emulate an N-node shuffle-exchange network with constant slowdown, and vice versa. It also shows that an N-node butterfly can emulate an N-node mesh with constant slowdown, even though any O(1)-to-1 embedding of a mesh in a butterfly has dilation Omega(log N). It includes a proof that a linear array can emulate a (much larger) butterfly network in a work-preserving fashion, but that a butterfly cannot emulate an expander (of any size) in a work-preserving fashion. Finally, it shows that an N-node shuffle-exchange network has a three-dimensional layout with volume O(N^{3/2}/log^{3/2}N), which is optimal. Previously no such layout was known.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page