A Self-Routing Benes Network and Parallel Permutation Algorithms

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

118 Scopus citations

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/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
VolumeC-30
Issue number5
DOIs
StatePublished - May 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

Cite this