COMPRESSING CUBE-CONNECTED CYCLES AND BUTTERFLY NETWORKS

We consider the simulation of large cube-connected cycles (CCC) and la rge butterfly networks (BFN) on smaller ones, a problem that arises wh en algorithms designed for an architecture of an ideal size are to be executed on an existing architecture of a fixed size. We show that lar ge CCCs and BFNs can be embedded into smaller networks of the same typ e with (a) dilation 2 and optimum load, (b) dilation 1 and optimum loa d in most cases, and (c) dilation 1 and nearly optimum load in all cas es. Our results show that large CCCs and BFNs can be simulated very ef ficiently on smaller ones. Additionally, we implemented our algorithm for compressing CCCs and ran several experiments on a Transputer netwo rk, which showed that our technique also behaves very well from a prac tical point of view. (C) 1998 John Wiley & Sons, Inc. Networks 32: 47- 65, 1998.