在VLSI自动布局规划产生的overlap移除算法的研究

摘要：本文介绍的是自动布局规划算法并有效的消除overlap算法的文章。该算法使用在一个增强的约束图中，在给出的固定位置，空隙以及边界约束下的宏单元消除overlap。在自动布局规划中采用模拟退火算法并采取有效措施消除摆放后的overlap。

关键词：overlap 模拟退火算法 自动布局规划

中图分类号：TP391 文献标识码：A 文章编号：1007-9416（2013）12-0129-03

1 引言

随着半导体工艺的迅速发展，目前绝大部分芯片已经采用32nm及以下工艺进行设计。因此集成电路的集成度也越来越高，集成电路已经进入超大规模集成电路（Very Large Scale Integrated circuits）时代。 超大规模集成电路20世纪70年代后期出现，其主要用于制造存储器和微处理机。超大规模集成电路及其相关技术是现代电子信息技术迅猛发展的关键因素和核心技术。超大规模集成电路的研究水平已经成为衡量一个国家技术和工业发展水平高低的重要标志，也是世界工业国家竞争最激烈的一个领域。在VLSI中其集成度一直遵循着“摩尔定律”，即以每18个月翻一番的速度急剧增加，目前一个芯片上集成的电路元件数早已远超数亿个。如此迅速的发展，除了半导体工艺技术、设备、原材料等方面的不断改进之外，设计技术的革新也是重要原因之一。这一革新技术主要表现在全面采用了电子设计自动化（Electronic Design Automation， EDA）技术。因为集成电路发展到现在已经十分复杂，要在几十平方毫米上硅片上完成线条只有零点几微米的数以亿计门器件的整个电子系统设计，依靠手工设计是完全不可能的，必须借助电子设计自动化技术和工具集成电路的发展对EDA技术不断提出新的要求，以满足日益提高的设计需求；相应地，EDA技术的发展又使得集成电路设计向着更广（产品种类越来越多）、更快（设计周期越来越短）、更准（一次成功率越来越高）、更精（设计尺寸越来越小）、更强（工艺适应性和设计自动化程度越来越强）的方向发展一个典型的集成电路设计流程，几乎在其中的每个设计环节和整个设计过程都普遍用到CAD技术和工具。其中，版图规划是一个极其重要的设计环节，也是最费时的，并且版图的优劣决定了最终芯片的性能。该阶段的设计任务是根据逻辑和电路功能要求以及工艺制造的约束条件（如线宽、线宽距等），完成电路中单元的摆放和互连，最终形成设计的掩膜图。在版图规划中布图设置是很重要的一环。布图规划算法完成的任务是在满足各项电学和工艺要求的条件下，在给定区域内（或尽可能小的区域内）互不重叠地安置电路中的所有单元，并且尽可能好地满足单元互连的要求。超大规模集成电路的布局规划作为物理设计阶段的重要组成部分近年来受到了广泛关注，其质量直接影响后续布线工作的顺利完成，乃至最终影响到电路的性能，随着布局设计过程中各种新问题的不断引入，布局规划问题较原先更加复杂，也越来越难以解决。

2 目前现状

2.1 布局算法的提出

自动化版图设计实际是在有限的区域内，寻找出一个最优的摆放结果，不仅能够把所有的单元全部放入其中，并且为后续的布局布线提供最优的结果，使最终的芯片得到最好的性能。其对应的数学问题为对合法构形空间的搜索问题。VLSI物理设计中的布局、布线等问题是高度复杂的，且其中很多问题已被证明为NP-Hard问题。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。经过前人的研究，布图规划已经被证明为是NP完全问题的数学模型。所以，布图规划是一个值得深入的课题。随着VLSI向深亚微米纳米不断推进，系统规模不断扩大，系统目标的多样化，问题空间维数随之剧增。传统的优化算法要么面临计算量爆炸（如穷举法、线性规划等），要么易陷入局部极值，无法接近全局最优解（如贪心算法等）。因此对各种新的智能优化方法的研究应运而起，先后提出了遗传算法、模拟退火法[11]等算法。各种方法各有千秋，但到目前为止，还没有任何一种方法可以有效地应用于解决VLSI物理设计中的所有问题。

