Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-071-87
An Improved Upper Bound for Sorting on Non-partitionable Superposed Parallel Buses
Authors: Arden, Bruce W., Nakatani, Toshio
Date:January 1987
Pages:24
Download Formats: [PDF]
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.