A New Perspective for Rearrangeability of MINs

Communication in systems with a high number of processors strongly relies on the interconnection network used, and on its capability of realizing all possible permutations. Scalability and self routing capability are two key factors for the communication structure, and Multistage Interconnection Networks (MINs) have both these features. In this paper, we show how to prove the rearrangeability of two (2logN -1)-stage MINs of size N=16, namely the Shuffle-Shuffle and the Double Butterfly, starting from the approach described in cite{RaghavendraVarma1987} for the Shuffle-Shuffle of size N=8. Our method generalizes the properties so that they hold for networks of size N=16, and opens the way to a further possible generalization for other topologies. Furthermore, we propose a backtracking algorithm for distributing the inputs over the switches of the central stage of the network, that can be applied to any network topology if properties to choose pairs of inputs arriving to switches of the central stage are suitably designed.