一种基于网格的芯片布局密度控制方法

摘要：物理设计中，布局密度过高导致的拥塞是一直不可避免的问题.本文提出了一种基于网格划分的密度控制方法来改善EDA工具在自动优化拥塞方面的局限性，以Synopsys公司的后端工具IC Compiler为主要实验工具，通过将目标模块划分成网格（grid）的形式，分析每个网格内的布局密度信息，对可能出现拥塞的区域通过算法进行控制，以达到减少并解决布局拥塞的目的.实际工程试验表明，该方法可以有效地解决模块中由于布局密度过高引起的拥塞问题，同时改善了设计时序，具有较高的工程价值和实用性.

关键词：网格划分；布局密度；拥塞控制

中图分类号：TN47 文献标识码：A

A Method of Controlling Chip Layout Density

Based on Grid Division

HE Xiao-wei1， HAN Yu1， WANG Dong2， ZHAO Zhen-yu1

（1. College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China；

2. Scientific Research Dept， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： In physical design， local high density issue always results in place and routing congestion problems. This paper presented a method of controlling chip density based on grid division in order to alleviate the drawbacks of congestion-driven optimizations by EDA tools. This paper used Synopsys IC Compiler as major experiment tool， divided the design block into several grids， and analyzed the layout-density information within each grid to control and optimize the possible congestion areas. Meanwhile， the design timing has also been improved. The effectiveness and feasibility of this strategy has been verified with actual project examples.

Key words： grid division； layout density； congestion control

随着半导体技术的发展，每一代工艺大体上将有效沟道长度降到前一代的0.7倍，芯片集成度极大地提高[1].在后端设计中通过EDA工具对标准单元进行布局时，这些单元并不会均匀地分布在芯片上，而是会根据逻辑划分、时序优先等布局引导来被放置.这就会导致在逻辑模块交汇或布线通道附近等时序关键区域被摆放大量单元，而芯片的四周边角的区域却只有少量单元[2].这使得在后端设计过程中，随着优化的进行，各种优化单元的不断插入，芯片在总体单元利用率不是很高的情况下也会出现局部布局密度过高的情况，从而产生拥塞.

拥塞通常出现在时序关键区域，这种区域在布局阶段摆放的单元数目就很多，在后续优化阶段还会插入大量的单元，所以极易形成拥塞，导致绕线、电迁移、功耗密度不均匀甚至无法继续优化等问题，严重影响了芯片的性能和稳定性；同时局部单元数目过多也会导致局部线网密度提高，这对芯片的可制造性也将产生极大的影响，所以如何解决拥塞问题一直是集成电路设计中的重要课题[3].

本文以Synopsys公司的后端工具IC Compiler为主要实验工具，主要通过将目标模块划分成网格（grid）的形式，分析每个网格内的布局密度信息，对可能出现拥塞的区域进行控制与优化，以达到减少或解决布局拥塞的目的.实际工程证明，该方法可有效解决芯片布局密度过高引起的拥塞问题，极大地减少了设计过程中的迭代次数，缩短了设计周期.

1 布局拥塞概述

虽然设计流程中在逻辑综合阶段会进行拥塞的优化，但是在后端设计过程中依然会不可避免地出现拥塞问题.如果要用更加准确的算法来控制后端流程中可能出现的拥塞情况，就必须了解在后端流程的不同阶段可能会影响到布局密度变化的情况.

在后端设计流程中，常常因为优化而需要插入或者改动单元，从而导致布局密度升高.这也正是在逻辑综合时无法预估到物理设计后期拥塞分布的原因.可能造成设计出现布局拥塞的情况包括：标准单元的尺寸变动；插入普通缓冲器或时钟单元，时钟单元具有相同的上升和下降时间，在时钟树综合时可以使时钟信号获得较好的占空比（duty cycle）[4]；插入延时单元；插入防闩锁单元等.

为适应芯片设计的需要，人们在分析标准单元通道布线结构的基础上发明了新的启发式算法，并将其应用在EDA工具中，逐渐发展成拥塞驱动的布局算法，包括基于网格[5]和非基于网格[6]两类.这两类算法都以互连线为中心，在初期布线有很高的成功率.但其对单元摆放的控制太宽泛，不能有效地约束关键区域的布局密度，导致在后期布线时，特别是对于长路径和布局密度高的区域，布通率下降明显.

