Title :
Statistical Timing Analysis Considering Spatial Correlations
Author :
Li, Hong ; Koh, Cheng-Kok ; Balakrishnan, Venkataramanan ; Chen, Yiran
Author_Institution :
Sch. of Electr. & Comput. Eng., Purdue Univ., West Lafayette, IN
Abstract :
In this paper, we present an efficient algorithm to predict the probability distribution of the circuit delay while accounting for spatial correlations. We exploit the structure of the covariance matrix to decouple the correlated variables to independent ones in linear-time, as opposed to conventional techniques which have a cubic-time complexity. Furthermore, we present a closed-form expression for the probability distribution of the max operation, based on which we propose a fast and accurate approximation technique. Experiments show that the proposed method is both accurate and efficient
Keywords :
approximation theory; circuit complexity; covariance matrices; delays; statistical analysis; statistical distributions; timing; circuit delay; closed-form expression; covariance matrix; cubic-time complexity; probability distribution; spatial correlations; statistical timing analysis; Algorithm design and analysis; Circuits; Closed-form solution; Covariance matrix; Delay; Distributed computing; Gaussian distribution; Probability distribution; Random variables; Timing;
Conference_Titel :
Quality Electronic Design, 2007. ISQED '07. 8th International Symposium on
Conference_Location :
San Jose, CA
Print_ISBN :
0-7695-2795-7
DOI :
10.1109/ISQED.2007.149