芯片规模大结构RC寄生参数提取和低阶建模

翁辉耀

摘 要：研究了芯片规模大结构RC寄生参数的快速提取方法，然后提出一种模型降阶方案。由于提取寄生电容过程需要考虑周围临近的互连线，芯片级集成电路有着千兆级以上的互连线，故需要一个相对优化的结构能够快速准确地找出符合条件的互连线，从而加快电容的提取的速度。因此介绍了各个空间管理结构（K-D树， 八叉树， 网格划分），进行深入研究并给出一个优化方案，上层四叉树下层K-D树将获得较优的速度和使用较少的内存。

关键词：寄生参数提取；空间管理结构；模型降阶

中图分类号：TN405 文献标识码：A 文章编号：1671-2064（2018）21-0022-03

当下，随着芯片的设计越来越复杂，互连线的长度越来越长，数量越来越多，互连线之间的电磁耦合问题已成为电路设计中日益困难的问题。超大规模集成电路互连线的布线层数一般在8层及以上，故互连线带来的延迟和寄生参数问题影响到电路性能，成为芯片设计首要考虑因素。IC设计也逐渐由以前的以逻辑功能为中心的模式变成功能与互联性能并重的模式，设计的重点也逐渐由前端向后端转移[1-2]。

1 互连线寄生参数基本理论

1.1 互连技术概念

所谓的互连技术，就是在集成电路芯片制造过程中，将各个独立的元器件通过金属线通孔等一定的方式，把它们连接成具有一定功能的电路模块的一种技术。

在现代的高速超大集成电路芯片设计中，对信号经过互连线后所产生的效应进行准确地定性定量地分析，仿真计算出结果并加以优化控制已经成为相应计算机辅助设计工具关注的主要问题之一。随着芯片规模越来越大，芯片面积却越来越小，芯片设计者分析信号经过互连线后所产生的效应的难度和准确性要求不断提升。如果能够精确地提取到互连线寄生参数，就可以对电路进行精确地综合模拟，从而发现设计问题，进行性能优化地布局布线，消除互连效应。故一种快速的提取互连线寄生参数的方法，对于优化集成电路设计有着十分重大的意义。

1.2 互连线寄生电阻提取

根据金属导线电阻计算公式：

R=ρL/S=ρL/HW

以上公式中：ρ是物质的电阻率，其单位是欧姆米（ohm*m）。L是长度，其单位是米（m）。S是截面积，其单位是平方米（m2），S可以通过导线的高度乘以宽度计算出。根据公式可以推导出，每个单元截面的传输线单位长度的电阻与频率无关。

1.3 互连线寄生电容提取

当前比较精确的三维寄生电容提取方法主要有：边界元法[3-5]、半解析方法[6]、MEI[7-9]方法和随机漫步法[10]。

因芯片内互连线数据量巨大，大部分场效应求解电容提取方法不适合实际应用于芯片规模大数据结构。所以在工作实践中，利用平行板电容公式来计算寄生电容的方法以求简化，并考虑边缘效应的误差量和周边环境的误差量，以达到快速提取电容的目的。介绍寄生参数提取方法前，先对传统的平行板电容结构及概念进行说明：

电压：V=φ1-φ2

Q和-Q在上下板上，Q和V成比例。

比率被定義为C：C=Q/V。

如果板的面积比两板之间的距离d大得多，有：

，

对于有限长的矩形平板，需要考虑平行板电容器的边缘效应。已有计及边缘效应时平行板电容器的电容值[11]。结果如图1所示。

C0是考虑边缘效应实际电容值，C是理想电容值，h是极板的宽度，d是两板的距离。

从图上可知：在h/d=16.644时，C0/C=0.901。故只要极板宽度与间距之比大于16.644，用平行板电容器公式误差不超过10%。

1.4 模型降阶及简化

随着工艺提升，集成电路设计越来越复杂，互连线也就越来越长，条数越来越多。相对的寄生参数提取的等效矩阵也将越来越大，大大影响了计算的效率，不利于仿真分析。以现在的计算机的能力，对如此多的等效模型直接进行分析已基本不可能。必须要找到一种模型降阶及简化技术，使之能够正确的对寄生参数提取的整体结果进行分析，得出较为正确的结果。

模型降阶的本质，是在保证精度的情况下，把复杂的系统简化为一个等价的简单的系统，以达到简化模型，加速计算的目的，从而能够高效准确地对原问题求解。

