Efficient numerical methods for capacitance extraction based on boundary element method

摘要

Fast and accurate solvers for capacitance extraction are needed by the VLSI industryin order to achieve good design quality in feasible time. With the developmentof technology, this demand is increasing dramatically. Three-dimensional capacitanceextraction algorithms are desired due to their high accuracy. However, the present3D algorithms are slow and thus their application is limited. In this dissertation, wepresent several novel techniques to significantly speed up capacitance extraction algorithmsbased on boundary element methods (BEM) and to compute the capacitanceextraction in the presence of floating dummy conductors.We propose the PHiCap algorithm, which is based on a hierarchical refinementalgorithm and the wavelet transform. Unlike traditional algorithms which result indense linear systems, PHiCap converts the coefficient matrix in capacitance extractionproblems to a sparse linear system. PHiCap solves the sparse linear system iteratively,with much faster convergence, using an efficient preconditioning technique. We alsopropose a variant of PHiCap in which the capacitances are solved for directly from avery small linear system. This small system is derived from the original large linearsystem by reordering the wavelet basis functions and computing an approximate LUfactorization. We named the algorithm RedCap. To our knowledge, RedCap is thefirst capacitance extraction algorithm based on BEM that uses a direct method to solve a reduced linear system.In the presence of floating dummy conductors, the equivalent capacitances amongregular conductors are required. For floating dummy conductors, the potential is unknownand the total charge is zero. We embed these requirements into the extractionlinear system. Thus, the equivalent capacitance matrix is solved directly. The numberof system solves needed is equal to the number of regular conductors.Based on a sensitivity analysis, we propose the selective coefficient enhancementmethod for increasing the accuracy of selected coupling or self-capacitances withonly a small increase in the overall computation time. This method is desirablefor applications, such as crosstalk and signal integrity analysis, where the couplingcapacitances between some conductors needs high accuracy. We also propose thevariable order multipole method which enhances the overall accuracy without raisingthe overall multipole expansion order. Finally, we apply the multigrid method tocapacitance extraction to solve the linear system faster.We present experimental results to show that the techniques are significantlymore efficient in comparison to existing techniques.