Rearrangeability of Multistage Shuffle/Exchange Networks

Abstract

In this paper, we study the rearrangeability of multistage shuffle/exchange networks. Although a theoretical lower bound of (2 log2 N - 1) stages for rearrangeability of a network with N = 2ninputs and outputs has been known, the sufficiency of (2 log2 N — 1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log2 N - 3) stages. We prove that, if (2 log2 R - 1) shuffle/exchange stages are sufficient for rearrangeability of a network with R = 2’ inputs and outputs, then, for any N > R, 3 log2 N - (r + 1) stages are sufficient for a network with N inputs and outputs. This result is established by setting some of the middle stages of the network to realize a fixed permutation and showing the reduced network to be topologically equivalent to a member of the Benes class of rearrangeable networks. We first characterize equivalence to Benes networks in set-theoretic terms and use this to prove equivalence of the reduced shuffle/ exchange network to the Benes network. From the known result that five stages are sufficient for rearrangeability when N = 8, we obtain an upper bound of (3 log2 N — 4) stages for rearrangeability when N > 8. Further, any increase in the network size R for which the rearrangeability of (2 log2 R — 1) stages could be shown, results in a corresponding improvement in the upper bound for all N > R. In addition, due to the one-to-one correspondence that exists between the switches in the reduced shuffle/ exchange network and those in the Benes network, the former network can be controlled by the well-known looping algorithm. © 1988 IEEE