Area-time tradeoffs for universal VLSI circuits

An 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 (A_u, T_u), we say that the universal circuit has blowup A_u / A and slowdown T_u / 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 (log A) slowdown. Universal designs for the family of area-A circuits containing O (sqrt(A^{1 + ε{lunate}}) log A) vertices, with O (A^ε{lunate}) blowup and O (log log A) 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 U_A^ε{lunate} with O (1 / ε{lunate}) slowdown and O (A^ε{lunate}) blowup, for any value of the parameter ε{lunate}, with 4 log log A / log A ≤ ε{lunate} ≤ 1. By varying ε{lunate}, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. In particular, when ε{lunate} is chosen to be a constant, our universal circuit yields O (1) slowdown.