The VLSI Complexity of Sorting
- 1 December 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (12) , 1171-1184
- https://doi.org/10.1109/tc.1983.1676178
Abstract
The area-time complexity of sorting is analyzed under an updated model of VLSI computation. The new model makes a distinction between "processing" circuits and "memory" circuits; the latter are less important since they are denser and consume less power. Other adjustments to the model make it possible to compare pipelined and nonpipelined designs.Keywords
This publication has 27 references indexed in Scilit:
- An 0(n log n) sorting networkPublished by Association for Computing Machinery (ACM) ,1983
- A logarithmic time sort for linear size networksPublished by Association for Computing Machinery (ACM) ,1983
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Area—time tradeoffs for matrix multiplication and related problems in VLSI modelsJournal of Computer and System Sciences, 1981
- The cube-connected-cycles: A versatile network for parallel computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Fully Interconnecting Multiple Computers with Pipelined Sorting NetsIEEE Transactions on Computers, 1979
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Big Omicron and big Omega and big ThetaACM SIGACT News, 1976
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971