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