Area-time lower-bound techniques with applications to sorting (Q1091139): Difference between revisions
From MaRDI portal
Latest revision as of 09:36, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Area-time lower-bound techniques with applications to sorting |
scientific article |
Statements
Area-time lower-bound techniques with applications to sorting (English)
0 references
1986
0 references
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.
0 references
area-time complexity of VLSI computations
0 references
square-tessellation
0 references
information exchange
0 references
lower bounds
0 references
computational friction
0 references
sorting
0 references