模型降阶的内容包括，根据提取的各个节点之间的寄生参数列出方程组，然后求解这些方程组，建立描述电路特性的简单又精确的宏模型。对于如何利用计算机快速并且运用较少内存地求解线性代数方程组，这是一个纯数学应用问题，这也是一个很经典的问题，已经有很多关于计算机求解线性代数的研究，研究已比较成熟。

本文采用改进节点分析法（Modified Nodal Approach）进行电路方程的建立。节点法有一些存在的问题，改进节点法克服了这些问题。在节点法电压作为方程未知变数外，还添加了支路电流作为新的未知变量。在保持原节点法的方程阶数低、方法简单的优点的同时，克服了节点法不能直接处理独立源支路、阻抗为零支路以及流控器件的弱点。正因为此，改进节点法得到了广泛的应用。许多知名的工具都是采用这个方法列方程的，例如美国著名的电路模拟程序SPICE[12]。而后用基于可观测标准型的模型降阶算法（Model Order Reduction using Observability Canonical form）建立简单的宏模型，进行模型降阶。

2 空间管理结构与方法

基于平行板电容公式算法，对于寄生电容提取过程中，需要快速找出当前金属线所最临近的金属线或通孔，需要找出快速找出当前金属线固定距离范围内的所有的金属线和通孔，用以计算寄生电容。由于互连线数量众多（千兆级别），通过遍历查找花费了过多的时间，不太合适，需要一种优化的数据结构，保存互连线数据用以查找临近线，以达到加快寄生电容提取的速度。

2.1 K-D树

K-D树（k-dimensional树），是一种可以在K维数据空间的进行快速查找的数据结构。K-D树是二进制空间分割树的特殊的情况，是对于二叉树的拓展。二叉树是对于一维空间一种有效的快速排序及查找的数据结构，K-D树是对于多个维度的二叉树以各个维度循环排序的方式进行排序和查找的数据结构。

研究中，由于互连线多为矩形（多边形亦可拆分成多个矩形），拟用四维K-D树，对芯片数据建立查找模型：

第一维：矩形左下角x坐标；

第二维：矩形左下角y坐标；

第三维：矩形右上角x坐标；

第四维：矩形右上角y坐标。

K-D树模型在建立二维空间的互连线查找模型中的优势是十分突出的。它使用内存少，建立时间短，查找时间短。缺点是在维度比较深的时候，运行速度会降低。

2.2 八叉树

八叉树（Octree），是针对在三维空间中的点的一种有效的划分方法，三维空间分割恰是2^3=8，对于一个节点不是0个元素就是8个元素，对于这8个元素可以再继续分割直至元素数量可被接受。

由于芯片设计是二维模型，所以芯片建模可以利用四叉树。由于互连线是矩形，如果有多个互连线穿越多个象限，会有一些重复数据需要保存，使用的内存相对于K-D树就会更多。

2.3 网格划分

即把空间分割成等距离的小块，例如1um。每个小块中存放对应的数据。查找时，查找范围内对应小块直接取出或一一比较即可。这种方法相当于只有一层的n*m叉树（n和m为横向和纵向的网格数）。

此方法，和四叉树同理，如果有多个互连线穿越多个区域，会有一些重复数据需要保存，使用的内存相对于K-D树就会更多，甚至多过八叉树。因查找时，需要经历查找范围内的对应小块，故对于查找区域较大，划分较细的情况，速度会相对较慢；同时划分较粗的情况，需要遍历小块中每个数据查找，速度会相对较慢。

3 实验

为了验证空间管理结构对于提取寄生电容效率的影响，作者将建立不同的空间管理结构进行效率比较及结果的比较，来验证上一节提到的利用各种空间管理结构所带来的性能优化以及结果的准确性。

提取芯片寄生参数流程如图2所示。

实验输入数据：芯片中的物理信息及其连接关系及工艺信息。包括所有金属线（wire）物理位置信息；所有通孔（via）物理位置信息；所有节点（node）物理位置信息；每一层的工艺（tech）信息，其中包括每一层上面的电阻率，相对介电常数，层的高度，上下层信息。

实验输出数据：提取的寄生电容电阻参数信息，包括有关联的两两节点之间的寄生电容电阻数据。

处理过程：对于每一层的数据，建立空间管理结构。查找同层金属线左右两侧最近的平行金属线，分别计算与左侧、与右侧线与线的寄生电容，同理查找上层，下层最近的平行金属线，分别计算线与线的寄生电容，而后将线与线的寄生电容转换计算成点与点之间的寄生电容。

