Matrix Techniques for Faster Routing of Affine Permutations on a MeshInterconnection Network

摘要

The problem of routing affine permutations on a SIMD MESH connected networkwithout wrap around connections is studied. An algorithm with 4.(square root of n)-4 routing steps at most is obtained. The permutation is performed by a sequence of selective bit complementations but they are no longer invertible and the two datasets reside in the same processing unit. The algorithm is optimal for some affine permutations and on average the number of routine steps is only O(1) from a lower bound.