随着IC设计水平的提升，物理设计中已经有很多趋于成熟的策略可以用来解决设计过程中出现的拥塞问题.根据执行者的不同，将其分为工具优化和人工优化两种.

人工优化一般分为两种，一种是在布图规划阶段通过合理摆放宏单元，设置布局/布线屏蔽层等方法来预防拥塞的发生；另一种则是在布局之后的阶段，通过删除冗余缓冲单元、减小单元尺寸、利用公共路径插入缓冲单元等方法来解决拥塞问题.第一种方法的准确度不高，往往要经过数次迭代才能找到合适的方案；第二种方法面向的对象可具体到每一条路径、每一个单元，准确度极高，但非常依赖于布局，优化空间较小，并且当出现大规模拥塞的情况时，过于精细的分析反而使得优化周期极大地增加.

因此如何结合两种方法的优势，进一步加强对密度的控制是具有较高工程价值的研究.本文通过划分网格的形式，在EDA工具算法的基础上加强对局部密度的控制，其中的拥塞预估将优化过程中插入的延时单元面积考虑在内，大大地增加了预估结果的准确性.

2 理论研究与算法实现

2.1 网格划分

将物理设计的模块划分为网格形式（如图1所示），每个网格都包含一定的标准单元，通过指导布局过程使得布局拥塞度与特定的网格相关，从而达到控制局部密度的目的.

在布局的初始阶段就需要确定网格的划分，划分网格时应遵循以下原则：

1）网格之间应该相互紧贴，并且不能重叠.

2）网格应当覆盖该设计模块的所有单元布局区域.

3）从算法复杂性考虑，尽量保证划分的所有网格大小一致.

对于网格的面积，主要从两方面考虑：第一是网格面积对后续优化准确性和效果的影响，第二是对优化过程中插入的延时单元输出翻转时间的影响.这两点若不分析清楚，将会使得后续优化算法的实用性大打折扣.

从计算复杂性和误差考虑，网格面积划分得越大越好，但过大的网格会由于优化时其内部插入的延时单元距离目标寄存器太远而产生翻转时间违例.所以必须根据延时单元的驱动能力来限制网格面积.在实际设计中应权衡两者关系做出最优选择.

2.2 布局密度预估与控制

对于一个已经完成标准单元放置的布局，其局部密度的定义为：

db（ei） = Cb（ei） /Ab（ei）.（1）

式中：Cb（ei）为分配在某一个网格ei中的标准单元总面积；Ab（ei）为该网格的面积.

最大密度的定义为：

D（B） = max db（ei），i = 1，2，…

布局的目标是在不影响时序的前提下，尽量令D（B）最小化，即让标准单元均匀分布，以减少局部拥塞率.

仅仅对布局之后的密度进行分析的效果并不理想，因为标准单元放置完毕之后，还未进行时序优化.由于无法预估到未来进行时序优化时网表的变动，所以不能判断每个网格在之后优化过程中的密度变动.若在此时通过分析局部密度来设置约束，只有两种办法：

1）仅对已经确定密度较高的网格设置约束，其优点是准确性高，对时序基本没有影响；缺点是约束的网格数量少，对密度的控制力度较小.

2）对全部网格都设置密度约束，优点是对密度的控制效果明显，可以看成是所有单元被均匀分布在模块的每个网格内，基本保证每个区域内都有空间进行后续优化；缺点是约束的网格较多，单元容易被布局屏蔽层推得过于分散，对时序影响较大.

这两种方法虽然都可以做到密度控制，但是也都存在明显的不足.所以我们要进行更加有效的干预，就必须对密度过高的原因进行更细致的分析.

在物理设计流程中，EDA工具在优化过程中为了修复建立时间和保持时间违例会插入不同类型的缓冲单元，虽然我们不能预估建立时间优化时插入的缓冲单元的位置，但在修复保持时间违例时，特别是在修复扫描模式的保持时间阶段，插入的缓冲单元却是可以预先判定位置的.因此，可以在布局之后提取设计中所有寄存器的位置信息，然后根据每个网格内含有的寄存器数目计算出该网格在修复保持时间时可能需要的空间，将这个信息和密度综合成新的拥塞预估标准.

由式（1）知道，对于网格ei，其局部密度为db（ei） = Cb（ei）/Ab（ei） ，设网格ei内有N个寄存器，为每个寄存器在修复保持时间时预留的空间为K，所以，对于该设计中的网格，其局部单元拥塞度的定义为：

