Parallel permutation and sorting algorithms and a new generalized connection network

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

123 Scopus citations

Abstract

O(k log N) algonthms are obtained to permute and sort N data items on cube and perfect shuffle computers with N1+1/k processing elements, 1 ≤k ≤ log N These algorithms lead directly to a generahzedconnecuon-network construction having O(k log N) delay and O(kN1+l/klog N) contact pairs. This network has the advantage that the switches can be set m O(klog N) time by either a cube or perfect shuffle computer with N1+1/h processing elements.

Original languageEnglish (US)
Pages (from-to)642-667
Number of pages26
JournalJournal of the ACM (JACM)
Volume29
Issue number3
DOIs
StatePublished - Jul 1 1982
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Permutauon
  • cube computer
  • generalized connection network
  • perfect shuffle computer

Fingerprint

Dive into the research topics of 'Parallel permutation and sorting algorithms and a new generalized connection network'. Together they form a unique fingerprint.

Cite this