Tight Bounds on the Complexity of Parallel Sorting
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 344-354
- https://doi.org/10.1109/tc.1985.5009385
Abstract
In this paper, we prove tight upper and lower bounds on the number of processors, information transfer, wire area, and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) the construction of an N-node degree-3 network capable of sorting N numbers in O(log N) word steps; 2) a proof that any network capable of sorting N (7 log N)-bit numbers in T bit steps requires area A where AT2 = Ω(N2 log2 N); and 3) the construction of a ``small-constant-factor'' bounded-degree network that sorts N Θ(log N)-bit numbers in T = Θ(log N) bit steps with A = Θ(N2) area.Keywords
This publication has 18 references indexed in Scilit:
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- A Minimum Area VLSI Network for O(log n) Time SortingIEEE Transactions on Computers, 1985
- The VLSI optimality of the aks sorting networkInformation Processing Letters, 1985
- New lower bound techniques for VLSITheory of Computing Systems, 1984
- An Architecture for Bitonic Sorting with Optimal VLSI PerformnanceIEEE Transactions on Computers, 1984
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- Sorting and Merging in RoundsSIAM Journal on Algebraic Discrete Methods, 1982
- Universal schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1981
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979
- Optimal Sorting Algorithms for Parallel ComputersIEEE Transactions on Computers, 1978