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.>

The inherent fault tolerances of systems based on nonredundant multistage interconnection networks (MINs) is investigated. Graph models are used to describe the system, indicate faults, study their effects, and aid in mathematical formulation of these effects. Methodical terminology for defining functionality of two-sided-MIN-based multicomputer systems and specifying their fault tolerance of such systems is analyzed. The effects of a single faulty vertex and a single faulty edge are studied, and single fault tolerance, with respect to various definitions of system functionality, is evaluated. Multiple faults are analyzed. A practical example of the banyan network used in the Texas reconfigurable array computer (TRAC) and its fault tolerance capabilities are given.>