Area-time lower-bound techniques with applications to sorting (Q1091139)

This paper is a contribution to the problem of area-time complexity of VLSI computations. The information exchanged across the boundary of the cell of a square-tessellation of the layout is studied. Two cases are distinguished: If the information exchange is due to the functional dependence between the input and output variables on opposite sides of the cell boundary, lower bounds are obtained for the \(AT^ 2\) measure. When information exchange is due to the storage saturation of the tessellation cells, a new type of lower bound is obtained on the AT measure. Furthermore, a mechanism is described which is called computational friction and it is shown that the applicability of this mechanism induces lower bounds on the AT/log A measure. The lower bound techniques introduced are illustrated by applying them to the sorting problem of n keys each of k bits. It is shown that \(AT^ 2\), AT, and AT/log A bounds can be derived which are interesting by themselves as each of them dominates the other two in a suitable range of key lengths and computation times.