DocumentCode :
523984
Title :
Eyecharts: Constructive benchmarking of gate sizing heuristics
Author :
Gupta, Puneet ; Kahng, Andrew B. ; Kasibhatla, Amarnath ; Sharma, Puneet
Author_Institution :
Univ. of California, Los Angeles, CA, USA
fYear :
2010
fDate :
13-18 June 2010
Firstpage :
597
Lastpage :
602
Abstract :
Discrete gate sizing is one of the most commonly used, flexible, and powerful techniques for digital circuit optimization. The underlying problem has been proven to be NP-hard. Several (suboptimal) gate sizing heuristics have been proposed over the past two decades, but research has suffered from the lack of any systematic way of assessing the quality of the proposed algorithms. We develop a method to generate benchmark circuits (called eyecharts) of arbitrary size along with a method to compute their optimal solutions using dynamic programming. We evaluate the suboptimalities of some popular gate sizing algorithms. Eyecharts help diagnose the weaknesses of existing gate sizing algorithms, enable systematic and quantitative comparison of sizing algorithms, and catalyze further gate sizing research. Our results show that common sizing methods (including commercial tools) can be suboptimal by as much as 54% (Vt-assignment), 46% (gate sizing) and 49% (gate-length biasing) for realistic libraries and circuit topologies.
Keywords :
circuit complexity; circuit optimisation; NP-hard problem; constructive benchmarking; digital circuit optimization; discrete gate sizing; dynamic programming; eyecharts; suboptimal gate sizing heuristics; Algorithm design and analysis; Benchmark testing; Circuit topology; Delay; Dynamic programming; Logic; Permission; Software libraries; Threshold voltage; Very large scale integration; Gate sizing; benchmarking; dynamic programming;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design Automation Conference (DAC), 2010 47th ACM/IEEE
Conference_Location :
Anaheim, CA
ISSN :
0738-100X
Print_ISBN :
978-1-4244-6677-1
Type :
conf
Filename :
5523536
Link To Document :
بازگشت