An Improved Upper Bound for Sorting on Non-partitionable Superposed Parallel Buses

Abstract:

The paper presents O(n log n) and O(n log log n) sorting methods on n x n non-partionable superposed parallel buses. For merging and sorting on n processors connected by a linear bus, an optimal method based on enumeration is developed. It takes 3n/2 and 2n steps, which are O(log n) and O(log2 n) improvements from bitonic merge and sort respectively. For two dimensional sorting on superposed parallel buses, three different methods are considered: bitonic, shear, and reverse sort. Improvements in time complexity of O(log n) using the first two methods and of O(log2 n/ log log n) using the third method are obtained. Also time complexity measures based on the bus bandwidth are presented. A final discussion on VLSI optimality for the three sorting schemes is included.