A Minimum Area VLSI Network for O(log n) Time Sorting
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 336-343
- https://doi.org/10.1109/tc.1985.5009384
Abstract
A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n2) area. The design is a typical instance of a ``hybrid architecture,'' resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT2 = Ω(n2 log2 n) lower bound for sorters of n words of length (1 + ε) log n (ε > 0).Keywords
This publication has 10 references indexed in Scilit:
- Tight Bounds on the Complexity of Parallel SortingIEEE Transactions on Computers, 1985
- An Architecture for Bitonic Sorting with Optimal VLSI PerformnanceIEEE Transactions on Computers, 1984
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- Efficient VLSI Networks for Parallel Processing Based on Orthogonal TreesIEEE Transactions on Computers, 1983
- Parallel permutation and sorting algorithms and a new generalized connection networkJournal of the ACM, 1982
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- New Parallel-Sorting SchemesIEEE Transactions on Computers, 1978
- The Indirect Binary n-Cube Microprocessor ArrayIEEE Transactions on Computers, 1977
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975