Variational capacitance modeling using orthogonal polynomial method

ABSTRACT

In this paper, we propose a novel statistical capacitance extraction method for interconnects considering process variations. The new method, called statCap, is based on the spectral stochastic method where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After that, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Experimental results show that our method is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical interconnect structures.

REFERENCES

• 1: Jeffrey Fan , Ning Mi , Sheldon X.-D. Tan , Yici Cai , Xianlong Hong, Statistical model order reduction for interconnect circuits considering spatial correlations, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 2: R. Ghanem, "The nonlinear Gaussian spectrum of log-normal stochastic processes and variables," Journal of Applied Mechanics, vol. 66, pp. 964--973, December 1999.
• 3: Roger G. Ghanem , Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag New York, Inc., New York, NY, 1991
• 4: 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
• 5: A. Klimke, "Sparse Grid Interpolation Toolbox -- user's guide," University of Stuttgart, Tech. Rep. IANS report 2006/001, 2006.
• 6: Andreas Klimke , Barbara Wohlmuth, Algorithm 847: Spinterp: piecewise multilinear hierarchical sparse grid interpolation in MATLAB, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.561-579, December 2005 [doi>10.1145/1114268.1114275]
• 7: A. Labun, "Rapid method to account for process variation in full-chip capacitance extraction," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 23, pp. 941--951, June 2004.
• 8: N. Mi, J. Fan, S. X.-D. Tan, Y. Cai, and X. Hong, "Statistical analysis of on-chip power delivery networks considering lognormal leakage current variations with spatial correlations," IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications, 2008, in press.
• 9: Ning Mi , Sheldon X.-D. Tan , Pu Liu , Jian Cui , Yici Cai , Xianlong Hong, Stochastic extended Krylov subspace method for variational analysis of on-chip power grid networks, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 10: K. Narbos and J. White, "FastCap: a multipole accelerated 3D capacitance extraction program," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 11, pp. 1447--1459, 1991.
• 11: S. Nassif, "Delay variability: sources, impact and trends," in Proc. IEEE Int. Solid-State Circuits Conf., San Francisco, CA, Feb 2000, pp. 368--369.
• 12: Sani R. Nassif, Design for Variability in DSM Technologies, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.451, March 20-22, 2000
• 13: C. C. Paige and M. A. Saunders, "Solution of sparse indefinite systems of linear equations," SIAM J. on Numerical Analysis, no. 4, pp. 617---629, September 1975.
• 14: S. Vrudhula, J. M. Wang, , and P. Ghanta, "Hermite polynomial based interconnect analysis in the presence of process variations," IEEE Trans. on Computer--Aided Design of Integrated Circuits and Systems, vol. 25, no. 10, 2006.
• 15: D. Wilton, S. Rao, A. Glisson, D. Schaubert, O. Al-Bundak, and C. Butler, "Potential integrals for uniform and linear source distributions on polygonal and polyhedral domains,"IEEE Trans. on Antennas and Propagation, vol. AP-32, no. 3, pp. 276--281, March 1984.
• 16: Dongbin Xiu , George Em Karniadakis, Modeling uncertainty in flow simulations via generalized polynomial chaos, Journal of Computational Physics, v.187 n.1, p.137-167, May 2003 [doi>10.1016/S0021-9991(03)00092-5]
• 17: Ying Zhou , Zhuo Li , Yuxin Tian , Weiping Shi , Frank Liu, A New Methodology for Interconnect Parasitics Extraction Considering Photo-Lithography Effects, Proceedings of the 2007 conference on Asia South Pacific design automation, p.450-455, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358027]
• 18: Hengliang Zhu , Xuan Zeng , Wei Cai , Jintao Xue , Dian Zhou, A sparse grid based spectral stochastic collocation method for variations-aware capacitance extraction of interconnects under nanometer process technology, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 19: 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
• 20: Zhenhai Zhu , J. White , A. Demir, A stochastic integral equation method for modeling the rough surface effect on interconnect capacitance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.887-891, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382699]
• 21: interconnect capacitance," in ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design. Washington, DC, USA: IEEE Computer Society, 2004, pp. 887---891.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Keywords:
capacitance extraction, orthogonal decomposition, process variations, random variable reduction