loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
20th Anniversary Conference on Advanced Research in VLSI
Area-Universal Circuits with Constant Slowdown
Atlanta, Georgia
March 21-March 24
ISBN: 0-7695-0056-0
Sandeep N. Bhatt, Bell Communications Research
Gianfranco Bilardi, Universita' di Padova and University of Illinois at Chicago
Geppino Pucci, Universita' di Padova
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 with 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 paper, universal designs with O(1) blowup and O(log A) slowdown for area-A circuits were known. Universal designs for area-A circuits of O((A^((1/2)(1+epsilon)) log A) nodes, with O(A^epsilon) blowup and O(loglog 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^epsilon_A with O(1/epsilon) slowdown and O(epsilon^2 A^(epsilon) (log A)^4) blowup, for any value of the parameter epsilon, 1/log A <= epsilon <= 1. By varying epsilon, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. In particular, when epsilon is chosen to be a constant, our universal circuit yields O(1) slowdown.
Citation:
Sandeep N. Bhatt, Gianfranco Bilardi, Geppino Pucci, "Area-Universal Circuits with Constant Slowdown," arvlsi, pp.89, 20th Anniversary Conference on Advanced Research in VLSI, 1999
Usage of this product signifies your acceptance of the Terms of Use.