Con（ei） = db（ei） + N（ei）K/Ab（ei）.

综合可得：

Con（ei） = [Cb（ei） + N（ei）K]/Ab（ei）.（2）

对于网格ei而言，其局部单元拥塞度为布局完成之后，该网格内所有单元的面积及为网格内部所有寄存器预留面积之和与网格总面积之比.

使用式（2）定义的局部单元拥塞度作为布局阶段的网格密度评估标准，比之前使用的式（1）更加精确，不但从局部密度来分析单元拥塞，而且考虑到了修复保持时间违例时的拥塞来源，增强了布局对流程后期的拥塞影响.新的最大单元拥塞度的定义为：

Con（B） = max [db（ei） + N（ei）K/Ab（ei）]，i = 1，2， …

可以看出，如果要让Con（B）最小，不但要将标准单元分布均匀，还要避免某一区域寄存器分布过多.这样等于将时序关键区域的单元均匀扩散，保证了优化的空间.

2.3 算法实现

基于网格的密度预估布局所采用的算法只需要通过预估，得到每个网格的局部密度即可.具体的算法实现步骤如下：

1）设计文件输入以及布局.首先要有一个已经确定的布局来避免迭代.将输入信息读入EDA工具，并进行标准单元摆放.对已经摆放的标准单元进行时序优化和物理位置优化，使得初始寄存器的位置基本固定.

2）网格划分.在标准单元布局完成之后，就可以开始网格的划分.根据网格划分的原则来划分网格，保证网格覆盖整个模块.值得注意的一点是，将网格的垂直长度设置成单元区（row）的整数倍，可以减少复杂度并提高准确性.

3）网格拥塞计算.在网格划分完成后，开始计算网格的拥塞度.从第一个网格开始计算，通过面积坐标信息将该网格内的单元提取出来，然后将处于网格内的单元面积进行累加，最后除以网格总面积，即可得到网格的当前密度db（ei）.对于预估的面积N（ei）K也采用同样的方法.通过坐标判断寄存器是否在当前网格内，如果不在就跳过该寄存器，如果在，则当前网格内寄存器数目加1，直到所有寄存器遍历完毕.在得到当前网格的布局密度和寄存器数目之后，即可进行下一网格的拥塞计算.

4）设置约束.对于处在中心区域布局密度较高的网格，可以设置较严格的布局约束；对于处在边角非关键区域、布局密度很低的网格，可以设置较宽松的约束或者不用设置约束.

具体的约束标准是以网格内的寄存器数目为标准的.拥有较多寄存器的网格意味着在未来优化中可能入更多的单元.对于一个拥塞度为Con（ei） = db（ei） + N（ei）K/ Ab（ei）的网格，需要预留的面积通常为N（ei）K的1.3～2.1倍，可根据不同的需求来进行设置.

最后将约束信息输出成tcl脚本形式，以便在下一步中应用.

5）重新布局.在约束设置完毕后，需要重新布局及摆放标准单元.在布局阶段读入上一步中生成的设置脚本，使得新的单元摆放遵循约束规范.

6）拥塞检查.在新的布局生成之后，还要对该布局进行一次拥塞检查.目的是防止一些在第一次布局中没有注意到的网格在第二次布局后产生拥塞.

以上6步完成之后，基于网格的密度控制布局就完成了，详细的算法流程图如图2所示.

3 实验结果

实验实例为一个百万门级的设计模块，该模块面积为1 380 μm×1 300 μm，含有58 776个寄存器，161 236个标准单元，时钟周期为700 ps.虽然该模块布局阶段的单元利用率并不高，但是由于单元摆放不均匀，在中间区域集中了80%以上的单元，而周围区域只摆放了一些与I/O引脚有关的单元，所以在优化过程中仍然可能出现拥塞.我们采用两套流程对该模块进行后端设计，不同点在于第一套流程在布局阶段的脚本中嵌入了本章研究的布局密度控制脚本；另一套流程采用的是正常后端设计的脚本，在每个阶段都会进行一次EDA工具自带的拥塞优化.

为方便对比，两套流程中均不采用任何ECO手段.首先对模块进行网格划分，分割成21×20共420个网格，每个网格面积为65.52 μm×65 μm = 4 258.8 μm2，网格划分之后的模块如图3所示.

