Permutation Admissibility in Shuffle-Exchange Networks with Arbitrary Number of Stages

The set of input-output permutations that are routable through a multistage interconnection network without any conflict (known as the admissible set), plays an important role in determining the capability of the network. Recent works on the permutation admissibity problem of shuffleexchange networks (SEN) of size N \Theta N , deal with (n + k) stages, where n = log2N , and k denotes the number of extra stages. For k = 0 or 1, O(Nn) algorithms exist to check if any permutation is admissible, but for k 2, a polynomial time solution is not yet known. The more general problem of finding the minimum number (m) of shuffleexchange stages required to realize an arbitrary permutation, 1 m 2n \Gamma 1, is also an open problem. In this paper, we present an O(Nn) algorithm that checks whether a given permutation P is admissible in an m stage SEN, 1 m n, and determines in O(Nnlogn) time the minimum number of stages m of shuffle-exchange, required to realize P . Thus, a single-stage shuffle-..