A Self-Routing Benes Network and Parallel Permutation Algorithms
- 1 May 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (5) , 332-340
- https://doi.org/10.1109/tc.1981.1675791
Abstract
A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input utput self-routing network is O(log N). It is shown that the network is capable of performing a rich class of permutations. The self-routing scheme leads to efficient O(log N) parallel algorithms to perform the same class of permutations on cube connected and perfect shuffle computers.Keywords
This publication has 12 references indexed in Scilit:
- Parallel permutation and sorting algorithms and a new generalized connection networkJournal of the ACM, 1982
- An optimal routing algorithm for mesh-connected Parallel computersJournal of the ACM, 1980
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Generalized Connection Networks for Parallel Processor IntercommunicationIEEE Transactions on Computers, 1978
- Parallel Permutations of Data: A Benes Network Control Algorithm for Frequently Used PermutationsIEEE Transactions on Computers, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- A Shuffle-Exchange Network with Simplified ControlIEEE Transactions on Computers, 1976
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- A Permutation NetworkJournal of the ACM, 1968