A New Perspective for Rearrangeability of MINs

Abstract

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 (2 log N – 1)- stage MINs of size N = 16, namely the Shuffle-Shuffle and the Double Butterfly, starting from the approach described in [1] 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.

Related Papers

• → Multistage interconnection networks reliability analysis(2016)6 cited
• New Irregular Augmented Shuffle Multistage Interconnection Network(2011)
• → Spatial Extension of Multistage Interconnection Networks(1989)2 cited
• → Mixed Preservation of Conditionally Nonblocking Switches under 2-stage Interconnection(2006)1 cited
• Evaluation and comparison of incremental permutation passable of same stage class of multistage interconnection networks(2014)