基于缓冲器插入的非汉娜布线优化算法

吕丽华

摘要：改進超大规模集成电路性能依靠插入缓冲器和非汉娜算法是一个有效的方案。在时间约束和互联性能要求严格的情形下，在单元布局之后使用空余空间供缓冲器插入从而优化布线拓扑。这样可以将布线最大时延最小化，从而布线成本降至最低。本算法在18μm IC 工艺中测试，可以降低约30%布线树时延，可以明显提升布线性能。

关键词：缓冲器插入 非汉娜优化 异步高阶埃尔摩算法

中图分类号：TP311.52 文献标识码：A 文章编号：1007-9416（2016）12-0137-01

1 引言

随着集成电路的规模不断提高，互联阻抗对于布线性能的影响越来越大。利用节点优化的缓冲器插入 算法是在异步高阶埃尔摩算法时延模型下将非 汉娜点优化和缓冲器插入结合起来[1]。在算法的执行过程中，非汉娜优化算法和缓冲器同步插入的操作多次迭代执行，直至结果达到最优。

2 节点优化的缓冲器插入算法

2.1 问题描述

在布线区域中预先插入一组可用的缓冲区空间作为输入，我们把这些缓冲空间中的可以被缓冲区所占用且不超过区域边界的缓冲空间叫做关键区。为了实现更优布线，当且只当关键区被一条路径穿过时，缓冲器才能插入到缓冲空间中，布线树和缓冲区之间是动态变化的。

2.2 缓冲器插入与非汉娜优化过程

在时延违反条件的约束下，为了得到拐点到连接点距离的最大值，需要将连接点尽量移动至距离点，也就是使拐点到连接点的距离最大化[2]。为了进一步减低布线成本，我们引入了缓冲器的插入技术。

2.3 四阶异步埃尔摩算法的使用

我们举例来说明埃尔摩 时延的不准确性，下面是一个5个漏点的线网。利用SPICE 传输线模型、高阶埃尔摩 公式计算结果进行了对比。分别计算了所有漏点上的时延，同时还计算了spice结果的误差时延的百分比。通过实验得知，埃尔摩 时延误差最大，它的结果远较异步高阶埃尔摩算法模型的时延差。随着布线深度的增加，这个趋势只会越来越严重。

为了提高时延模型的精确度，我们提出了异步高阶埃尔摩算法的时延模型。获取时延的时候，可以利用 RICE 算法计算出布线的时间，对Padé近似值的分母进行解析，能够得到一个在极值位置收敛的高阶多项式。反拉普拉斯变换的使用，会让我们获得一个关于埃尔摩 时延的泰勒多项式，这是关于时间域的幂指函数。时延值就利用这个收敛的、四阶的多项式来计算。经过不超过三次的反复迭代，多项式就会收敛。

2.4 算法描述

文中用到的术语做如下描述：

Ui是规定时延在漏点i的值，Tdi是漏点 i时延，Tvi为根据公式计算：Tvi=Tdi-Qi漏点i时延违反，W布线树的长度，表示一个漏点的负载电容，Bj可选的缓冲位置的缓冲区空间，α是缓冲器的加权系数，c是线路的单位长度电容值，位于布线树上是漏点的个数用n表示，m是布线树上可作为的缓冲区空间的数量，插入到布线树上的缓冲器的数量由k表示。

已知条件为：一棵布线树，它①拥有源点L0，②一组漏点L，③每个漏点的规定时延。并且已经找到了一组可用的缓冲器插入空间，以上构成一棵斯坦纳布线树，从集合L中再选择一个满足下列条件子集：

是导线成本的加权系数。公式中增加了系数和，使得缓冲器和导线成本从数量上变得具有可比性。这样做的目的是可以从理论上证明埃尔摩时延是远程控制线网时延 的上限，而实际应用中，需要对 埃尔摩 时延公式进行校正，即 乘以ln2可提高准确性。我们这里所使用的“埃尔摩时延”便是由上述方法而得到的。

2.5 算法步骤详述

算法是由两个主要步骤组成。第一步，斯坦纳异步埃尔摩算法布线树阶段，它与 SERT 布线方法类似，不同的就是由四阶 AWT 模型所取代其 埃尔摩时延模型，可得到布线树 T；行非 Hanan 优化和缓冲器插入是算法第二阶段。

在第一步中，布线树由一个源点组成，之后布线树不断生长。布线树生长的基本办法就是先找到原本未连接到布线树上的漏点，陆续将这些漏点连接到布线树的特定上，目的是为了尽量减小最大时延。

然后进行第二步的优化。该步骤的主要目的是为每个漏点找到合适的连接点以便重新连接到布线树上。这个过程可能的结果有三种：成功在一个缓冲区中插入了一个缓冲器；该缓冲区依然空闲；缓冲区由于不能导致最大时延的最小化而被舍弃。

缓冲区所处的位置可能位于多个布线片段的交叉区域，即该缓冲区所处节点具有多扇出特性。该缓冲区是否允许插入缓冲器将由每个分支上的漏点临界点的状态来决定。如果每个分支中的漏点具有十分接近的临界点，那么在该缓冲区插入缓冲器将会对所有扇出分支进行优化；否则，缓冲器会被插入在非关键漏点的分支，结果将会调配关键路径和非关键路径中负荷，使得每个路径中的负荷达到最优。

3 复杂性分析

虽然将传统埃尔摩算法被异步高阶埃尔摩算法代替，进行缓冲器插入优化，但穿越和迭代次数没有发生变化，复杂度依然为O（n）级，所以，缓冲器插入在节点优化的第一步骤中成本还是O（n4）。缓冲器插入在节点优化的第二步骤中，每个经过第一步优化的布线树具有两个迭代层，缓冲区的数目为层数的上界。综合第一步和第二部的总成本约为O（m2·n4·L/）。从公式看出，参加乘法运算的对象比m2小得多，可用空间的数目总是比线网穿越的候选缓冲区数据要多。

4 实验结果

我们用IC 和 MCM 工艺分别对以4的1倍、2倍、3倍的线网为例，测试了优化情形。从实验结果表明，18μmIC工艺中，经过节点优化的缓冲器插入算法优化，31%的布线成本可被改善；针对 MCM，33%的成本可被改善。在实验中，对具有12个漏点的线网进行了测试，通常在一分钟内可计算完成，在最坏的情况下，也只需要几分钟即可完成。总体来看，在针对全局时延的关键线网进行试验测试，计算成本合理。

5 结语

为了改进超大规模集成电路的互联性能，我们提出的非 Hanan 优化算法和同步缓冲器插入，尤其当时延约束布线资源要求非常严格的时候，该算法对优化布线性能效果明显。

参考文献

[1]Hou Huibo， Hu Jiang， Sapatnekar S S. Non-Hanan Routing[J].IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems， 1999，18（4）：436-444.

[2]Lillis J， Cheng C K， Lin T T Y， et al. New Performance-driven Routing Techniques with Explicit Area/delay Tradeoffs and Simultaneous Wire Sizing[C]//Proc. of the ACM/IEEE Design Automation Conference. [S. 1.]： IEEE Press， 1996： 395-400.