Parallel permutation and sorting algorithms and a new generalized connection network

David Nassimi; Sartaj Sahni

doi:10.1145/322326.322329

Parallel permutation and sorting algorithms and a new generalized connection network

David Nassimi, Sartaj Sahni

Research output: Contribution to journal › Article › peer-review

128 Scopus citations

Abstract

O(k log N) algonthms are obtained to permute and sort N data items on cube and perfect shuffle computers with N^1+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(kN^1+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 N^1+1/h processing elements.

Original language	English (US)
Pages (from-to)	642-667
Number of pages	26
Journal	Journal of the ACM (JACM)
Volume	29
Issue number	3
DOIs	https://doi.org/10.1145/322326.322329
State	Published - Jul 1 1982
Externally published	Yes

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

Access to Document

10.1145/322326.322329

Cite this

@article{66d550d8927242a4ab048faf389adc6b,

title = "Parallel permutation and sorting algorithms and a new generalized connection network",

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.",

keywords = "Permutauon, cube computer, generalized connection network, perfect shuffle computer",

author = "David Nassimi and Sartaj Sahni",

year = "1982",

month = jul,

day = "1",

doi = "10.1145/322326.322329",

language = "English (US)",

volume = "29",

pages = "642--667",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Parallel permutation and sorting algorithms and a new generalized connection network

AU - Nassimi, David

AU - Sahni, Sartaj

PY - 1982/7/1

Y1 - 1982/7/1

N2 - 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.

AB - 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.

KW - Permutauon

KW - cube computer

KW - generalized connection network

KW - perfect shuffle computer

UR - http://www.scopus.com/inward/record.url?scp=0020157164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020157164&partnerID=8YFLogxK

U2 - 10.1145/322326.322329

DO - 10.1145/322326.322329

M3 - Article

AN - SCOPUS:0020157164

SN - 0004-5411

VL - 29

SP - 642

EP - 667

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 3

ER -

Parallel permutation and sorting algorithms and a new generalized connection network

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this