Statistical timing analysis with correlated non-gaussian parameters using independent component analysis

Jaskirat Singh, Sachin S Sapatnekar

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

89 Scopus citations

Abstract

We propose a scalable and efficient parameterized block-based statistical static timing analysis algorithm incorporating both Gaussian and non-Gaussian parameter distributions, capturing spatial correlations using a grid-based model. As a preprocessing step, we employ independent component analysis to transform the set of correlated non-Gaussian parameters to a basis set of parameters that are statistically independent, and principal components analysis to orthogonalize the Gaussian parameters. The procedure requires minimal input information: given the moments of the variational parameters, we use a Padé approximation-based moment matching scheme to generate the distributions of the random variables representing the signal arrival times, and preserve correlation information by propagating arrival times in a canonical form. For the ISCAS89 benchmark circuits, as compared to Monte Carlo simulations, we obtain average errors of 0.99% and 2.05%, respectively, in the mean and standard deviation of the circuit delay. For a circuit with G gates and a layout with g spatial correlation grids,the complexity of our approach is O(g G).

Original languageEnglish (US)
Title of host publication2006 43rd ACM/IEEE Design Automation Conference, DAC'06
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages155-160
Number of pages6
ISBN (Print)1595933816, 1595933816, 9781595933812
DOIs
StatePublished - 2006
Event43rd Annual Design Automation Conference, DAC 2006 - San Francisco, CA, United States
Duration: Jul 24 2006Jul 28 2006

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conference43rd Annual Design Automation Conference, DAC 2006
Country/TerritoryUnited States
CitySan Francisco, CA
Period7/24/067/28/06

Keywords

  • Independent component analysis
  • Moment matching
  • Non-Gaussian
  • Statistical timing

Fingerprint

Dive into the research topics of 'Statistical timing analysis with correlated non-gaussian parameters using independent component analysis'. Together they form a unique fingerprint.

Cite this