(λT) Complexity Measures for VLSI Computations in Constant Chip Area

The computational complexity measures introduced here are motivated by the trend to higher VLSI integration levels (rather than increased chip area) to accomplish solutions to larger problem instances. It seems that the increase in the computational power of VLSI circuits can be mainly attributed to the reduction in the minimum feature size rather than to an increase in the chip area. In view of this, we present a constant area perspective and consider the discrete Fourier transform and related problems in a VLSI model that has λand T as its resources. Advantages of the mesh algorithm over the shuffle-exchange algorithm in the computation time for the DFT are shown to arise from an upper bound on current density in the wires, which we suggest must be considered in any VLSI grid model.