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), Q(TGNG), to within a constant factor. We say that an emulation occurs in real-time if TH 5 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 V(log N), and (4) simple O(N2/log2 N)-area and O(N3/ 2/log3/2 N)-volume layouts for the N-node shuffle-exchange network. Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures— parallel processors; C.2.1 [Computer-Communications Networks]: Network Analysis and Design— network topology; F.1.1 [Computation by Abstract Devices]: Models of Computation—networks of machines; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems—computations on discrete structures; G.2.1 [Discrete Mathematics]: combinatories—combinatorial algorithms; G.2.2 [Discrete Mathematics]: Graph Theory—graph algorithms General Terms: Algorithms, Design, Theor