This thesis describes a divide-and-conquer algorithm to improve the 3D boundary element method (BEM) for capacitance extraction. We divide large interconnect structures into small sections, set new boundary conditions using the borderfor each section, solve each section, and then combine the results to derive the capacitance. The target application is critical nets where 3D accuracy is required. The new algorithm is a significant improvement over the traditional BEMs and their enhancements, such as the "window" method where conductors far away are dropped, and the "shield" method where conductors hidden behind other conductors are dropped. Experimental results show that our algorithm is 25 times faster than the traditional BEM and 5 times faster than the window+shield method, for medium to large structures. The error of the capacitance computed by the new algorithm is within 2% for self capacitance and 7% for coupling capacitance, compared with the results obtained by solving the entire system using BEM. Furthermore, our algorithms gives accurate distributed RC, where none of the previous 3D BEM algorithms and their enhancements can.

This thesis describes a divide-and-conquer algorithm to improve the 3D boundary element method (BEM) for capacitance extraction. We divide large interconnect structures into small sections, set new boundary conditions using the borderfor each section, solve each section, and then combine the results to derive the capacitance. The target application is critical nets where 3D accuracy is required. The new algorithm is a significant improvement over the traditional BEMs and their enhancements, such as the "window" method where conductors far away are dropped, and the "shield" method where conductors hidden behind other conductors are dropped. Experimental results show that our algorithm is 25 times faster than the traditional BEM and 5 times faster than the window+shield method, for medium to large structures. The error of the capacitance computed by the new algorithm is within 2% for self capacitance and 7% for coupling capacitance, compared with the results obtained by solving the entire system using BEM. Furthermore, our algorithms gives accurate distributed RC, where none of the previous 3D BEM algorithms and their enhancements can.

In this thesis, the Method of Moments has been applied to calculate capacitance between two arbitrary 3D metal conductors or a capacitance matrix for a 3D multi-conductor system. Capacitance extraction has found extensive use for systems involving sets of long par- allel transmission lines in multi-dielectric environment as well as integrated circuit package including three-dimensional conductors located on parallel planes. This paper starts by reviewing fundamental aspects of transient electro-magnetics followed by the governing dif- ferential and integral equations to motivate the application of numerical methods as Method of Moments(MoM), Finite Element Method(FEM), etc. Among these numerical tools, the surface-based integral-equation methodology - MoM is ideally suited to address the prob- lem. It leads to a well-conditioned system with reduced size, as compared to volumetric methods. In this dissertation, the MoM Surface Integral Equation (SIE)-based modeling approach is developed to realize electrostatic capacitance extraction for 3D geometry. MAT- LAB is employed to validate its e?ciency and e?ectiveness along with design of a friendly GUI. As a base example, a parallel-plate capacitor is considered. We evaluate the accu- racy of the method by comparison with FEM simulations as well as the corresponding quasi-analytical solution. We apply this method to the parallel-plate square capacitor and demonstrate how far could the undergraduate result 0C = A ? "=d' be from reality. For the completion of the solver, the same method is applied to the calculation of line capacitance for two- and multi-conductor 2D transmission lines.

