A Minimum Area VLSI (Very Large Scale Integrated Architecture for O(LOGN) Time Sorting

摘要

A generalization of a known class of parallel sorting algorithms is presented, together with a new architecture to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in 0(logn) time by a chip occupying O(n2) area. The design is a typical instance of a 'hybrid architecture', resulting from the combination of well-known VLSI arrays as the orthogonal-trees and the cube-connected-cycles; it is also the first known to meet the AT21 = omega(n2log2n) lower bound for sorters of n words of length (1 + epsilon) and working in minimum 0(logn) time. (Author)