Product-shuffle networks: Toward reconciling shuffles and butterflies (Q1199448)

Design of computers consisting of large networks of parallel processors poses a challenge as the main goal and construction parameters to be optimized in current technologies are antagonizing. In the presented paper a family of nets is investigated which can emulate certain nets of meshes and other nets of high interest thereby minimizing the increase of load of processors (nodes) and of connections (edges) and also of number of ports (connections per processor) and of transmission steps (edges per message path, dilation). As a safe base the concept of emulation of nets by nets is rigorously defined with regard to the four above mentioned parameters, so that programmes written for the original nets can efficiently both be translated and be working in the emulating net. The introduced product- shuffle nets \(P_{m,n}\) are shown as a very satisfying solution. Graph- theoretically \(P_{m,n}\) is defined as cross-product \(D_ m\times D_ n\) of two de Bruijn nets \(D\). After abstract definitions for the known families \(D_ k\) (de Bruijn), \(S_ k\) (``Shuffle Exchange'') \(C_ k\) (``Cube-Connected Cycle''), \(B_ k\) (``Butterfly''), accompanied by instructive discussion and proofs of properties and examples, the main part consists in the proof of theorems how and how good \(P_{m,n}\) emulates any of the former nets for any \(k\leq K\) (in most cases with \(K=m+n)\) and even nets of ``meshes'' \(R_{2^ m}\times R_{2^ n}\) (toroidal \(\langle\)2-dimensional\(\rangle\) lattices as product of simple cycles \(R_ k)\) and some other derived nets with mesh properties. The goodness concerns three of the parameters and in some other cases desirable properties especially area consumption in integrated circuit implementations. The proofs rely essentially on showing that the emulated nets are embeddings in \(P_{m,n}\) with small increase of transmission steps and of connection load (both with constant factor up to 4 at most) and no increase in processor load (no super-imposing of nodes). The power of \(P_{m,n}\) is shown by a theorem concerning the inverse emulation on \(D_{m+n}\) and \(B_ k\). Finally solved and unsolved questions around the investigated field are mentioned.