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.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