A Self-Routing Benes Network and Parallel Permutation Algorithms

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

125 Scopus citations


A Benes permutation network capable of setting its own switches dynamically is presented. The total switch setting and delay time for the N input/output 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.

Original languageEnglish (US)
Pages (from-to)332-340
Number of pages9
JournalIEEE Transactions on Computers
Issue number5
StatePublished - May 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • Benes network
  • bit-permute-complement permutations
  • complexity
  • cube connected computer
  • inverse omega permutations
  • omega permutations
  • perfect shuffle computer


Dive into the research topics of 'A Self-Routing Benes Network and Parallel Permutation Algorithms'. Together they form a unique fingerprint.

Cite this