求解VLSI不可二划分布图规划问题混合遗传算法.docVIP

求解VLSI不可二划分布图规划问题的混合遗传算法 陈建利，朱文兴 （福州大学离散数学与理论计算机研究中心，福建 福州 350116） 摘要：超大规模集成电路（VLSI）布图规划是VLSI物理设计的关键的环节之一，对集成电路的芯片面积、线长等性能指标有重大影响。基于B*-tree的结构表示，结合遗传算法的思想，提出了一种用于解决VLSI不可二划分布图规划问题的混合遗传算法，并用MCNC标准测试例子对所设计的算法进行测试，证明该算法的有效性。 关键词：VLSI布图规划；B*-tree；混合遗传算法 中图分类号：TP319 A hybrid genetic algorithm for non-slicing VLSI floorplanning CHEN Jian-li1，ZHU Wen-xing (Center for Discrete Mathematics and Theoretical Computer Science，Fuzhou University，Fuzhou，Fujian 3501，China) Abstractshow that the hybrid genetic algorithm is effective. Keywords：VLSI floorplanning; B*-tree; hybrid genetic algorithm 0 引言 超大规模集成电路（VLSI）布图规划是VLSI物理设计的早期阶段，对集成电路的芯片面积、线长等性能指标有重大影响，是VLSI物理设计的关键环节之一［1］。VLSI布图规划问题是根据给出的矩形模块、模块之间相互联结的信息（网表），把所有模块合法地放置在芯片中适当的位置上，并使其满足一定的要求。布图结果的好坏直接影响整个芯片的性能。 在VLSI布图规划中，有可二划分(Slicing)和不可二划分(non-slicing)两种类型的芯片版图结构[1]。可二划分结构通过递归法以垂直和水平划分线把一个个矩形模块划分划分成二部分。其结构比较简单，但只涵盖了部分布图问题。相对而言，不可二划分结构更具有一般性、灵活性，和具有更高的面积利用率等优点。但不可二划分版图结构更加复杂，实现也更为困难。 为表示不可二划分的布图结构，大量的结构表示方法被提出。不同的表示法有不同的解空间和不同的冗余度,它们的解码操作和扰动操作的效率也不尽相同。现有的用来解决VLSI布图规划的主要表示结构有：O-tree［2］、B*-tree[3]、序列对(Sequence Pair)[4]、角模块序列(corner block list)[5]、TCG (transitive closure graph)[6]、TCG-S[7]、SKB-tree[8]等。与其它结构表示相比，B*-tree具有解空间小、操作简单、能够处理不同类型模块等优点，且由一棵B*-tree可以得到唯一的一个与之相对应的布图。对有预先放置模块和布图区域有约束的布图问题，B*-tree也可以容易地进行处理。因此，本研究采用B*-tree表示结构。 布图规划已被证明是NP困难问题[1]，因此不能在线性时间内得到它的最优解。研究者提出了各种启发式算法来解决布图规划问题，主要有模拟退火算法[9-10]、粒子群算法[11-12]、遗传算法[13-16]等。在基于遗传算法的布图规划方法中，文献[14-16]所提出的算法只能解决可二划分布图规划问题。基于O-tree的结构表示，文[13]提出一种基于遗传算法的Memetic算法用来解决不可二划分的布图规划问题。但由于O-tree与布图非一一对应关系，此编码方案在有哪些信誉好的足球投注网站时难于从布图结果中获得有效的拓扑信息，因此该算法效率不高。 本研究提出一种用以解决不可二划分VLSI布图规划的混合遗传算法。基于B*-tree的结构表示，在全局有哪些信誉好的足球投注网站时，该算法采用交叉运算和变异运算使有效的拓扑信息得到保留；在局部有哪些信誉好的足球投注网站中，通过不断地交换B*-tree的结点，得到一个局部最优解。在MCNC[17]标准测试例子集测试的实验结果表明，该混合遗传算法是有效的。 1 相关描述 1.1 布图规划问题 把VLSI问题加以抽象化，可描述为：给定个矩形块 (的长为宽为)这个模块之间相互联的一个足够大的矩形框。9-12]一样，目标函数为： . 在一个满足布图要求的布图F中，表示包含所有模块的最小矩形框的面积；表示采用半周长线长[10]计算的总线长；表示当前最优的面积及线长；w是权重因子，。 1.2 B*-tree B*-tree[3]是一棵有序的二叉树，它的根结点对应着左下角的矩形模块。类似于深度优先有哪些信誉好的足球投注网站，一棵