TRADEOFFS FOR VLSI MODELS WITH SUBPOLYNOMIAL DELAY.

Abstract

The effect of delay along long wires in VLSI on the area-time complexity of computing certain functions has been investigated recently. However, tradeoffs have been established only for the cases where the delay is a polynomial in the length of the wire. On the other hand, most researchers believe that a more pragmatic model is one that has theta (log l) delay along a wire length l. However, no serious effort has gone into establishing optimal tradeoffs or lower bounds in this model. The authors attempt to eliminate this deficiency by investigating bounds on area and time for computing certain transitive functions and addition in the subpolynomial delay models. In particular, they demonstrate some results which contradict intuition as well as some widely held conjectures.