WORK-PRESERVING EMULATIONS OF FIXED-CONNECTION NETWORKS

In this paper, we study the problem of emulating T-G steps of an N-G-n ode guest network, G, on an N-H-node host network, H. We call an emula tion work-preserving if the time required by the host, T-H, is O(TGNG/ N-H), because then both the guest and host networks perform the same t otal work (i.e., processor-time product), Theta(TGNG), to within a con stant 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 emula tions, we also provide a general model in which lower bounds can be pr oved. Some of the more interesting and diverse consequences of this wo rk 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 rea l-time work-preserving fashion, and vice versa, (3) a proof that a but terfly 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 em bedding of an N-node mesh in an N-node butterfly has dilation Omega(lo g N), and (4) simple O(N-2/log(2) N)-area and O(N-3/2/log(3/2) N)-volu me layouts for the N-node shuffle-exchange network.