Graph Theoretical Analysis and Design of Multistage Interconnection Networks
- 1 July 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (7), 637-648
- https://doi.org/10.1109/tc.1983.1676295
Abstract
This paper introduces two graph theoretic models that provide a uniform procedure for analyzing 2n-input/2n-output Multistage Interconnection Networks (MIN's), implemented with 2-input/2-output Switching Elements (SE's) and satisfying a characteristics called the "buddy property." These models show that all such n-stage MIN's are topologically equivalent and hence prove that one MIN can be implemented from integrated circuits designed for another MIN. The proposed techniques also allow identical modeling and comparison of permutation capabilities of n-stage MIN's and other link-controlled networks like augmented data manipulator and SW Banyan Network and hence, allows comparison of their permutation. In the case of any conflict in the MIN, an upper bound for the required number of passes has been obtained.Keywords
This publication has 23 references indexed in Scilit:
- Design and Performance of Generalized Interconnection NetworksIEEE Transactions on Computers, 1983
- Testing and Fault Tolerance of Multistage Interconnection NetworksComputer, 1982
- Performance of Processor-Memory Interconnections for MultiprocessorsIEEE Transactions on Computers, 1981
- Analysis and Simulation of Buffered Delta NetworksIEEE Transactions on Computers, 1981
- On a Class of Multistage Interconnection NetworksIEEE Transactions on Computers, 1980
- Notes on Shuffle/Exchange-Type Switching NetworksIEEE Transactions on Computers, 1980
- A Model of SIMD Machines and a Comparison of Various Interconnection NetworksIEEE Transactions on Computers, 1979
- A Sampler of Circuit Switching NetworksComputer, 1979
- Generalized Connection Networks for Parallel Processor IntercommunicationIEEE Transactions on Computers, 1978
- Banyan networks for partitioning multiprocessor systemsPublished by Association for Computing Machinery (ACM) ,1973