A Uniform Representation of Single-and Multistage Interconnection Networks Used in SIMD Machines

A switching theoretic framework for the study of interconnection networks is developed. An equivalence relationship between networks is defined. Single-stage and multistage networks that are particularly useful for single-instruction multiple-data stream (SIMD) machines are studied. It is shown that the networks form two distinct equivalence classes under this definition of equivalence relationship. It is shown that any multistage network can be easily modified to realize the permutations that are admissible by any other network which is equivalent to it.