Work-preserving emulations of fixed-connection networks

In this paper, we study the problem of emulating TG steps of an NG-node guest network, G, on an NH-node host network, H. We call an emulation work-preserving if the time required by the host, TH, is O(TGNG/NH), because then both the guest and host networks perform the same total work (i.e., processor-time product), Θ(TGNG), to within a constant factor. We say that an emulation occurs in real-time if TH = O(TG), 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 Ω(log N), and (4) simple O(N²/log² N)-area and O(N^3/2/log^3/2 N)-volume layouts for the N-node shuffle-exchange network.

Duke Scholars

Author Bruce Maggs Computer Science