Area-universal circuits with constant slowdown

Sandeep N. Bhatt, Gianfranco Bilardi, Geppino Pucci

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 20th Anniversary Conference on Advanced Research in VLSI, ARVLSI 1999
EditorsStephen P. DeWeerth, D. Scott Wills
Pages89-98
Number of pages10
ISBN (Electronic)0769500560, 9780769500560
DOIs
StatePublished - 1999
Event1999 Conference on Advanced Research in VLSI, ARVLSI 1999 - Atlanta, United States
Duration: 21 Mar 199924 Mar 1999

Publication series

NameProceedings - 20th Anniversary Conference on Advanced Research in VLSI, ARVLSI 1999

Conference

Conference1999 Conference on Advanced Research in VLSI, ARVLSI 1999
Country/TerritoryUnited States
CityAtlanta
Period21/03/9924/03/99

Fingerprint

Dive into the research topics of 'Area-universal circuits with constant slowdown'. Together they form a unique fingerprint.

Cite this