Accession Number:

ADA142414

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1983-11-01

Pagination or Media Count:

28.0

Abstract:

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

Subject Categories:

  • Computer Hardware
  • Computer Systems
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE