Parallel algorithms to set up the benes permutation network

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

116 Scopus citations

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 languageEnglish (US)
Pages (from-to)148-154
Number of pages7
JournalIEEE Transactions on Computers
VolumeC-31
Issue number2
DOIs
StatePublished - Feb 1982
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Parallel algorithms to set up the benes permutation network'. Together they form a unique fingerprint.

Cite this