Shuffling with the Illiac and PM2I SIMD Networks

Two SIMD single-stage interconnection networks which have been proposed and studied in the literature are the Illiac type and PM2I. The ability of the Illiac and PM2I networks to perform the shuffle data permutation in an SIMD machine with N processors is examined. Two algorithms for an SIMD or multiple-SIMD machine with the PM2I network to perform the shuffle are given. One algorithm is used in the event that the SIMD machine is of the same size (in terms of number of processors) as the shuffle to be emulated. The other algorithm is used when the shuffle to be performed is of smaller size than the given machine with the PM2I network. It is proven that both algorithms require only one more network transfer than the previously published lower bound (which is log2 S for a shuffle on S elements). Using the PM2I algorithm as a basis, an algorithm for the Illiac to emulate the shuffle is given. Its performance is 2¿N - 1 transfers which is only three transfers more than the previously published lower bound of 2¿N - 4.