Extreme Area-Time Tradeoffs in VLSI.

In this paper we consider the layout of bounded fan-out prefix computation in VLSI and show that the area requirements of such graphs exhibit a very interesting property. A small constant factor reduction in time of computation from 2log eta to log eta increases the area required to embed an eta node prefix computation graph significantly from 0(eta log eta) to OMEGA (eta(2)). For time of computation T, log eta =T= 2 log eta, the area requirements are OMEGA(eta(2)2{2(log eta-T)} + eta). We call this behavior an example of an extreme area-time tradeoff in VLSI. Since prefix computation also models the carry computation is a carry lookahead adder, the same behavior is observed in the area requirements of a near-minimum computation time carry lookahead adder.