An Efficient Routing Algorithm for Realizing Linear Permutations on pt-Shuffle-Exchange Networks

This paper presents an efficient routing algorithm for realizing any permutation in LIN (linear-permutation-class) on single stage shuffle-exchange networks with k x k switching elements, where k = p is a prime number. For any positive integer number n there are N kn processors connected by the network. The proposed algorithm can realize LIN in 2n — 1 passes; it can be implemented by using Nn processors in O(n) time. It can also be extended to the shuffle-exchange networks with (pt xpt) switching elements, where t is a positive integer number. In addition, the routing of any arbitrary permutations on the networks with any integer k 2 is discussed. Further, by using the techniques developed in this paper, we present an optimal O(log n) parallel algorithm for solving a set of linear equations with a nonsingular coefficient matrix when the arithmetic is over the finite field GF(pt).