The area-time complexity of sorting (algorithms, computation, architecture, vlsi)

This thesis studies the minimum area A = (alpha)(,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 exchanged 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('2) 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('2) 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 suggests a classification of keys into short (k (LESSTHEQ) logn), long (k (GREATERTHEQ) 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.