Universality in VLSI Computation

A VLSI circuit U(A) is said to be area-universal if it can be configured to emulate every VLSI circuit of a given area A. If U(A) has area A_U, then it has blowup alpha = A_U/A. If any circuit with area-time bounds (A,T) is emulated by U(A) in time T_U \leq \sigma T, then U(A) has slowdown sigma. Clearly, smaller blowup and smaller slowdown reflect a better quality of a universal circuit. An analogous formulation enables the study of area-universal general-purpose routing. The broad goal of research on area-universality is to characterize blowup/slowdown tradeoffs, that is, what is the minimum blowup achievable for any given slowdown.