Clustering based pruning for statistical criticality computation under process variations

Hushrav D. Mogal, Qian Haifeng, Sachin S. Sapatnekar, Kia Bazargan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

We present a new linear time technique to compute criticality information in a timing graph by dividing it into "zones". Errors in using tightness probabilities for criticality computation are dealt with using a new clustering based pruning algorithm which greatly reduces the size of circuit-level cutsets. Our clustering algorithm gives a 150X speedup compared to a pairwise pruning strategy in addition to ordering edges in a cutset to reduce errors due to Clark's MAX formulation. The clustering based pruning strategy coupled with a localized sampling technique reduces errors to within 5% of Monte Carlo simulations with large speedups in runtime.

Original languageEnglish (US)
Title of host publication2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
Pages340-343
Number of pages4
DOIs
StatePublished - Dec 1 2007
Event2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States
Duration: Nov 4 2007Nov 8 2007

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Other

Other2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD
CountryUnited States
CitySan Jose, CA
Period11/4/0711/8/07

Fingerprint Dive into the research topics of 'Clustering based pruning for statistical criticality computation under process variations'. Together they form a unique fingerprint.

Cite this