On the number of permutations performable by extra-stage multistage interconnection networks

摘要

The number of permutations performable by extra-stage multistage interconnection networks in a single pass is studied. A graph-theoretical approach is used to evaluate the multiplicity of the performable permutations. More specifically, the problem is reduced to a hypercube enumeration problem, and it is shown that there is a direct correspondence between the number of partial subgraphs of a hypercube with a given number of components, and the multiplicity of a corresponding class of permutations performable by the extra- stage network. The evaluation of these multiplicities leads to the calculation of the number of distinct permutations performable by the network.