Integral Equatation Based Parameter Extraction For Interconnect Structures And Fast Algorithms Integral Equatation Based Parameter Extraction For Interconnect Structures And Fast Algorithms

This dissertation mainly deals with the integral equation based solution for parameter extraction of interconnect structures in high-speed integrated circuits,including the modeling of lossy conductors and the fast algorithms based on H-matrix.The dissertation detailedly discusses the boundary integral equation based solution for 2-D distributed parameter extraction,the electric filed integral equation based on the equivalent surface impedance for parameter extraction of 3-D interconnects,the optimized H-matrix for accelerating the electromagnetic simulation of interconnect structures and the purely algebraic nested cross approximation of linear complexity for the construction of H2-matrix.The main contribution of this dissertation is summarized as follows:1.Starting from the quasi-static form of the Maxwell's equation,the boundary integral equations for the 2-D interconnect structures are discussed in detail.The distributed parameters of the interconnects are derived through the relation between the electric current and the vector potential,and the equal potential distribution of the voltage.2.The equivalent surface impedance is built according to the solutions of the electric field and equivalent surface current distribution based on boundary integral equations.The boundary integral equations based equivalent surface impedance at the high frequency and low frequency are analyzed to make comparisons with the classical physics models to verify the correctness.The combination of the equivalent surface impedance and the electric field integral equation are adopted to extract the impedance parameters of the 3-D interconnect structures.3.The H-matrix algorithm is adopted to accelerate the overall solution of integral equations.The numerical formulation and low-rank compression representation of the hybrid cross approximation in different types of surface integral equations are derived.The efficiency of both the hybrid cross approximation based H-matrix and the adaptive cross approximation based H-matrix are compared to verify the efficiency.4.The optimized H-matrix algorithms are studied for both the 2-D distributed parameter extraction and the parameter extraction of 3-D interconnect structures.For the 2-D distributed parameter extraction,the special form of cluster tree is built.The optimization of the post-process for H-matrix are adopted to achieve the optimal computational complexiy.For the parameter extraction of 3-D interconnects,the construction of the balanced binary cluster tree and the bottom-up method to update the distance between clusters are introduced.According to the relative error from the analysis of the polynomial interpolation method,the relative rough pattern of the rank's growth rate is studied to design the auxiliary inspection condition and the extended admissibility condition.The comparisons between the optimized and conventional H-matrix are made to verify the efficiency.5.The purely algebraic nested cross approximation of linear complexity for the construction of H2-matrix is studied.Starting from the perspective of the adaptive cross approximation and the combination of the two approaches for representing low-rank matrices according to row index and column set,the nested cross approximation is derived with very clear mathematical meaning.The two-stage pivot selection method is studied for the construction of nested bases,which contains the bottom-up traverse and top-down traverse.The two-stage pivot selection method achieves linear complexity with controlled accuracy for interconnect or electrically small-size problems.The computational complexity are verified with several numerical examples.This dissertation systematically studies the integral equation based solution for parameter extraction of interconnect structures,and the related fast algorithm for accelerating the solution of integral equations,aiming at providing numerical solver and tools for the fast modeling of high-speed integrated circuit with advanced process node.