Optimal VLSI sorting with reduced number of processors
Hussein Alnuweiri, Vinod Kumar · IEEE Transactions on Computers · 1991
A new parallel architecture is presented which has p processors and N=n/sup 2/ memory locations, each consisting of 2s bits. The proposed organization can sort N s-bit numbers, where s=O((1+ epsilon ) log N), epsilon >0, in time t=O(N log N/p), for p in the range 1 to square root N log square root N. This result is optimal in the sense that the product of the number of processors and the parallel sorting time is equal to the sequential complexity of sorting. Also, the constant factors involved in the algorithm complexity are relatively small. When p= square root N log square root N, the time required for sorting N numbers on the proposed organization is O( square root N), which is the same time required by a two-dimensional mesh array, a mesh of trees organization, or a pyramid computer, all with O(N) processors, to sort N numbers.>