The VLSI Optimality of the AKS Sorting Network.

Abstract

Ajtai, Komlos, and Szemeredi recently proposed a sorting network of O(nlogn) comparators and O(logn) depth. Their construction is of great theoretical interest, for it shows that O(nlogn) comparisons suffice to sort n elements, even under the constraint that comparisons be nonadaptively executed in O(logn) parallel stages. At present, the AKS network appears not suitable for practical implementations, due to the large value of the constraints; however, improvements are conceivable that could make the network more attractive for real-world applications, It is therefore natural to ask what is the performance of the AKS network in the synchronous VLSI model of computation which has been proposed to capture the essential features of planar very large scale integration as a computing environment. In this model it is known that any chip capable of sorting n words of length q = (1+ alpha)logn. with alpha > 0, must satisfy a certain relationship where A is the chip area, and T is the computation time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1984
Accession Number
ADA161335

Entities

People

  • Franco P. Preparata
  • Gianfranco Bilardi

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Counter IED

DTIC Thesaurus Topics

  • Algorithms
  • Assembly
  • Buildings And Structures
  • Comparators
  • Computational Science
  • Computations
  • Construction
  • Contracts
  • Electronics
  • Environment
  • Fabrication
  • Hierarchies
  • Illinois
  • Large Scale Integration
  • Trees (Data Structures)
  • Two Dimensional
  • Very Large Scale Integration

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.
  • Operations Research