A Minimum Area VLSI (Very Large Scale Integrated Architecture for O(LOGN) Time Sorting.
ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP
Pagination or Media Count:
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 0logn time by a chip occupying On2 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 omegan2log2n lower bound for sorters of n words of length 1 epsilon and working in minimum 0logn time. Author
- Computer Hardware
- Computer Systems
- Non-Radio Communications