The distance bound for sorting on mesh-connected processor arrays is tight
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 255-263
- https://doi.org/10.1109/sfcs.1986.54
Abstract
In this paper, We consider the problem of sorting n2 numbers, initially distributed randomly in an n × n mesh-connected processor array with one element per processor. We show a lower bound, based on distance arguments, of 4n routing steps on mesh-connected processors operating in an SIMD mode with no wraparounds in rows or columns, We present an algorithm using a novel approach, which is optimal upto the conslant of the leading term, and hence, succeed in proving the tightness of the lower bound based on distance. Keeping in mind the practical difficulties in implementation of this algorithm, we also present an extremely practical O(n) algorithm amenable for VLSI implementation and for existing mesh- connected computers. All the results in this paper were derived by using a new method of analysis inspired by the discovery of shear-sort or row-column sort.Keywords
This publication has 7 references indexed in Scilit:
- Some parallel sorts on a mesh-connected processor array and their time efficiencyJournal of Parallel and Distributed Computing, 1986
- An optimal sorting algorithm for mesh connected computersPublished by Association for Computing Machinery (ACM) ,1986
- The VLSI Complexity of SortingIEEE Transactions on Computers, 1983
- An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting SchemesIEEE Transactions on Computers, 1983
- Optimal BPC Permutations on a Cube Connected SIMD ComputerIEEE Transactions on Computers, 1982
- Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers, 1979
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977