SCIENTIA SINICA Informationis, Volume 46 , Issue 10 : 1372-1391(2016) https://doi.org/10.1360/N112016-00085

Massively parallel computing in nano-VLSI interconnect modeling and lithography simulation

More info
  • ReceivedMay 4, 2016
  • AcceptedAug 4, 2016
  • PublishedOct 25, 2016


VLSI is large in scale, and complex in structure. In today's nano-VLSI, serious process variations induced by the complex nanometer integrated circuit process technology may result in severe degradation of the integrated circuit performance. These factors present ever increasing challenges for present day nano-scale VLSI design. Interconnect modeling and lithography simulations rely on numerical approaches for solving large-scale Maxwell's equations, of which the computational cost is extremely high. In this paper, several massively parallel computing approaches for interconnect modeling and lithography simulation are surveyed, based on adaptive finite element theory and a parallel hierarchical grid (PHG) platform. Regarding interconnect modeling, we first review the parallel adaptive finite-element method ParAFEMCap for parasitic capacitance extraction, which achieves a parallel efficiency of 75.7\% on 1536 CPU cores. In addition, we review a hybridization of the boundary integral equation method and the random walk on spheres method (BIE-WOS) for surface charge density computations for conductors or dielectric mediums. The proposed method proves to be superior to existing methods for massively parallel computing. On a supercomputer with 5120 CPU cores, BIE-WOS can achieve almost a linear parallel efficiency. Regarding lithography simulation, we propose a parallel adaptive finite-element framework method by adopting the PHG (parallel hierarchical grid) platform and a perfectly matched anisotropy uniaxial layer to handle scattering boundary conditions.

Funded by






中国科学院国家数学与交叉科学研究中心(NC MIS)


国家高技术研究发展计划(863 计划)








[1] Sabelka R, Harlander C, Selberherr S. The state of the art in interconnect simulation. In: Proceedings of International Conference on Simulation of Semiconductor Processes and Devices, Seattle, 2000. 6-11. Google Scholar

[2] Nagaraj N S, Bonifield T, Singh A, et al. Benchmarks for interconnect parasitic resistance and capacitance. In: Proceedings of the 4th International Symposium on Quality Electronic Design, San Jose, 2003. 163-168. Google Scholar

[3] Kao W H, Lo C, Basel M, et al. Parasitic extraction: current state of the art and future trends. newblock Proc IEEE, 2001, 89: 729-739 CrossRef Google Scholar

[4] Delorme N, Belleville M, Chilo J. Inductance and capacitance analytic formulas for vlsi interconnects. newblock Electron Lett, 1996, 32: 996-997 CrossRef Google Scholar

[5] Nabors K, White J. {FastCap}: a multipole accelerated 3-D capacitance extraction program. newblock IEEE Trans Comput-Aided Design Integr Circ Syst, 1991, 10: 1447-1459 CrossRef Google Scholar

[6] Yan S, Sarin V, Shi W. Sparse transformations and preconditioners for 3-D capacitance extraction. newblock IEEE Trans Comput-Aided Design Integr Circ Syst, 2005, 24: 1420-1426 CrossRef Google Scholar

[7] Shi W, Liu J, Kakani N, et al. A fast hierarchical algorithm for three-dimensional capacitance extraction. newblock IEEE Trans Comput-Aided Design Integr Circ Syst, 2002, 21: 330-336 CrossRef Google Scholar

[8] Ozgun O, Mittra R, Kuzuoglu M. {CBFEM-MPI}: a parallelized version of characteristic basis finite element method for extraction of 3-D interconnect capacitances. newblock IEEE Trans Adv Packag, 2009, 32: 164-174 CrossRef Google Scholar

[9] Chen G L, Zhu H L, Cui T, et al. Parafemcap: a parallel adaptive finite-element method for 3-D VLSI interconnect capacitance extraction. newblock IEEE Trans Microw Theory Tech, 2012, 60: 218-231 CrossRef Google Scholar

[10] Veremey V, Mittra R. A technique for fast calculation of capacitance matrices of interconnect structures. newblock IEEE Trans Compon Packag Manuf Tech Part B: Adv Packag, 1998, 21: 241-249 CrossRef Google Scholar

[11] Coz Y L L, Iverson R B. A stochastic algorithm for high speed capacitance extraction in integrated circuits. newblock Solid-State Electron, 1992, 35: 1005-1012 CrossRef Google Scholar

[12] Yuan Y, Banerjee P. A parallel implementation of a fast multipole-based 3-D capacitance extraction program on distributed memory multicomputers. newblock J Parallel Distrib Comput, 2001, 61: 1751-1774 CrossRef Google Scholar