下面分别给出了两套流程在不同阶段每个网格的拥塞度对比以及静态时序分析的报告.为了更清楚更直观地分析不同阶段的局部拥塞，将网格拥塞度以散点图的形式表现出来，图4和图5分别为两套流程在布局阶段局部拥塞度对比.图中横坐标为网格内的局部密度，纵坐标为网格内的寄存器数目，每一个散点代表一个网格，从图中可以清楚地看到每一个网格区域的布局密度与寄存器数目.

图4为该模块使用正常流程时，在布局之后的各网格拥塞度情况.可以看到，在布局阶段，大部分网格的布局密度已经接近0.8，一些网格的布局密度甚至已经超过0.9.图5为采用密度控制之后的布局拥塞示意图，可知在通过对布局密度较高和寄存器密集区域进行了控制之后，大部分网格的布局密度降低到了0.6左右，只有少数网格超过0.8，效果非常明显.同时网格内寄存器数目的最大值也从350左右减少到了不到300，max Con（B）降低了11%.

违例后，模块布局密度有了较大的增加.图6中大部分网格的布局密度都达到或接近1，这些网格所包含区域的布局空间趋于饱和，并且可能已经产生拥塞.图7为采用了密度控制的流程在签核阶段的拥塞示意图，可看到虽然布局密度同样有大幅提升，但大部分网格的布局密度维持在0.9左右，即在这些区域仍有10%左右的空间可供使用，说明这些区域尚未产生拥塞.

下面我们将两套流程在签核阶段的时序结果进行比较.表1为该模块在签核阶段的PT时序报告，其中func和shift分别代表功能模式和扫描模式；后缀为max的端角为检查建立时间的端角，后缀为min的端角为检查保持时间的端角；WNS代表最关键路径的违反时间；VPN代表关键路径的条数.

从表1的时序报告中可看出，该模块在使用常规流程完成签核阶段优化后还有将近30 000条保持时间的关键路径没有被修复.这是由于在该阶段出现了明显的拥塞问题.没有足够空间进行保持时间修复. EDA工具本身的拥塞优化不但未能解决问题，反而影响到了模块的建立时间，优化已经无法继续进行，只能回到布局阶段甚至将网表重新综合后再进行新的流程.

而采用了密度控制的流程在该阶段很好地完成了优化任务，所有模式下的保持时间已经基本修复完毕，而且建立时间也没有出现大幅度的恶化.后续只需要进行一些ECO的时序优化，就可以令时序收敛达到签核的标准.

通过以上的实验结果以及图表分析，可以很清楚地看到密度控制在实际后端流程中的作用.在布局阶段进行密度控制之后，完全避免了后续阶段的拥塞问题，减少了迭代的工作，缩短了设计周期.

4 结 论

本文针对物理设计中EDA工具对芯片布局密度控制不力从而容易导致产生拥塞的问题，提出了一种通过将布局区域划分为网格形式来加强对局部掌控的布局密度控制算法.实际工程试验结果表明，该算法可以较好地解决芯片的布局拥塞问题，减少物理设计流程中的迭代次数，缩短了设计周期.

参考文献

[1] 赵继业， 杨旭.纳米级工艺对物理设计的影响[J].信息技术快报，2008，6（2）：25-34.

ZHAO Ji-ye， YANG Xu. The affect of nano-process to physical design[J]. Information Technology Letter， 2008，6（2）：25-34. （In Chinese）

[2] MARKOV I L. Capo： congestion-driven placement for standard cell and RTL netlists with incremental capability[D]. Ann Arbor， Michigan： University of Michigan， 2010： 99-110.

[3] 唐有情.纳米级工艺下系统级芯片的物理设计[J].中国科技信息，2010（5）：50-51.

TANG You-qing. The physical design of system-on-chip in nano-process[J]. China Science and Technology Information， 2010（5）：50-51.（In Chinese）

[4] TSMC.90/80/65/55/45/40nm standard cell library application note（Version 1.9）[R].Xinzhu： TSMC， 2009.

[5] YANG B， YU J， YAN T， et al. An obstacle detoured routing algorithm based on the enhanced ACS[C]// Proceedings of 2004 International Conference on Communications， Circuits and Systems.Washington， DC： IEEE Computer Society， 2004：1286-1289.

[6] CONG J， FANG J， KHOO K Y. DUNE―a multilayer gridless routing system[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2001，20（5）：633-647.