A capacitance solver for incremental variation-aware extraction

ABSTRACT

Lithographic limitations and manufacturing uncertainties are resulting in fabricated shapes on wafer that are topologically equivalent, but geometrically different from the corresponding drawn shapes. While first-order sensitivity information can measure the change in pattern parasitics when the shape variations are small, there is still a need for a high-order algorithm that can extract parasitic variations incrementally in the presence of a large number of simultaneous shape variations. This paper proposes such an algorithm based on the well-known method of floating random walk (FRW). Specifically, we formalize the notion of random path sharing between several conductors undergoing shape perturbations and use it as a basis of a fast capacitance sensitivity extraction algorithm and a fast incremental variational capacitance extraction algorithm. The efficiency of these algorithms is further improved with a novel FRW method for dealing with layered media. Our numerical examples show a 10X speed up with respect to the boundary-element method adjoint or finite-difference sensitivity extraction, and more than 560X speed up with respect to a non-incremental FRW method for a high-order variational extraction.

REFERENCES

• 1: J. R. Phillips and J. K. White, "A precorrected-FFT method for electrostatic analysis of complicated 3D structures" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 1059--1072, 1997.
• 2: K. Nabors and J. K. White, "FASTCAP A multipole-accelerated 3D capacitance extraction program" IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 1447--1459, 1991.
• 3: W. Hackbusch, A sparse matrix arithmetic based on H-matrices. Part I: introduction to H-matrices, Computing, v.62 n.2, p.89-108, 1999 [doi>10.1007/s006070050015]
• 4: 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]
• 5: Tarek El-Moselhy , I. M. Elfadel , David Widiger, Efficient algorithm for the computation of on-chip capacitance sensitivities with respect to a large set of parameters, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California [doi>10.1145/1391469.1391699]
• 6: Fast Generation of Statistically-based Worst-Case Modeling of On-Chip Interconnect, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.720, October 12-15, 1997
• 7: D. Xiu and J. Hesthaven, "High-Order Collocation Method for Differential Equations with Random Inputs" SIAM J. Sci. Comput., 2005.
• 8: Tony F. Chan , Michael K. Ng, Galerkin Projection Methods for Solving Multiple Linear Systems, SIAM Journal on Scientific Computing, v.21 n.3, p.836-850, Nov.-Dec. 1999 [doi>10.1137/S1064827598310227]
• 9: Michael L. Parks , Eric de Sturler , Greg Mackey , Duane D. Johnson , Spandan Maiti, Recycling Krylov Subspaces for Sequences of Linear Systems, SIAM Journal on Scientific Computing, v.28 n.5, p.1651-1674, September 2006 [doi>10.1137/040607277]
• 10: R. B. Iverson and Y. L. Le Coz, "A Stochastic Algorithm for High Speed capacitance Extraction in Integrated Circuits," Solid-State Electronics, Vol. 35, No. 7, pp. 1005--1012, 1992.
• 11: J. N. Jere and Y. L. Le Coz, "An Improved Floating-Random Walk Algorithm for Solving Multi-Dielectric Dirichlet Problem" IEEE Transaction on Microwave Theory and Techniques, Vol. 41, No. 2, pp. 325 -- 329, 1993.
• 12: J. Wang and J. White., "Fast Algorithms for Computing Electrostatic Geometric Sensitivities" International Conference on Simulation of Semiconductor Processes and Devices, pp. 121--123, 1997.
• 13: T. Gerstner and M. Griebel, "Numerical Integration using Sparse Grids" Numerical Algorithms, 1998.