对于布局规划中，特别是自动布局规划（master plan），通过对比相关算法，采用模拟退火算法。使用模拟退火算法我们可以较快的得出全局最优解。在用模拟退火算法反复迭代找出最优解时，会出现一些不可避免的重叠（overlap），这个时候我们要尽可能的消除它们，同时还要考虑模块间的距离（wirelength）以及通过的总线长（timing path）。模块间中心距离是我们布局最主要的约束条件，理论上我们要使它尽可能的小。因为在一块小小的集成电路板块中可能会有千万个单元（stand cell），它们组成了各个模块（module），为此，布局开始阶段模块在起始的温度下自由排列，随着温度的下降，当找到不错的排列组合时存档，继续寻找，直到达到最优解。模拟退火算法的基本原理是：跳出局部最优，亦称爬山解（（up-hill）当满足一定的条件时以收敛到全局最优。算法可以看成是随机和贪婪算法的结合。当然模拟退火有着坚实的数学基础，其对新解的接受概率是min{1，e-C/T}，其中C为代价函数的差，T为当前温度。开始当温度较高时，接受坏解的概率近似等于1，无论解的质量是好是坏，一律接受，可以看成是随机搜索。当温度足够低时，接受坏解的概率近似等于0，只接受好的解，可以近似的认为是贪婪搜索。在温度变化的过程中是一个从随机到贪婪的渐变过程[12]（图1）。

3 算法的改进

3.1 功能模块设计

4 运行结果与分析

对于以上改进算法的实现进行代码编写，并且在Linux操作系统开发环境下运行encounter软件，采用一组case进行实现，得到的结果如（图3、4）。

通过对实验结果的分析可以看出，改进后的算法是有效的，跟传统的布局规划相比布局线路wirelength优化了17.5%，overlap降低了12.1%，达到了实验预期的效果。

5 结语

本文主要通过对自动布局规划设计分析，提出了改进的模拟退火算法，并消除布局中不应产生的overlap。该算法中采用了自顶向下的结群策略，实验表明，该算法比较稳定，得出的结果好，适用性强。

参考文献

[1]L.Jin，D.Kim，L.Mu，D.-S.Kim，and S.-M. Hu，“A sweepline algorithm for Euclidean Voronoi diagram of circules，”IEEE put.-Aided Des.，vol.38，no.3，pp. 260-272，Mar.2006.

[2]Y.Feng，D.P.Mehta，and H.Yang，“Constrained modern floorplanning，”in Proc.ISPD，2003，pp.128-135.

[3]J.-M.Lin and Y.-W.Chang，“TCG：A transitive closure graph base representation for general floorplans，”IEEE Trans.Very Large Scale Integr.，vol. 13， no. 4， pp. 288–292，Apr.2005.

[4]X.Hong，G. Huang，Y.Cai， J. Gu，S. Dong， C.-K. Cheng，and J. Gu，“Corner block list： An effective and efficient topological representation of non-slicing floorplan，” in Proc.ICCAD，2000，pp.8-12.

[5]S.Nakatake， M. Furuya， and Y. Kajitani， “Module placement on BSGstructure with pre-placed modules and rectilinear modules，” in Proc.ASP-DAC， 1998， pp. 571–576.

[6] Richard Auletta，Expert System Perimeter Block Placement Floorplanning，” date， p. 30140， Design，Automation and Test in Europe Conference and Exhibition Designers Forum （DATE’04），2004.

[7]Y.Zhan，Y. Feng， and S.Sapatnekar，“A fixed-die floorplanning algorithm using an analytical approach，”in Proc.ASP-DAC，2006， pp.771-776.

[8]Alupoaei，S.； Katkoori，S.Ant colony system application to macrocell overlap removal，Very Large Scale Integration （VLSI） Systems， IEEE Transactions，Vol.12， Iss.10，pp.1118- 1123，Oct.2004.

[9]S.N.Adya，I.L. Markov， Fixed-outline Floorplanning： Enabling Hierarchical Design， to appear in IEEE Trans.On VLSI，2003.

[10]W.Choi and K.Bazargan Hierarchical Global Floorplacement Using Simulated Annealing and Network Flow Area Migration，DATE 2003.

[11]杨依忠，解光军.基于遗传模拟退火算法的门阵列布局方法.计算机工程，2010，1.

[12]蒋中华.超大规模集成电路布图布局算法及热模型研究.2008.3.21.

[13]刘怀亮.模拟退火算法及其改进.广州大学学报（自然科学版）.2005，4（6）：503-506.

[14]黄钢，洪先龙，乔长阁等.带软模块的VLSI布局规划优化设计.计算机辅助设计与图形学学报，1999，11（2）：134-138.

[15]庄昌文，范明饪，李春晖，虞厥邦.基于协同工作方式的一种蚁群布线系统.半导体学报，1999，2（5）：400-406.