Abstract
A parallel algorithm to determine the switch settings for a Benes permutation network is developed. This algorithm can determine the switch settings for an N input/output Benes network in 0(log2N) time when a fully interconnected parallel computer with N processing elements is used. The algorithm runs in 0(N1/2) time on an N1/2 × N1/2 mesh-connected computer and 0(log4N) time on both a cube connected and a perfect shuffle computer with N processing elements. It runs in 0(k log 3N) time on cube connected and perfect shuffle computers with N1+1/k processing elements.
Original language | English (US) |
---|---|
Pages (from-to) | 148-154 |
Number of pages | 7 |
Journal | IEEE Transactions on Computers |
Volume | C-31 |
Issue number | 2 |
DOIs | |
State | Published - Feb 1982 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics
Keywords
- Benes permutation network
- complexity
- cube connected computer
- fully connected SIMD computer
- mesh-connected computer
- parallel algorithm
- perfect shuffle computer
- set-up algorithm