一种改进的IC互连线3D电容提取快速层级算法

An Improved Fast Hierarchical Method for Three-Dimensional Capacitance Extraction of IC Interconnects

快速层级算法(FHM)是边界元法求解3D电容积分方程的一种加速方法,该方法基于分层近似对电势系数矩阵隐式表示,使求解的时间复杂度降低到O(n).改进算法对FHM做了两点改进:(1)给出了分层近似的理论依据,这种分层依据适用于所有导体结构而无需重复试验.(2)利用层级关系,直接计算面电荷,避免了迭代过程,加速了电荷求解.一系列典型3D互连线结构的测试显示:改进后的算法不仅提高了求解精度,而且计算时间也减少到改进前的1/3.

An improved fast hierarchical method （IFHM） for three-dimensional （3-D） capacitance extraction of IC Interconnects is presented. The fast hierarchical method （FIIM） has been utilized for acceleration of the boundary element method （BEM） in solving the integral equations associated with the 3-D capacitance extraction problem. However, there is a shortcoming of the original FIIM method： the criterion for hierarchical approximation is not explained and lack of theoretical support. The criterion plays a key role in the tradeoff between acceleration and precision.In the original FHM method the hierarchical approximation criterion was gained by a trial-and-error scheme. Here, specific and quantitative criterion is proposed in this improved FHM method. In addition, a new effective hierarchical scheme for charge evaluations is also proposed. The IFHM results in higher accuracy with about 1/3 computational time than the original FHM. Numerical examples are included to demonstrate the efficiency of this proposed IFHM.