Classifying and counting the permutations passable by the extra-stage shuffle/exchange interconnection networks
Adding an extra stage to the log2N, N=2n multistage interconnection networks (MINs) will increase their combinatorial power as well as their fault-tolerance This is because of the redundant paths they provide for passing the permutations. Two approaches have appeared in the literature to compute the number of permutations passable by the extra stage multistage interconnection networks (EMINs). These approaches can be classified into two types. The first type computes the number of permutations that have conflicts at any stage of the log2N network and then counts the number of permutations the extra stage can resolve. This type is only applicable to specific cases. The second type is very interesting and general and uses a graph theoretic approach. Neither of the two approaches has classified the set of the extra permutations passable due to the extra stage nor has been extended for further stages. In this paper, we will give a general and extendible method to count and classify the number of permutations passable by the shuffle/exchange (ES/E) network. This is very useful in the delay analysis of the single S/E stage network. Besides, and due to the existence of multiple switch settings for the same permutation, one can reroute it on different paths in case of a network fault. Our approach is very natural and uses the inverse base-line network BL?1 passability condition and the bit reversal permutation connecting the extra stage and the network.
permutations ins shuffle exchange performance evaluation