- 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.

**Back to other
publications**

**Back to my home page**