The Area-Time Complexity of Sorting.
Abstract
This thesis studies the minimum area A = alpha sub n,k (T) required by a layout of a VLSI circuit that sorts n k-bit keys in time T. The square tessellation technique is introduced as a powerful tool to establish area-time lower bounds, based on the information exchanges across the boundary of a suitable set of square cells that tessellate the layout region. When the information exchange is due to the fact that variables output on one side of the cell boundary are functions of variables input on the other side, the square tessellation yields bounds on the AT squared measure. When, on the other hand, the information exchange is due to the fact that the cell saturates its storage resources and sends some information outside for temporary storage, the square tessellation yields bounds on the AT measure. Both AT squared and AT lower bounds are obtained for sorting. The former dominate in fast computations, while the latter dominate in slow computations. The analysis indicates that the nature of the problem varies considerably with the relative size of n and k, and suggest a classification of keys into short (k > or = logn), long (k > or = 2logn), and of medium length . Optimal or near-optimal designs of VLSI sorters are proposed for the entire range of n, k, and T, confirming the inherent validity of the lower-bound analysis. Keyword: Parallel processors.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1984
- Accession Number
- ADA161562
Entities
People
- Gianfranco Bilardi
Organizations
- University of Illinois Urbana–Champaign