SIMD-emulations of hypercubes and related networks

This paper addresses a problem in emulation theory. The author shows how processor-array networks with simple topologies can efficiently emulate the computations of complex topologies. This is possible by trading off parallelism for time. Such emulations are advantageous since processor-array networks of simple topologies are cost-effective to build on a large-scale. The challenge is to perform these emulations optimally, without the loss of too much parallelism. The author presents emulations of generic computations programmed in a SIMD fashion which are all optimal (up to constant factors). Specifically, they present emulations of the order-n cube-connected-cycles network and the order-n shuffle-exchange network by an n-node ring-connected processor array. They also present an emulation of an order-n hypercube network by an n/log n-node linear processor array