A sparse grid based spectral stochastic collocation method for variations-aware capacitance extraction of interconnects under nanometer process technology

ABSTRACT

In this paper, a Spectral Stochastic Collocation Method (SSCM) is proposed for the capacitance extraction of interconnects with stochastic geometric variations for nanometer process technology. The proposed SSCM has several advantages over the existing methods. Firstly, compared with the PFA (Principal Factor Analysis) modeling of geometric variations, the K-L (Karhunen-Loeve) expansion involved in SSCM can be independent of the discretization of conductors, thus significantly reduces the computation cost. Secondly, compared with the perturbation method, the stochastic spectral method based on Homogeneous Chaos expansion has optimal (exponential) convergence rate, which makes SSCM applicable to most geometric variation cases. Furthermore, Sparse Grid combined with a MST (Minimum Spanning Tree) representation is proposed to reduce the number of sampling points and the computation time for capacitance extraction at each sampling point. Numerical experiments have demonstrated that SSCM can achieve higher accuracy and faster convergence rate compared with the perturbation method.

REFERENCES

• 1: Xin Li , Jiayong Le , P. Gopalakrishnan , L. T. Pileggi, Asymptotic probability extraction for non-normal distributions of circuit performance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.2-9, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382533]
• 2: J. Xiong, V. Zolotov, and L. He. Robust extraction of spatial correlation. IEEE Transactions on ICSCAD, Accepted for future publication.
• 3: Rong Jiang , Wenyin Fu , J. M. Wang , V. Lin , C. C. -P. Chen, Efficient statistical capacitance variability modeling with orthogonal principle factor analysis, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.683-690, November 06-10, 2005, San Jose, CA
• 4: Zhenhai Zhu , J. White, FastSies: a fast stochastic integral equation solver for modeling the rough surface effect, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.675-682, November 06-10, 2005, San Jose, CA
• 5: Roger G. Ghanem , Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag New York, Inc., New York, NY, 1991
• 6: Praveen Ghanta , Sarma Vrudhula , Rajendran Panda , Janet Wang, Stochastic Power Grid Analysis Considering Process Variations, Proceedings of the conference on Design, Automation and Test in Europe, p.964-969, March 07-11, 2005 [doi>10.1109/DATE.2005.282]
• 7: Y. Satish Kumar , Jun Li , Claudio Talarico , Janet Wang, A Probabilistic Collocation Method Based Statistical Gate Delay Model Considering Process Variations and Multiple Input Switching, Proceedings of the conference on Design, Automation and Test in Europe, p.770-775, March 07-11, 2005 [doi>10.1109/DATE.2005.31]
• 8: S. A. Smolyak. Quadrature and interpolation formulas for tensor products of certain classes of functions. Soviet Math., 4:240--243, 1963.
• 9: H. J. Bungartz. Sparse grids. Acta Numerica, pages 1--123, 2004.
• 10: K. Nabors and J. White. Fastcap: A multipole accelerated 3-d capacitance extraction program. IEEE Transactions on Computer-aided Design, 10(11): 1447--1459, november 1991.
• 11: Dongbin Xiu , George Em Karniadakis, The Wiener--Askey Polynomial Chaos for Stochastic Differential Equations, SIAM Journal on Scientific Computing, v.24 n.2, p.619-644, 2002 [doi>10.1137/S1064827501387826]
• 12: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 13: W. Shi, J. Liu, and N. Kakani. A fast hierarchical algorithm for 3-D capacitance extraction. IEEE Transactions on ICSCAD, 21(3):330--336, 2002.
• 14: S. Yan, V. Sarin, and W. Shi. Sparse transformations and preconditioners for 3d capacitance extraction. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, 24(9): 1420--1426, 2005.
• 15: E. Novak and K. Ritter. Simple cubature formulas with high polynomial exactness. Constructuve Approximation, 15(4):449--522, December 1999.
• 16: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001