Area-Time Lower-Bound Techniques with Applications to Sorting

The area-time complexity of VLSI computations is constrained by the flow and the storage of information in the two-dimensional chip. We study here the information exchanged across the boundary of the cells of a square-tessellation of the layout. When the information exchange is due to the functional dependence between variables respectively input and output on opposite sides of a cell boundary, lower bounds are obtained on the AT(2) measure (which subsume bisection bounds as a special case). When information exchange is due to the storage saturation of the tessellation cells, a new type of lower bound is obtained on the A T measure. In the above arguments, information is essentially viewed as a fluid whose flow is uniquely constrained by the available bandwidth. However, in some computations, the flow is kept below capacity by the necessity to transform information before an output is produced. We call this mechanism computational friction and show that it implies lower bounds on the AT/log A measure. Regimes corresponding to each of the three mechanisms described above can appear by varying the problem parameters, as we shall illustrate by analyzing the problem of sorting n keys each of k bits, for which AT(2), AT, and AT/log A bounds are derived. Each bound is interesting, since it dominates the other two in a suitable range of key lengths and computations times.