Rearrangeability of multistage shuffle/exchange networks

Although a theoretical lower bound of (2 log₂N-1) stages for rearrangeability of a network with N=2ⁿ inputs and outputs has been known, the sufficiency of (2 log₂N-1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log₂N-3) stages. It is proved that if (2 log₂R-1) shuffle/exchange stages are sufficient for rearrangeability of a network with R=2^r inputs and outputs, then for any N>R, (3 log₂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. From the known result that five stages are sufficient for rearrangeability when N ⩾8, an upper bound of (3 log₂N-4) is obtained. Any increase in the network size R for which the rearrangeability of (2 log₂R-1) stages can be shown results in corresponding improvements in the upper bound for all N ⩾R. As a result of 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