Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks
- 1 July 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (7) , 591-601
- https://doi.org/10.1109/tc.1986.1676800
Abstract
In this paper, we present a new model, finite permutation machine (FPM), to describe the permutation networks. A set of theorems are developed to capture the theory of operations for the permutation networks. Using this new framework, an interesting problem is attacked: are 2n − 1 passes of shuffle exchange necessary and sufficient to realize all permutations? where n = log2 N and N is the number of inputs and outputs interconnected by the network. We prove that to realize all permutations, 2n − 1 passes of shuffle exchange are necessary and that 3n − 3 passes are sufficient. This reduces the sufficient number of passes by 2 from the best-known result.Keywords
This publication has 15 references indexed in Scilit:
- The Universality of the Shuffle-Exchange NetworkIEEE Transactions on Computers, 1981
- The Reverse-Exchange Interconnection NetworkIEEE Transactions on Computers, 1980
- A Uniform Representation of Single-and Multistage Interconnection Networks Used in SIMD MachinesIEEE Transactions on Computers, 1980
- On a Class of Multistage Interconnection NetworksIEEE Transactions on Computers, 1980
- Notes on Shuffle/Exchange-Type Switching NetworksIEEE Transactions on Computers, 1980
- Interconnection Networks for SIMD MachinesComputer, 1979
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- An Adaptation of the Fast Fourier Transform for Parallel ProcessingJournal of the ACM, 1968
- A Permutation NetworkJournal of the ACM, 1968