Systolic Sorting on a Mesh-Connected Network
- 1 July 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (7), 652-658
- https://doi.org/10.1109/tc.1985.1676603
Abstract
A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.Keywords
This publication has 7 references indexed in Scilit:
- An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting SchemesIEEE Transactions on Computers, 1983
- A “Zero-Time” VLSI SorterIBM Journal of Research and Development, 1983
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- The Design of Special-Purpose VLSI ChipsComputer, 1980
- 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