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

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 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1983
Accession Number
ADA142414

Entities

People

  • Franco P. Preparata
  • G. Bilardi

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Arrays
  • Buildings And Structures
  • Circuits
  • Classification
  • Computational Science
  • Computations
  • Contracts
  • Electronics
  • Electronics Laboratories
  • Illinois
  • Integrated Circuits
  • Large Scale Integrated Circuits
  • Networks
  • Parallel Computing
  • Security
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.
  • Parallel and Distributed Computing.