Title :
Statistical timing analysis with correlated non-Gaussian parameters using independent component analysis
Author :
Singh, Jaskirat ; Sapatnekar, Sachin
Author_Institution :
Dept. of Electr. & Comput. Eng., Minnesota Univ.
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 Pade 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|)
Keywords :
approximation theory; independent component analysis; method of moments; network analysis; principal component analysis; Gaussian parameter; Monte Carlo simulations; Pade approximation; circuit delay; grid-based model; independent component analysis; moment matching; nonGaussian parameters; principal components analysis; spatial correlation grids; statistical timing analysis; Algorithm design and analysis; Circuits; Closed-form solution; Delay effects; Gaussian distribution; Independent component analysis; Principal component analysis; Probability distribution; Random variables; Timing; Independent Component Analysis; Moment Matching; Non-Gaussian; Performance; Statistical Timing;
Conference_Titel :
Design Automation Conference, 2006 43rd ACM/IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
1-59593-381-6
DOI :
10.1109/DAC.2006.229199