VLSI Sorting with Reduced Hardware
- 1 July 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (7) , 668-671
- https://doi.org/10.1109/TC.1984.5009340
Abstract
We propose a new VLSI architecture which allows many problems to be solved quite efficiently on chips with very small processing areas. We consider in detail the sorting problem and show how it can be solved quickly and elegantly on our model. We show that sorting n numbers can be done on a chip with processing area A = o(n) with an almost optimal speedup in a network with mesh-connected interconnections. The control is shown to be simple and easily implementable in VLSI.Keywords
This publication has 10 references indexed in Scilit:
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- A Mesh-Connected Area-Time Optimal VLSI Integer MultiplierPublished by Springer Nature ,1981
- On the Complexity of Sorting in Magnetic Bubble Memory SystemsIEEE Transactions on Computers, 1980
- Fully Interconnecting Multiple Computers with Pipelined Sorting NetsIEEE Transactions on Computers, 1979
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Algorithm and Hardware for a Merge Sort Using Multiple ProcessorsIBM Journal of Research and Development, 1978
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971