Computation and refinement of statistical bounds on circuit delay

Aseem Agarwal, David Blaauw, Vladimir Zolotov, Sarma Vrudhula

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

69 Scopus citations


The growing impact of within-die process variation has created the need for statistical timing analysis, where gate delays are modeled as random variables. Statistical timing analysis has traditionally suffered from exponential run time complexity with circuit size, due to arrival time dependencies created by reconverging paths in the circuit. In this paper, we propose a new approach to statistical timing analysis that is based on statistical bounds of the circuit delay. Since these bounds have linear run time complexity with circuit size, they can be computed efficiently for large circuits. Since both a lower and upper bound on the true statistical delay is available, the quality of the bounds can be determined. If the computed bounds are not sufficiently close to each other, we propose a heuristic to iteratively improve the bounds using selective enumeration of the sample space with additional run time. We demonstrate that the proposed bounds have only a small error and that by carefully selecting an small set of nodes for enumeration, this error can be further improved.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
Number of pages6
StatePublished - 2003
EventProceedings of the 40th Design Automation Conference - Anaheim, CA, United States
Duration: Jun 2 2003Jun 6 2003


OtherProceedings of the 40th Design Automation Conference
Country/TerritoryUnited States
CityAnaheim, CA


  • Algorithms
  • Performance
  • Reliability

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering


Dive into the research topics of 'Computation and refinement of statistical bounds on circuit delay'. Together they form a unique fingerprint.

Cite this