An Architecture for Bitonic Sorting with Optimal VLSI Performnance
- 1 July 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (7) , 646-651
- https://doi.org/10.1109/tc.1984.5009338
Abstract
We propose a class of designs of a new interconnection network, the pleated cube-connected cycles (PCCC), which can impleement stable bitonic sorting of n records of size q in area A = O(q2n2/T2), where T, the computation time, is in the range [Ω(q log2 n), O(q √n/(q+ log n))]. Thus, this network is an AT2,/R-optimal bitonic sorter in the synchronous VLSI model of computation under the word-local restriction.Keywords
This publication has 5 references indexed in Scilit:
- An asymptotically optimal layout for the shuffle—exchange graphJournal of Computer and System Sciences, 1983
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971