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

摘要

A switching theoretic framework for the study of interconnection networks is developed. An equivalence relationship between networks id defined. Single stage and multi-stage networks that are particularly useful for single instructions 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 multi-stage network can be easily modified to realize the permutations that are admissable by any other network which is equivalent to it. (Author)