A New Interconnection Network for SIMD Computers: The Sigma Network

When processing vectors on SIMD computers, some data manipulations (rearrangement, expansion, compression, perfect-shuffle, bit-reversal) have to be performed by an interconnection network. When this network lacks an efficient routing control, it becomes the bottleneck for performance. It has been pointed out that general algorithms to control rearrangeable networks for arbitrary permutations are time consuming. To overcome this difficulty, Lenfant [9] proposed a set of permutations covering standard needs associated with efficient control algorithms for the Benes network. But to perform explicit permutations on vectors, several passes through the network are necessary because they have to be composed with transfer rearrangements. We present efficient control algorithms to perform these vector permutations in a single pass on a new interconnection network.