Fast and accurate statistical criticality computation under process variations

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


With ever-shrinking device geometries, process variations play an increased role in determining the delay of a digital circuit. Under such variations, a gate may lie on the critical path of a manufactured die with a certain probability, called the criticality probability. In this paper, we present a new technique to compute the statistical criticality information in a digital circuit under process variations by linearly traversing the edges in its timing graph and dividing it into zones. We investigate the sources of error in using tightness probabilities for criticality computation with Clark's statistical maximum formulation. The errors are dealt with using a new clustering-based pruning algorithm which greatly reduces the size of circuit-level cutsets improving both accuracy and runtime over the current state of the art. On large benchmark circuits, our clustering algorithm gives about a 250× speedup compared with a pairwise pruning strategy with similar accuracy in results. Coupled with a localized sampling technique, errors are reduced to around 5% of Monte Carlo simulations with large speedups in runtime.

Original languageEnglish (US)
Article number7
Pages (from-to)350-363
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
StatePublished - Mar 2009

Bibliographical note

Funding Information:
Manuscript received February 29, 2008; revised July 10, 2008. Current version published February 19, 2009. This work was supported in part by the SRC under Award 2007-TJ-1572. This paper was recommended by Associate Editor M. Orshansky. H. D. Mogal, S. S. Sapatnekar, and K. Bazargan are with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. H. Qian is with IBM Research, Yorktown Heights, NY 10598 USA. Color versions of one or more of the figures in this paper are available online at Digital Object Identifier 10.1109/TCAD.2009.2013278


  • Design automation
  • Digital integrated circuits
  • Statistical timing
  • VLSI


Dive into the research topics of 'Fast and accurate statistical criticality computation under process variations'. Together they form a unique fingerprint.

Cite this