因数据量巨大，寄生电容套用平行板电容公式以求简化。

C= ε*A/D

ε是介质层的相对介电常数。A是重叠部分面积。D是两块板之间的距离。同时考虑上一章所提及的平行板的边缘效应对于实际结果的影响。芯片中的电容示意图如图3所示。

根据不同的互连线情况，各个数据结构所需要的时间是不同的。本实验使用了三个实例分别是三个有着不同互连线数目的实际电路设计。实验结果如表1所示。

经验证实验中利用各种空间管理结构的最终查找临近线的结果完全一致且正确。

对于兆级别量的互连线数据，使用遍历的方法去寻找临近线提取电容，消耗时间上远远大于使用空间管理结构的方法，所以遍历的方法不可行。

业界内主流仿真工具，对于查找临近线是使用的K-D树的数据结构。因此可以根据实验结果和K-D树查找数据结果比较，得出一些结论。

根据实验数据，对于实例1、2使用四叉树会以较多的内存得到较优的运算效率（约多用10%内存，加速40%），对于实例3上层四叉树+下层K-D树有最优的运算效率（约相似的内存使用，加速50%）。总体的结论有，在数据量不是特别大的时候（兆級别），K-D树使用较少的内存，四叉树有较快的效率；在数据量比较大的时候（百兆级别），使用上层四叉树，下层K-D树的结构能够获得较优的速度和较少的内存。

4 结语

对于文中提出的利用各种空间管理结构提高芯片级大规模寄生电容提取的效率及减少内存的方法得到了实验验证。实验使用了多种空间管理结构以及其各种组合结构进行实际比较，结果表明针对于不同情况的实例，可以应用不同的空间管理结构以获取较快的效率和较少的内存。对于互连线数量小于等于兆级别，互连线长度不长，使用四叉树空间管理结构会以多消耗一些内存的代价达到更优化的速度；对于互连线数量百兆级别，使用上层四叉树，下层K-D树结构保存数据，既能消耗不多的内存，又能得到更快的查找速度。

为获取更准确的寄生电容值，后面的研究将会更深入的考虑平行板电容器边缘效应及周围环境所造成的影响。

参考文献

[1]喻文健，王习仁.面向集成电路电阻电容提取的高级场求解器技术[M].北京：清华大学出版社，2014：1-2.

[2]陈中宪.超大规模集成电路互连线分析与综合[M].北京：清华大学出版社，2008：1-2.

[3]Keith Nabors， Jacob White， FastCap： A Multipole Accelerated 3-D Capacitance Extraction Program[J].IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN，1991，10（11）：1447-1459.

[4]Keith Nabors，Songmin Kim，Jacob White，Fast Capacitance Extraction of General Three-Dimensional Structures[J].IEEE TRANSACTIONS ON MICROWAVE THEORY AND TECHNIQUES. 1992，40（7）：1496-1505

[5]喻文健，王澤毅.三维VLSI互连线寄生电容提取的研究进展[J].计算机辅助设计与图形学学报，2003，15（1）：21-26.

[6]J Tausch，J White.A multiscale method for fast capacitance extraction[J].In Proceedings of Design Automation Conference，New Orleans.1999：537-542.

[7]K K Mei，R Pous，Z Chen，et al.Measured equation of invariance：a new concept in field computations[J]，IEEE Transactions on Antennas and Propagation.1994，42（3）：320-328.

[8]W Sun，WM Dai，W Hong，Fast parameter extraction of general interconnects using geometry independent measured equation of invariance[J].IEEE Transactions on Microwave Theory and Techniques.1997， 45（5）：827-836.

[9]EA Dengi，RA Rohrer，Hierarchical 2D field solution for capacitance extraction for VLSI interconnect modeling[J].In Proceedings of the 34th Annual Conference on Design Automation Conference，Anaheim，1997：127-132.

[10]喻文健，王习仁.面向集成电路电阻电容提取的高级场求解器技术[M].北京：清华大学出版社，2014：179-183.

[11]朱益清，徐坚宏.计及边缘效应的平行板电容器的电容计算[J].工科物理，1998，8（1）：7-9.

[12]杨华中，罗嵘，汪蕙.电子电路的计算机辅助分析与设计方法[M].第2版，北京：清华大学出版社，2008：24-25.