Generalized Stochastic Collocation Method for Variation-Aware Capacitance Extraction of Interconnects Considering Arbitrary Random Probability

Hengliang ZHU
Xuan ZENG
Xu LUO
Wei CAI

Publication
IEICE TRANSACTIONS on Electronics   Vol.E92-C    No.4    pp.508-516
Publication Date: 2009/04/01
Online ISSN: 1745-1353
DOI: 10.1587/transele.E92.C.508
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Low-Leakage, Low-Voltage, Low-Power and High-Speed Technologies for System LSIs in Deep-Submicron Era)
Category: 
Keyword: 
variation-aware capacitance extraction,  geometric variations,  generalized polynomial chaos,  

Full Text: PDF>>
Buy this Article


Summary: 
For variation-aware capacitance extraction, stochastic collocation method (SCM) based on Homogeneous Chaos expansion has the exponential convergence rate for Gaussian geometric variations, and is considered as the optimal solution using a quadratic model to model the parasitic capacitances. However, when geometric variations are measured from the real test chip, they are not necessarily Gaussian, which will significantly compromise the exponential convergence property of SCM. In order to pursue the exponential convergence, in this paper, a generalized stochastic collocation method (gSCM) based on generalized Polynomial Chaos (gPC) expansion and generalized Sparse Grid quadrature is proposed for variation-aware capacitance extraction that further considers the arbitrary random probability of real geometric variations. Additionally, a recycling technique based on Minimum Spanning Tree (MST) structure is proposed to reduce the computation cost at each collocation point, for not only "recycling" the initial value, but also "recycling" the preconditioning matrix. The exponential convergence of the proposed gSCM is clearly shown in the numerical results for the geometric variations with arbitrary random probability.