Quantifying Error: Extending Static Timing Analysis with Probabilistic Transitions

Kevin E. Murray1,a, Andrea Suardi2,c, Vaughn Betz1,b and George Constantinides2,d
1Electrical and Computer Engineering, University of Toronto.
2Electrical and Electronic Engineering, Imperial College London.


Timing analysis is a cornerstone of the digital design process. Statistical Static Timing Analysis was introduced to reduce pessimism by modelling device delay variations. However it ignores circuit logic, which may cause some timing paths to never or only rarely be sensitized. We introduce a general timing analysis approach and tool to calculate the probability that individual timing paths are sensitized, enabling the calculation of bounding delay distributions over all input combinations. We show the connection to the well-known #SAT problem and present approaches to improve scalability, achieving average results 46 to 32% less pessimistic than Static Timing Analysis while running 14.6 to 44.0 times faster than Monte-Carlo timing simulation.

Full Text (PDF)