Area-time tradeoffs for universal VLSI circuits

AbstractAn area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at the cost of lower area-time performance. In particular, if a circuit with area-time bounds (A,T) is emulated by a universal circuit with bounds (Au,Tu), we say that the universal circuit has blowup Au/A and slowdown Tu/T. A central question in VLSI theory is to investigate the inherent costs and tradeoffs of universal circuit designs.Prior to this work, universal designs were known for area-A circuits with O(1) blowup and O(logA) slowdown. Universal designs for the family of area-A circuits containing O(A1+ϵlogA) vertices, with O(Aϵ) blowup and O(loglogA) slowdown had also been developed. However, the existence of universal circuits with O(1) slowdown and relatively small blowup was an open question. In this paper, we settle this question by designing an area-universal circuit UAϵ with O(1/ϵ) slowdown and O(Aϵ) blowup, for any value of the parameter ϵ, with 4loglogA/logA≤ϵ≤1. By varying ϵ, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. In particular, when ϵ is chosen to be a constant, our universal circuit yields O(1) slowdown