[13] Zhao X Q, Feng Z. Fast multipole method on gpu tackling 3-D capacitance extraction on massively parallel simd platforms. In: Proceedings of IEEE/ACM Design Automation Conference, New York, 2011. 558-563. Google Scholar

[14] Hsiao Y C, Daniel L. Caplet: a highly parallelized field solver for capacitance extraction using instantiable basis functions. newblock IEEE Trans Comput-Aided Design Integr Circ Syst, 2016, 35: 458-470 CrossRef Google Scholar

[15] Yan C H, Cai W, Zeng X. A parallel method for solving laplace equations with dirichlet data using local boundary integral equations and random walks. newblock SIAM J Sci Comput, 2013, 35: B868-B889 CrossRef Google Scholar

[16] Wong A K, Neureuther A R. Rigorous three-dimensional time-domain finite-difference electromagnetic simulation for photolithographic applications. newblock IEEE Trans Semicond Manuf, 1995, 8: 419-431 CrossRef Google Scholar

[17] Lucas K D, Tanabe H, Strojwas A J. Effcient and rigorous three-dimensional model for optical lithography simulation. newblock J Opt Soc America, 1996, 13: 2187-2199 CrossRef Google Scholar

[18] Cai W, Ji X, Sun J, et al. A schwarz generalized eigen-oscillation spectral element method (GeSEM) for 2-D high frequency electromagnetic scattering in dispersive inhomogeneous media. newblock J Comput Phys, 2008, 227: 9933-9954 CrossRef Google Scholar

[19] Zong K, Zeng X, Ji X, et al. {Highly parallel rigorous simulation of phase shift masks with a generalized eigen-oscillation spectral element method (GeSEM)}. newblock J Micro/Nanolith MEMS MOEMS (JM3), 2009, 8: 031403-9954 CrossRef Google Scholar

[20] Burger S, Kohle R, Zschiedrich L, et al. Benchmark of FEM, waveguide and FDTD algorithms for rigorous mask simulation. Proc SPIE, 2005, 5992: 368-379. Google Scholar

[21] Chen Z, Dai S. On the efficiency of adaptive finite element methods for elliptic problems with discontinuous coefficients. newblock SIAM J Sci Comput, 2002, 24: 443-462 CrossRef Google Scholar

[22] Zhang L B, Zheng W Y, Lu B Z, et al. The toolbox PHG and its applications. Sci Sin Inform, 2016, 10: 1442-1464 [张林波, 郑伟英, 卢本卓, 等. 并行自适应有限元软件平台 PHG 及其应用. 中国科学: 信息科学, 2016, 10: 1442-1464]. Google Scholar

[23] Cui T, Chen J Q, Zhu H L, et al. Algorithms in {ParAFEMImp}: a parallel and wideband impedance extraction program for complicated 3-D geometries. In: Proceedings of IEEE International Conference on High Performance and Smart Computing (HPSC), New York, 2016. 304-309. Google Scholar

[24] Zhang L. A parallel algorithm for adaptive local refinement of tetrahedral meshes using bisection. {Numer Math Theory Meth Appl}, 2009, 2: 65-89. Google Scholar

[25] Friedman A. {Stochastic Differential Equations and Applications}. New York: Dover Publications, 2006. Google Scholar

[26] Hwang C O, Given J A. Last-passage monte carlo algorithm for mutual capacitance. newblock Phys Rev E, 2006, 74: 027701-89 CrossRef Google Scholar

[27] Wong A S, Newmark D M, Rolfson J B, et al. Investigating phase-shifting mask layout issues using a {CAD} toolkit. In: Proceedings of International Electron Devices Meeting, Washington, 1991. 705-708. Google Scholar

[28] Yu P, Pan D Z. TIP-OPC: a new topological invariant paradigm for pixel based optical proximity correction. In: Proceedings of IEEE/ACM International Conference on Computer-Aided Design, San Jose, 2007. 847-853. Google Scholar

[29] Pan D Z, Liebmann L, Yu B, et al. Pushing multiple patterning in sub-10nm: are we ready? In: Proceedings of the 52nd IEEE/ACM Design Automation Conference (DAC), San Francisco, 2015. 1-6. Google Scholar

[30] Ponomarev G A, Yakubov V P. Kirchhoff's approximation method of geometrical optics in the problem of scattering of waves at an irregular surface. newblock Radiophys Quant Electron, 1976, 19: 849-852 CrossRef Google Scholar

[31] Amestoy P R, Duff I S, L'Excellent J Y, et al. A fully asynchronous multifrontal solver using distributed dynamic scheduling. newblock Siam J Matrix Anal Appl, 2001, 23: 15-41 CrossRef Google Scholar

[32] Chen Z M, Xiang X S. A source transfer domain decomposition method for helmholtz equations in unbounded domain. newblock SIAM J Numer Anal, 2013, 51: 2331-2356 CrossRef Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号