With VLSI(very large scale integration) technology shrinking and frequency increasing, the minimum feature size is smaller than sub-wavelength lithography wavelength, and the manufacturing cost is significantly increasing in order to achieve a good yield. Consequently design companies need to further lower power consumption. All these factors bring new challenges; simulation and modeling need to handle more design constraints, and need to work with modern manufacturing processes. In this dissertation, algorithms and new methodology are presented for these problems: (1) fast and accurate capacitance extraction, (2) capacitance extraction considering lithography effect, (3) BEOL(back end of line) impact on SRAM(static random access memory) performance and yield, and (4) new physical synthesis optimization flow is used to shed area and reduce the power consumption. Interconnect parasitic extraction plays an important role in simulation, verification, optimization. A fast and accurate parasitic extraction algorithm is always important for a current design automation tool. In this dissertation, we propose a new algorithm named HybCap to efficiently handle multiple planar, conformal or embedded dielectric media. From experimental results, the new method is significantly faster than the previous one, 77X speedup, and has a 99% memory savings compared with FastCap and 2X speedup, and has an 80% memory savings compared with PHiCap for complex dielectric media. In order to consider lithography effect in the existing LPE(Layout Parasitic Extraction) flow, a modified LPE flow and fast algorithms for interconnect parasitic extraction are proposed in this dissertation. Our methodology is efficient, compatible with the existing design flow and has high accuracy. With the new enhanced parasitic extraction flow, simulation of BEOL effect on SRAM performance becomes possible. A SRAM simulation model with internal cell interconnect RC parasitics is proposed in order to study the BEOL lithography impact. The impact of BEOL variations on memory designs are systematically evaluated in this dissertation. The results show the power estimation with our SRAM model is more accurate. Finally, a new optimization flow to shed area blow in the design synthesis flow is proposed, which is one level beyond simulation and modeling to directly optimize design, but is also built upon accurate simulations and modeling. Two simple, yet efficient, buffering and gate sizing techniques are presented. On 20 industrial designs in 45nm and 65nm, our new work achieves 12.5% logic area growth reduction, 5.8% total area reduction, 10% wirelength reduction and 770 ps worst slack improvement on average.

Fast and accurate solvers for capacitance extraction are needed by the VLSI industry in order to achieve good design quality in feasible time. With the development of technology, this demand is increasing dramatically. Three-dimensional capacitance extraction algorithms are desired due to their high accuracy. However, the present 3D algorithms are slow and thus their application is limited. In this dissertation, we present several novel techniques to significantly speed up capacitance extraction algorithms based on boundary element methods (BEM) and to compute the capacitance extraction in the presence of floating dummy conductors. We propose the PHiCap algorithm, which is based on a hierarchical refinement algorithm and the wavelet transform. Unlike traditional algorithms which result in dense linear systems, PHiCap converts the coefficient matrix in capacitance extraction problems to a sparse linear system. PHiCap solves the sparse linear system iteratively, with much faster convergence, using an efficient preconditioning technique. We also propose a variant of PHiCap in which the capacitances are solved for directly from a very small linear system. This small system is derived from the original large linear system by reordering the wavelet basis functions and computing an approximate LU factorization. We named the algorithm RedCap. To our knowledge, RedCap is the first 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 among regular conductors are required. For floating dummy conductors, the potential is unknown and the total charge is zero. We embed these requirements into the extraction linear system. Thus, the equivalent capacitance matrix is solved directly. The number of system solves needed is equal to the number of regular conductors. Based on a sensitivity analysis, we propose the selective coefficient enhancement method for increasing the accuracy of selected coupling or self-capacitances with only a small increase in the overall computation time. This method is desirable for applications, such as crosstalk and signal integrity analysis, where the coupling capacitances between some conductors needs high accuracy. We also propose the variable order multipole method which enhances the overall accuracy without raising the overall multipole expansion order. Finally, we apply the multigrid method to capacitance extraction to solve the linear system faster. We present experimental results to show that the techniques are significantly more efficient in comparison to existing techniques.

The method of moment (MoM) [1] is a widely used method in electromagnetics to solve static and dynamic electromagnetic problems on varying geometries. However, in closely spaced geometries coupled with large aspect ratios, e.g. a large parallel plate capacitor with very small separation gap, the problem exhibits several challenges. Firstly, the close proximity of the field and source elements presents problems with convergence in numerical evaluations of the interactions between them. Secondly, the aspect ratio of the geometry gives an approximation whereby to far field points, the source contributions from locations that are far apart appear to cancel each other. This leads to high condition numbers in the system matrix. This thesis explores the potential solution to these problems as well as the application of modular fast and direct (MFD) [2] solver to expedite the solution of such problems.