Extreme area-time tradeoffs in VLSI

Consideration is given to the layout of bounded fan-in and fan-out prefix computation graphs in VLSI, and it is shown that the area requirements of such graphs exhibit this interesting property. A small constant factor reduction in time of computation from 2 log η to log η increases the area required to embed an η node prefix computation graph significantly from O(η log η) to Ω(η ²). The area requirements are also given. This behavior is an example of an extreme area-time tradeoff in VLSI. Since prefix computation also models the carry computation in a carry look-ahead adder, the same behavior is observed in the area requirements of a near-minimum computation time carry look-ahead adder. The authors also present circuits which meet the derived lower bounds for all values of T between log η and 2 log η