【作者】 赵宇；

【导师】 毛军发；

【作者基本信息】 上海交通大学 ， 电子科学与技术， 2018， 博士

【摘要】 本论文主要研究基于积分方程的高速集成电路互连参数提取问题,包括有耗导体的建模和基于H-matrix的核无关快速算法。论文详细论述了基于等效表面阻抗的电场积分方程提取三维互连参数,提出优化的H-matrix算法加速二维互连分布参数和三维互连参数提取,以及纯代数的线性复杂度嵌套交叉近似算法。论文主要工作概述如下:1.从准静态近似的麦克斯韦方程组出发,详细介绍了二维互连结构的边界积分方程。利用电流与矢量磁位的关系以及互连线截面上的电压等势分布,得到互连线的二维互连分布参数。2.提出基于边界积分方程的等效表面阻抗模型。以边界积分方程为基础,求解导体边界上的电场与等效表面电流分布,构建等效表面阻抗模型。分析了基于边界积分方程的等效表面阻抗在高频和低频极限情况下的值,并与经典物理模型做对比,验证其正确性。将等效表面阻抗模型与电场积分方程相结合,用于提取三维互连结构的参数。3.针对互连参数提取问题,选择H-matrix算法加速整个求解过程。探索了混合交叉近似算法在表面积分方程中的应用。详细推导了混合交叉近似用于不同类型表面积分方程的计算公式和具体的矩阵表示方法。将基于混合交叉近似和自适应交叉近似的H-matrix的计算效率进行比较,验证了算法的高效性。4.提出适用于二维互连分布参数和三维互连参数提取的优化H-matrix的方法。对于二维互连分布参数提取问题,构建特殊形式的指标树结构,并对H-matrix采用后处理的优化方法,使得整体的计算复杂度达到最优。对于三维互连参数提取问题,提出平衡二叉指标树的构建方法以及自底向上更新分块之间距离信息的方法。根据多项式插值近似矩阵元素的相对误差,分析低秩矩阵的秩的增长规律,并提出判断矩阵低秩特性的辅助检验条件和扩展可容性条件。将优化的H-matrix与传统H-matrix的效率作对比,验证了算法的高效性。5.提出了纯代数的线性复杂度嵌套交叉近似算法用于构建H2-matrix。从自适应交叉近似的角度出发,结合低秩矩阵按照行指标和列指标近似的两种形式,得到嵌套交叉近似的表示形式。针对嵌套交叉近似中的主元选择问题,提出两阶段的纯代数方法,分别对指标树进行自底向上和自顶向下的遍历过程。在理论上证明对于互连参数提取或电小尺寸的问题,两阶段的主元选取方法在保证计算精度的条件下达到线性的计算复杂度。最后,通过若干算例对算法的可靠性和计算复杂度进行了验证。本论文比较系统地研究了基于积分方程的互连参数提取方法,以及适用于加速求解积分方程的快速算法,为先进工艺节点下的高速集成电路的快速建模提供数值求解方案和工具。更多还原

【Abstract】 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.更多还原