TY - GEN
T1 - Area-universal circuits with constant slowdown
AU - Bhatt, Sandeep N.
AU - Bilardi, Gianfranco
AU - Pucci, Geppino
N1 - Publisher Copyright:
© 1999 IEEE.
PY - 1999
Y1 - 1999
N2 - An area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at cost of lower area-time performance. In particular, if a circuit with area-time bounds (A,T) emulated with a universal circuit with bounds (Au,Tu), we say that the universal circuit has slowup 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 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/sup 1+ϵ/logA) nodes, with O(Aϵ) 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 UAϵ with O(1/ϵ) slowdown and O(ϵ2/Asup ϵ/ log4A) blowup, for any value of the parameter ϵ, 1/log Ales/ϵles/1. By varying, we obtain universal circuits which operate at different points in the spectrum of the slowdown-slowup tradeoff. In particular, when ϵ is chosen to be a constant, our universal circuit yields O(1) slowdown.
AB - An area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at cost of lower area-time performance. In particular, if a circuit with area-time bounds (A,T) emulated with a universal circuit with bounds (Au,Tu), we say that the universal circuit has slowup 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 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/sup 1+ϵ/logA) nodes, with O(Aϵ) 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 UAϵ with O(1/ϵ) slowdown and O(ϵ2/Asup ϵ/ log4A) blowup, for any value of the parameter ϵ, 1/log Ales/ϵles/1. By varying, we obtain universal circuits which operate at different points in the spectrum of the slowdown-slowup tradeoff. In particular, when ϵ is chosen to be a constant, our universal circuit yields O(1) slowdown.
UR - http://www.scopus.com/inward/record.url?scp=34548771139&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548771139&partnerID=8YFLogxK
U2 - 10.1109/ARVLSI.1999.756040
DO - 10.1109/ARVLSI.1999.756040
M3 - Conference contribution
AN - SCOPUS:34548771139
T3 - Proceedings - 20th Anniversary Conference on Advanced Research in VLSI, ARVLSI 1999
SP - 89
EP - 98
BT - Proceedings - 20th Anniversary Conference on Advanced Research in VLSI, ARVLSI 1999
A2 - DeWeerth, Stephen P.
A2 - Wills, D. Scott
T2 - 1999 Conference on Advanced Research in VLSI, ARVLSI 1999
Y2 - 21 March 1999 through 24 March 1999
ER -