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


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)
Pages (from-to)350-363
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number1
StatePublished - Jan 1 2009


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

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

Cite this