Statistical timing analysis under spatial correlations

Hongliang Chang, Sachin S. Sapatnekar

Research output: Contribution to journalArticlepeer-review

215 Scopus citations


Process variations are of increasing concern in today's technologies, and they can significantly affect circuit performance. An efficient statistical timing analysis algorithm that predicts the probability distribution of the circuit delay considering both inter-die and intra-die variations, while accounting for the effects of spatial correlations of intra-die parameter variations, is presented. The procedure uses a first-order Taylor series expansion to approximate the gate and interconnect delays. Next, principal component analysis (PCA) techniques are employed to transform the set of correlated parameters into an uncorrelated set. The statistical timing computation is then easily performed with a program evaluation and review technique (PERT)-like circuit graph traversal. The run time of this algorithm is linear in the number of gates and interconnects, as well as the number of varying parameters and grid partitions that are used to model spatial correlations. The accuracy of the method is verified with Monte Carlo (MC) simulation. On average, for the 100 nm technology, the errors of mean and standard deviation (SD) values computed by the proposed method are 1.06% and -4.34%, respectively, and the errors of predicting the 99% and 1% confidence point are -2.46% and -0.99%, respectively. A testcase with about 17800 gates was solved in about 500 s, with high accuracy as compared to an MC simulation that required more than 15 h.

Original languageEnglish (US)
Pages (from-to)1467-1482
Number of pages16
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - Sep 2005

Bibliographical note

Funding Information:
Manuscript received October 23, 2003; revised June 21, 2004. This work was supported in part by the National Science Foundation under award CCR-0205227 and by the Semiconductor Research Corporation under contract 2003-TJ-1092. The paper was recommended by Associate Editor F. N. Najm. H. Chang is with the Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455 USA. S. S. Sapatnekar is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. Digital Object Identifier 10.1109/TCAD.2005.850834


  • Circuit
  • Deep submicron
  • Timing analysis
  • VLSI


Dive into the research topics of 'Statistical timing analysis under spatial correlations'. Together they form a unique fingerprint.

Cite this