第３Ｏ卷第４期 ２０１３年４月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．３０ Ｎｏ．４ Ａｐｒ．２０１３ 基于切分结构的快速布图规划算法术 杜世民 ，夏银水 ，罗佐 （宁波大学ａ．信息科学与工程学院；ｂ．科学技术学院，浙江宁波３１５２１１） 摘 要：分析了切分（Ｓｌｉｃｉｎｇ）结构的布图产生空白面积的原因，提出了一种直观、快速的确定模块方向的方法。 改进了正则波兰表达式的一个邻域构造算子，并采用模拟退火算法实现了Ｓｌｉｃｉｎｇ结构布图规划。对ＭＣＮＣ和 ＧＳＲＣ的标准电路进行了测试，结果表明所提出的算法在解决Ｓｌｉｃｉｎｇ结构的布图规划方面是有效的。 关键词：布图规划；Ｓｌｉｃｉｎｇ结构；正则波兰表达式；模块方向；模拟退火算法 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１００１．３６９５（２０１３）０４ ０９９５—０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１３．０４．００９ Ｆａｓｔ ｆｌｏｏｒｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｓｌｉｃｉｎｇ ｓｔｒｕｃｔｕｒｅ ＤＵ Ｓｈｉ－ｍｉｎ 一，ＸＩＡ Ｙｉｎ．ｓｈｕｉ ，ＬＵＯ Ｚｕｏ （ａ．Ｃｏｌｌｅｇｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ｂ．Ｃｏｌｌｅｇｅ ｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｎｉｎｇｂｏ Ｕｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｂｏ Ｚｈｅｊｉａｎｇ ３１５２１１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｄ ｔｈｅ ｒｅａｓｏｎ ｗｈｉｃｈ ｃａｕｓｅｄ ｄｅａｄ ａｒｅａ，ａｎｄ ｐｒｏｐｏｓｅｄ ａｎ ｉｎｔｕｉｔｉｖｅ ａｎｄ ｆａｓｔ ａｐｐｒｏａｃｈ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｄｉｒｅｃｔｉｏｎ ｏｆ ｅａｃｈ ｍｏｄｕｌｅ．Ｉｔ ｉｍｐｒｏｖｅｄ ａｎ ｏｐｅｒａｔｏｒ ｔｏ ｐｅｒｔｕｒｂ ｎｏｒｍａｌｉｚｅｄ ｐｏｌｉｓｈ ｅｘｐｒｅｓｓｉｏｎ ｔｏ ｇｅｎｅｒａｔｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｏｌｕ— ｔｉｏｎ，ａｎｄ ｅｘｐｌｏｉｔｅｄ ｓｉｍｕｌａｔｉｏｎ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｏ ｉｍｐｌｅｍｅｎｔ ｔｈｅ Ｓｌｉｃｉｎｇ ｆｌｏｏｒｐｌａｎｎｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ｔｈｅ ｃｏｍ— ｍｏｎｌｙ ｕｓｅ ＭＣＮＣ ａｎｄ ＧＳＲＣ ｂｅｎｃｈｍａｒｋ ｃｉｒｃｕｉｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｅｆｉｃｉｆｅｎｔ ｔｏ ｓｏｌｖｅ ｔｈｅ Ｓｌｉｃｉｎｇ ｌｆｏｏｒｐｌａｎｉｎｇ ｐｒｏｂｌｅｍｓ． Ｋｅｙ ｗｏｒｄｓ：ｆｌｏｏｒｐｌａｎｎｉｎｇ；Ｓｌｉｃｉｎｇ ｓｔｒｕｃｔｕｒｅ；ｎｏｒｍａｌｉｚｅｄ ｐｏｌｉｓｈ ｅｘｐｒｅｓｓｉｏｎ；ｍｏｄｕｌｅ’Ｓ ｄｉｒｅｃｔｉｏｎ；ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏ— ｒｉｔｈｍ 芯片面积是除总线长之外传统布图规划要优化的主要指 ０ 引言 布图规划是ＶＬＳＩ（ｖｅｒｙ—ｌａｒｇｅ—ｓｃａｌｅ ｉｎｔｅｇｒａｔｉｏｎ）设计中一个 关键步骤。作为集成电路物理设计流程的第一步，它不仅决定 了芯片的空间结构（包括各个模块的位置、形状和方向），而且 对芯片互连进行了初步的优化。一个性能优良的布图规划能 标之一。在Ｓｌｉｃｉｎｇ结构的布图规划中，即使所有宏模块的尺 寸和面积都是固定的，但只要宏模块的方向不固定，则当模块 取不同方向时同一布图表示所计算得到的面积可能相差很大， 如图２所示。因此，在得到一个布图表达式之后，如何快速地 确定每个模块最优或次优方向，是布图规划要解决的重要问题 之一。 ４．５ ４ ３．５ ３ ２．５ 有效避免后期设计失败，从而加速整个设计的收敛过程。随着 电路规模和复杂程度的急剧增加，知识产权核（ＩＰ）、ｍｅｍｏｒｙ等 宏模块（ｍａｃｒｏ ｂｌｏｃｋ）在芯片设计中的使用越来越广泛。因此， 面向宏模块的平面布图规划问题得到了越来越广泛的研 究 圳。 ＶＬＳＩ布图规划的表示通常有两种方式，即Ｓｌｉｃｉｎｇ结构和 ｎｏｎ．Ｓｌｉｃｉｎｇ结构，如图ｌ所示。Ｓｌｉｃｉｎｇ结构是指可以不断地用 水平或垂直切割线将整个布图二分到每一个模块。与ｎｏｎ—Ｓｌｉ— ｃｉｎｇ结构相比，Ｓｌｉｃｉｎｇ结构具有以下优点：ａ）具有方便的数据 （ａ）Ｓｌｉｃｉｎｇ （ｂ）ｎｏｎ－Ｓｌｉｃｉｎｇ 图１ Ｆｌｏｏｒｐｌａｎｉｎｇ的两种表示结构 表示，通常可以利用二叉树或正则波兰表达式（ｎｏｒｍａｌｉｚｅｄ ｐｏｌ— ｉｓｈ ｅｘｐｒｅｓｓｉｏｎ，ＮＰＥ）等数据结构表示 …．ｂ）有利于后续芯片内 部通道的布线；Ｃ）有利于芯片在采用多电压供电时进行电压 岛的构建…。虽然与ｎｏｎ—Ｓｌｉｃｉｎｇ结构的＿些表示方法相比， Ｓｌｉｃｉｎｇ结构具有解空间较小（Ｏ（Ｉｔ，１ ２ ／ｎ ），ｎ为模块 １ 有关定义和表示 １．１ 平面布图规划问题 ＶＬＳＩ平面布图规划问题描述如下：给定一个包含有ｎ个 矩形模块的集合Ｂ＝｛ｂ。，ｂ ．－，ｂ ｝，对每个模块ｂ （１≤ｉ≤ｎ） 都有一个三元组（Ｗ ，ｈ ，ａ ）与之相对应，分别代表该模块的 宽、高和面积。其中，模块的面积ａ 是固定的，而模块的方向 数） 的缺点，但是Ｃｈａｎ等人 指出布图规划结果的优劣与 其采用的布图表示方式并不十分相关。因此，本文研究基于 Ｓｌｉｃｉｎｇ结构的布图规划算法。 收稿日期：２０１２．０８—１０；修回日期：２０１２．０９．２９ 可以作９０。旋转（即高度ｈ 和宽度Ｗ 互换）。布图规划的目标 基金项目：国家自然科学基金资助项目（６０８７１０２２，６１０４１００１）；浙江省自然科学基金资 助项目（Ｙ１０８０６５４，Ｚ１０９０６２２）；浙江省教育厅科研项目（Ｙ２００９０６６３７）；宁波大学学科项目（ｘｋ１０９６） 作者简介：杜世民（１９７６－），男，浙江东阳人，讲师，博士研究生，主要研究方向为集成电路设计自动化（ｄｕｓｈｉｍｉｎ＠ｎｂｕ．ｅｄｕ．ｅｎ）；夏银水（１９６３一），男，教 授，博导：博士，主要研究方向为集成电路综合和优化、高信息密度集成电路设计；罗佐（１９８８。），男，硕士研究生，主要研究方向为集成电路综合和优化． ・９９６・ 计算机应用研究 第３０卷 是将每个模块摆放在芯片中的合适位置（用模块左下角的坐 标来表示），使这些模块不发生重叠，且使包络全部模块的最 小矩形的面积与模块之间的总连线长度的加权和为最小。 １．２正则波兰表达式 一由上所述，每个布图表达式下所产生的空白面积是由模块 在两两组合过程中由于纵向或横向尺寸不一致而带来的空白 面积不断累积得到的。因此，如果能在表达式计算的过程中让 每一步组合运算所产生的空白面积尽可能小，那么最后就有可 能获得空白面积较小的布图实现。基于这一思想，本文提出一 种模块方向的确定方法，即把两个模块运算后产生空白面积最 小的布图实现作为模块的方向。 图４和５对所提出的模块方向确定方法给出了图形化的 说明。在图４中，模块１和２都是基本模块，其尺寸分别是６× ４和５ Ｘ ３，它们在做“ ”运算时可能得到四种不同的布图结 果。显然，图４（Ｃ）所得到的空白面积（阴影区域）是最小的，因 个Ｓｌｉｃｉｎｇ结构的布图可以方便地用二叉树（ｓｌｉｃｉｎｇ ｔｒｅｅ）表示，如图３所示。树中的每个叶节点代表一个基本模 块，用数字１～ｎ表示；内部节点“＋”和“ ”表示模块运算符， 分别表示两个模块在位置上左右与上下相邻。对布图相应的 二叉树进行后序遍历，即可得到一个长度为（２ｎ一１）的波兰表 达式Ｅ＝ｅｌ ｅ２…ｅ２ 一１，ｅ ∈｛１，２，…，ｎ， ，＋｝，１≤ ≤２ｎ一１。其 中：｛１，２，…，ｎ｝为操作数（ｏｐｅｒａｎｄ），｛ ，＋｝为运算符（ｏｐｅｒａ— 此，在计算“１２ ”时就确定模块１的尺寸为４×６，模块２的尺 ｔｏｒ）。例如，图３所示的二叉树对应的波兰表达式为“１２＋３ ４＋”。表达式 是一个正则波兰表达式，当且仅当 ］ｏｊ：ａ）每 个操作数ｉ（１≤ｉ≤ｎ），仅在表达式Ｅ中出现一次；ｂ）Ｅ的任一 子表达式Ｅ ：ｅ１ｅ：…ｅ ，１≤ｍ≤２ｎ一１，所包含的操作数的数 量要大于操作符的数量；Ｃ）表达式Ｅ中不存在多个（两个或两 个以上）连续的相同运算符（如 或＋＋）。 ｌｃ 入 ‘ １ ２ （ａ）Ｓｌｉｃｉｎｇ结构的布图 （ｂ）相应的二叉树 图３二叉树对应的波兰表达式 ２ Ｓｌｉｃｉｎｇ布图中模块方向的确定 在本文中将每个模块看做是矩形的硬模块（ｈａｒｄ ｂｌｏｃｋ）， 即模块的面积是确定的，但模块的方向可以旋转９０。（即高度 和宽度互换）。由于每个模块有两种可能的方向，因此在计算 一个包含ｎ个模块的正则波兰表达式时，可能得到不同的布图 实现（其中多数是冗余的），最多可达２ 种。显然，当芯片规 模较大时，要得到每个表达式下最小面积的布图结果是非常困 难的。模拟退火算法是布图优化常用的算法之一。然而在利 用模拟退火算法对表达式进行搜索时，由于每个温度下都要产 生数百至数千个不同的布图表达式，因此，不可能去计算每个 表达式下最优的布图实现，否则整个算法会非常耗时。文献 ［８］采用在模拟退火算法中增加一个模块旋转的算子来随机 选择基本模块的方向，这种方法同样存在收敛速度慢的缺点。 Ｓｔｏｃｋｍｅｙｅｒ 最早对布图规划中的模块方向问题进行了研究， 指出对于Ｓｌｉｃｉｎｇ的布图结构，两个节点（模块）每经过一次“ ” 或“＋”组合运算，所产生的非冗余的布图数量呈线性增长关 系。因此，需要寻找到一种简单、快速且比较有效的方法来计算 每个表达式下的布图实现，以提高算法收敛的速度。 在图３（ａ）所示的Ｓｌｉｃｉｎｇ布图规划中，阴影部分表示布图 后所产生的空白面积。它由三部分构成，分别是图中的矩形区 域Ａ、 和Ｃ。其中：区域Ａ是由于模块１和２在进行“＋”运算 时，由于模块１与模块２的宽度不一致造成的；区域日则是由 模块１和２运算得到的组合模块，以及模块３在进行“ ”运算 时，由于它们的高度不一致所产生的。由此可见，当两个模块 在做“＋”运算时，如果水平方向的尺寸不一致，就会产生空白 面积。类似地，如果两个模块垂直方向的尺寸不同，则它们在 做“ ”运算时也会产生多余的空白面积。整个布图规划总的 空白面积等于每一步运算所产生的空白面积之和。 寸为３ Ｘ ５。类似地，当一个基本模块与复合模块（由若干个基 本模块组合得到的模块）做运算时，同样可根据运算后所产生 空白面积的大小来确定基本模块的方向（注：复合模块一旦生 成方向就已固定）。例如在图５中，表达式“１２＋”生成的复合 模块与基本模块３做“ ”运算时有两种可能的布图结果，由 于图５（ａ）中的空白面积要小于图５（ｂ），因此基本模块３的方 向就确定为图５（ａ）中所示的方向。 ， 謇’ ＇ 臣 Ｉ ２ ｌ ｌ图４表达式“１２ 四种 罔５ 复合模块与基本模块进行运算 可能的布图实现 时两种町能的布图实现 ３模拟退火算法 ＶＬＳＩ布图规划问题是一类非常复杂的组合优化问题，它 的一些子问题已被证明是ＮＰ—ｈａｒｄ问题。自Ｏｔｔｅｎ １２ｊ首次将模 拟退火算法用于解决ＶＬＳＩ的平面布图规划问题后，模拟退火 算法逐渐成为ＶＬＳＩ物理设计领域应用最为广泛的一种智能优 化算法。应用模拟退火算法进行布图规划的优化设计时，主要 解决以下三个问题：ａ）布图规划的表示；ｂ）解的邻域构造策 略；Ｃ）温度控制策略和算法终止条件。布图规划的表示是对 给定的布图进行编码，将其表示成一个解的形式。由于本文中 考虑的是Ｓｌｉｃｉｎｇ结构的布图规划，因此采用正则波兰表达式 来表示布图的解。下面主要介绍采用的邻域构造策略和温度 策略。 ３．１邻域构造策略 在可切分的布图规划设计中，对正则波兰表达式所表示的 当前解，一般通过以下四种操作来对其进行扰动，以产生新的 邻域解：ａ）随机选择两个相邻的操作数进行交换；ｂ）随机交换 两个相邻的操作数和操作符；Ｃ）随机选择一连续的操作符链 取反，即将该链中“ ”换成“＋”，将“＋”换成“ ”；ｄ）随机选 择一个模块进行旋转。 操作ｄ）用于随机选择基本模块的方向。由于本文中模块 的方向根据前面第２章的方法来确定，因此，在本文的算法中 仅包含前面三种操作。其中，操作ａ）和ｃ）都可以保证操作后 得到的依然是一个合法的正则波兰表达式；但对操作ｂ），则需 要一些限定条件，使其满足合法正则表达式的条件。由于操作 ａ）在有些情况下并不会改变当前布图的面积（这种操作称之 第４期 杜世民，等：基于切分结构的快速布图规划算法 ・９９７・ 为空操作），例如在正则表达式“７ ９ ６ ５＋３ ８ １０＋１ ＋ ４ ２ ０＋ ”中，“７ ９”“９ ６”都属于几何上相邻的操作数，但若 交换“７ ９”这对操作数并不会改变布图后的面积。因此在本文 中将允许交换范围扩大，不再在位置上相邻的两个操作 数，而是允许交换两个任意位置的操作数，这样可以在一定程 度上减少产生空操作的次数，加快算法收敛的速度。 ３．２ 温度策略和终止条件 ４ 实验结果 本文所提出的针对可切分结构的布图规划算法已用Ｃ语 言编程实现，并在主频为Ｉｎｔｅｌ ２．４ ＧＨｚ ＣＰＵ和１ ＧＢ内存的ＰＣ 上运行。对算法进行了两组实验，第一组用五个ＭＣＮＣ电路 进行测试，以布图后得到的芯片面积为优化目标；第二组则以 面积和线长的加权和为目标函数对ＧＳＲＣ中三个规模最大的 模拟退火算法的温度策略主要包括初始温度的确定和降 温策略的选择。本文采用式（１）来确定算法的起始温度 。 ＝ 电路进行测试。测试电路基本信息如表１所示。模拟退火算 法参数设置如下：ａ）降温系数ｏＬ＝０．９５；ｂ）马尔可夫链的长度 取４０ｎ（ｎ为芯片包含模块数）；Ｃ）算法终止条件为温度下降到 １０ 或在当前温度下接受新解的概率＜５‰。 表１测试电路基本信息表 （１） 要计算式（１）中Ａａｖｇ，首先要随机产生一个初始解，然后 对其进行Ⅳ次操作。其中：Ａａｖｇ就等于这Ⅳ次操作下目标函 数变化量的平均值；参数Ｐ是退火初始时接受更差解的概率， 是一个接近于１但又小于１的数，一般在０．９～１间取值。 在降温策略方面，本文采用式（２）对温度进行更新。 Ｔｋ＝ｎ Ｘ 电路 数 数 数 藩 Ｎ数ｅｔ 总面积 电路 数、 ａｐｔｅ ｘｅｒｏｘ ｈｐ Ｎ数ｅｔ 腼积 “ ２２ ３３４ ５６４ ９ １０ １１ ７３ ２ ４５ ９７ ４６．５６１６ ａｍｉ４９ ２０３ １９．３５０３ ８３ ８．８３０３ ｎｌｏｏ ｎ２ｏｏ ４９ １００ ２００ ４０８ ３５．４４５４ ８８５ ０．１７９５ １５８５ ０．１７５７ １ （２） ａｍｉ３３ ３３ ４２ １２３ １．１５６４ ｎ３ｏｏ ３００ ５６９ １８９３ ０ ２７３２ 式中： 是降温系数。在每个温度下需要迭代的次数（即马尔 可夫链的长度）与芯片的规模有关。 ３．３算法流程 第一组实验结果如表２所示，其中，ｄｓ百分比等于布图后 得到的芯片空白面积与其总面积之比。从表２可以看出，本算 法与文献［４～６］相比可在更短的时间内得到更小的芯片面 积。与文献［７］相比，虽然在芯片平均的空白面积上略微增加 一整个算法从随机产生的一个初始解开始，然后在解空间中进 行搜索，直到解的质量没有任何改进或温度降到终止条件为止。 应用模拟退火算法解决可切分结构的布图规划流程如下： ａ）读取测试电路的信息。 ｂ）随机产生一个布图的初始解。 ｃ）依式（１）计算退火初始温度 。 ｄ）随机选择一种邻域构造方法对当前解进行变换，产生新解。 ｅ）判断新解是否优于当前解。若优于当前解，保存新解为当前解 （作为下一次搜索的出发点），并更新最优解；否则，以（ｅ ）概率接 受新解。 ｆ）判断是否超过当前温度下的迭代次数。若是，转ｇ）；否则，转ｄ）。 ｇ）依式（２）更新当前温度，并判断是否到达终止温度。若不满足， 转ｄ）；否则，转ｈ）。 ｈ）输出已搜索到的最优解，算法结束。 点，但在速度上却有较大的提高。其中，ａｍｉ３３的空白面积 率（百分比）分别比文献［４，６，７］减少了３．８６％、６．７７％和 ０．７５％，同时速度分别提高了６．５、３３．９和１６．９倍；ａｍｉ４９的空 白面积率分别比文献［４，６］减少了２．６１％和１０．１２％，同时速 度提高了１４．４和１３１．３倍。虽然ａｍｉ４９的空白面积率与文献 ［７］基本相同，但是速度却提高了１５．４倍。图６给出了ＭＣＮＣ 中模块数最多的两个电路ａｍｉ３３和ａｍｉ４９的布图规划结果。 在第二组实验中，以式（３）作为目标函数，同时对ＧＳＲＣ电 路的面积和线长进行优化： ｃｏｓｔ＝ ×Ａ＋（１一ＯＬ）×Ｗ （３） 表２ ＭＣＮＣ电路的实验结果与其他文献的比较 注：ＮＡ为Ｎｏｔ Ａｖａｉｌａｂｌｅ（原文中数据役有给出） 式中：Ａ、 为芯片的总面积和总线长；权值Ｏｔ用来调整两者的 ｓ 比重，在本实验中取０．９。实验结果如表３所示。表中总线长 列采用半周长法（ｈａｌｆ ｐｅｒｉｍｅｔｅｒ ｗｉｒｅ ｌｅｎｇｔｈ，ＨＰＷＬ）计算得到。 Ｉ ・ ｌ ｌ — 。ｌ ｔ ｍ 由表３可知，当电路规模增加时，应用本文算法可同时获得较 低的空白面积率和总线长。虽然模块数增加较多，算法的运行 时间变长，空白面积率较ＭＣＮＣ电路有所增加，但仍在可接受 的范围内，进一步验证了本文算法的有效性。图７给出了 ｓ １ ＊Ｉ Ｉ 一ｌ竺卜 ｌ ］ｍ ・ｌ阳 二Ｉ｝４＊ ｚ ＧＳＲＣ中两个电路（ｎｌ００和ｎ２００）的布图结果。 表３ ＧＳＲＣ电路的实验结果 ０ ２００ ４００ ６００ ８００ Ｉ（３００ ｝÷］ １２００ ０ １００６ ２ＯＯＯ ３叩０ ４０００ ５０００ （ａ）ａｍｉ３３（ｄｓ％：２．８８） （ｂ）ａｍｉ４９（ｄｓ％：３．４５） 图６两个ＭＣＮＣ电路的布图结果 ・９９８・ 计算机应用研究 第３０卷 １ ２ Ｊ ＳＨＥＮ ｚ Ｃ，ＣＨＵ Ｃ Ｃ Ｎ．Ｂｏｕｎｄｓ ｏｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓｌｉｃｉｎｇ，ｍｏｓａｉｃ，ａｎｄ － ｔ，Ｉ ５００ 广＝］ ，。 Ｉ Ｉ鞋捶 Ｉ Ｉｇｅｎｅｒｌａ ｆｌｏｏ￣ｌａｎｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｃｏｍｐｕｔｅｒ－Ａｉｄｅｄ Ｄｅｓｉｇｎ ｏｆ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ，２００３，２２（１０）：１３５４—１３６１． Ｉ ３ ｌ ＣＨＡＮ Ｈ Ｈ，ＡＤＹＡ ｓ Ｎ，ＭＡＲＫ０ Ｉ Ｌ．Ａｒｅ ｆｌｏｏｒｐｌａｎ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ Ｉ｜ ｌ 。 ｌｌ １－ 。 一＝ －Ｉ ｌ 上 ｉｍｐｏｒｔａｎｔ ｉｎ ｄｉｇｉｔａｌ ｄｅｓｉｇｎ？［ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｈｙｓｉｃａｌ Ｄｅｓｉｇｎ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００５：１２９．１３６． 。 ｍ ‘ｌ＇ｌ 。 －－－＾－●●＿－＿—— ” ｌ 鞋 啪－一ｒ卜ｌ１ｓ． 熹 ｉ ７’ ｎ － １４ ｌ ＰＡＮＧ Ｙｉｎｇ．ｘｉｎ，ＣＨＥＮＧ Ｃ Ｋ，ＹＯＳＨＩＭＵＲＡ Ｔ．Ａｎ ｅｎｈａｎｃｅｄ ｐｅ￣ｕｒ－ ｂｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｌｏｏｒｐｌａｎ ｄｅｓｉｇｎ ｕｓｉｎｇ ｔｈｅ Ｏ—ｔｒｅｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ — ｒ＿１ ＊ ” Ｊ 蕾 ｌ ｍ １－ Ｆ ［ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｈｙｓｉｃａｌ Ｄｅｓｉｇｎ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２０００：１６８—１７３． ｍ ｍ ｌＩ １ｌ”ｒＩ ｒｔ ＊ ［５］ＲＡＨＩＭ Ｈ Ａ，ＡＢ Ｒ Ａ Ｈ，ＡＮＤＡＬＪＡＹＡＬＡＫＳＨＭＩ Ｇ，ｅｔ ａ１．Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｐｐｒｏａｃｈ ｔｏ ＶＬＳＩ ｍａｃｒｏ ｃｅｌｌ ｎｏｎ－ｓｌｉｃｉｎｇ ｌｏｏｒｐｌｆａｎｓ ｕｓｉｎｇ ｂｉ・－ —ｌ －Ｉ Ｎ ＊ ” ｍ “ＨＨ，ｌ ｍ ｍ ｎａｒｙ ｔｒｅｅ ｆ Ｃ ｌ／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ Ｐｒｅｓｓ．２００８：２６．３１． ∞ 一：—！”ｌ＿Ｔ １ｌＬ厂ｊＩ ＿－一 Ｊ” 。妻 一“ － ｌ・ ００ Ｉ＇１ ｍ ｌ一 一 ｌ ＿］ｌｉｔｌ＊Ｉ ｔ ｌ∞网１６ Ｊ ＳＵＮ Ｔ Ｙ，ＨＳＩＥＨ Ｓ Ｔ，ＷＡＮＧ Ｈ Ｍ，ｅｔ ａ１．Ｆｌｏｏｒｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ 桃 Ｈ・一１ 一・ ｐａｒｔｉｃｌｅ ｓｗａｒ／ｎ ｏｐｔｉｍｉｚａｔｉｏｎ［ｃ］／／Ｐｒｏｃ ｏｆ Ｅｍｅｒｇｉｎｇ ＶＬＳＩ Ｔｅｃｈｎｏｌｏ． ｇｉｅｓ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅｓ．Ｋａｒｌｓｍｈｅ：ＩＥＥＥ Ｐｒｅｓｓ．２００６：７一Ｉ１． 。 Ｉ ． １００ ［７］ＵＮ Ｊ Ｍ，ＣＨＡＮＧ Ｙａｏ—ｗｅｎ．ＴＣＧ：ａ ｔｒａｎｓｉｔｉｖｅ ｃｌｏｓｕｒｅ ｇｒａｐｈ．ｂａｓｅｄ ｒｅｐ— ０ ２∞３∞ Ｏ １００ ２∞ ｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｎｏｎ—ｓｌｉｃｉｎｇ ｌｆｏｏｒｐｌａｎｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ３８ｔｈ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．２００１：７６４＿７６９． （ａ）ｎｌ００（ｄｓ％：４．２８） （ｂ）ｎ２００（ｄｓ％：４．８２） 图７两个ＧＳＲＣ电路的布图结果 ［８］ＴＡＮＧ Ｃ Ｃ．Ｖｏｌｔａｇｅ ｉｓｌａｎｄ－ａｗａｒｅ ｆｌｏｏｒｐｌａｎｎｉｎｇ ｆｏｒ ＳｏＣ ｄｅｓｉｇｎ［Ｄ］． Ｈｓｉｎｃｈｕ：Ｎａｔｉｏｎａｌ ＴｓｉｎｇｈＨａ Ｕｎｉｖｅｒｓｉｔｙ，２００９． ５ 结束语 本文讨论了Ｓｌｉｃｉｎｇ结构的布图规划问题，采用正则波兰 ［９］张博，李毅．一种改进的ＶＬＳＩ电路有效布局算法［Ｊ］．计算机工程 与应用，２００７，４３（１３）：２４３—２４６． １１Ｏ Ｊ ＷＯＮＧ Ｄ Ｆ，ＬＩＵ Ｃ Ｌ．Ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｌｏｏｒｐｌａｎ ｄｅｓｉｇｎ『ｃ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ２３ｒｄ ＡＣＭ／ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ．Ｌａｓ 表达式来表示布图结构，根据模块运算后产生空白面积的大小 来确定模块的方向，并采用模拟退火算法来搜索最优的布图表 达式。实验结果表明，本文方法能有效地解决Ｓｌｉｃｉｎｇ结构的 布图规划问题。 参考文献： ［１］ＭＡ Ｑｉａｎｇ，ＹＯＵＮＧ Ｅ Ｆ Ｙ．Ｖｏｌｔａｇｅ ｉｓｌａｎｄ－ｄｒｉｖｅｎ ｌｆｏｏｒｐｌａｎｎｉｎｇ［Ｃ］／／ Ｐｒｏｃ ｏｆ ＩＥＥＥ／ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ—Ａｉｄｅｄ Ｄｅｓｉｇｎ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ Ｐｒｅｓｓ．２００７：６４４—６４９． Ｖｅｇａｓ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｐｒｅｓｓ，１９８６：１０１．１０７． 【】】Ｊ ＳＴＯＣＫＭＥＹＥＲ Ｌ．Ｏｐｔｉｍａｌ ｏｒｉｅｎｔａｔｉｏｎｓ ｏｆ ｃｅｌｌｓ ｉｎ Ｓｌｉｃｉｎｇ Ｆｌｏｏｒｐｌａｎ ｄｅｓｉｇｎｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｎｔｒｏｌ，１９８３，５７（２．３）：９１．１０１． ［１２］ＯＴＴＥＮ Ｒ．Ｅｆｆｉｃｉｅｎｔ ｆｌｏｏｒｐｌａｎ ｏｐｔｉｍｉｚａｔｉｏｎ『Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒ． ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｄｅｓｉｇｎ：ＶＬＳＩ ｉｎ Ｃｏｍｐｕｔｅｒｓ．１９８３： ４９９．５０２． ［１３］ＨＯＮＧ Ｘｉａｎ—ｌｏｎｇ，ＨＵＡＮＧ Ｇａｎｇ，ＣＡＩ Ｙｉ ｃｉ，ｅｔ ａ１．Ｃｏｒｎｅｒ ｂｌｏｃｋ ｌｉｓｔ： ａｎ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｔｏｐｏｌｏｇｉｃａｌ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｎｏｎ—Ｓｌｉｃｉｎｇ ｌｆｏｏｒｐｌａｎ［ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ／ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｒｎ ｐｕｒｅｒ－Ａｉｄｅｄ Ｄｅｓｉｇｎ．２０００：８－１２． （上接第９９４页） 蚓 闼 极值域速度快、捕捉效率高等优点。０—１背包问题属于组合优 蠖 皿 ｊ／ 迭代次数 化问题，且是ＮＰ难题。本文就背包问题的特点设计了基于 ＭＡＴＬＡＢ环境的萤火虫群优化算法，编写了算法程序。测试结 果表明，萤火虫群优化算法对０．１背包问题的求解是可行的， 并收到了良好的效果，为有效求解此类问题提供了一种新的可 行方法，同时也拓展了萤火虫群优化算法的应用领域。 参考文献： ［１］ＳＹＳＬＯ Ｍ Ｍ．Ｄｉｓｃｒｅｔｅ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ［Ｍ］．Ｎｅｗ Ｊｅｒｓｅｖ：Ｐｒｅｎ— ｒｉｃｅ．Ｈａｌｌ，１９８３：１１８—１６５． 图４萤火虫算法的收敛性 微粒群算法 与萤火虫算法就该问题的对比结果如表２ 所示。由表２可以看出，两种算法在一定的迭代次数下都可以 求得该实例的最优值，但是微粒群算法的频率（求得最优解次 数／运行总次数）明显低于萤火虫算法。经过大量计算实验， 说明算法性能令人满意。 表２微粒群算法与萤火虫算法的计算结果对比 ［２］张永兵，王斌，张永飞，等．基于遗传算法的背包问题求解『Ｊ］．大 理学院学报，２００５，４（５）：２４．２５． ［３］马良，朱刚，宁爱兵．蚁群优化算法［Ｍ］．北京：科学出版社，２００８． ［４］樊小毛，马良．０－１背包问题的蜂群优化算法［Ｊ］．数学的实践与 认识，２０１０，４０（６）：１５５—１６０． ［５］沈显君，王伟武，郑波尽，等．基于改进的微粒群优化算法的０－１ 背包问题求解［Ｊ］．计算机工程，２００６，３２（１８）：２３．２４．３８． １ ６ Ｊ ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ，ＧＨＯＳＥ Ｄ．Ｄｅｔｅｃｔｉｏｎ ｏｆ ｍｕｌｔｉｐｌｅ ｓｏｕｒｃｅ ｌ０ｃａ— ｔｉｏｎｓ ｕｓｉｎｇ ａ ｇｌｏｗｗｏｒｍ ｍｅｔａｐｈｏｒ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｃｏｌｌｅｃｔｉｖｅ ｒｏｂｏ— ｔｉｃｓｌ Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｓｗａｒｍ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｙｍｐｏｓｉｕｍ．２００５：８４． ９１． １ ７ Ｊ ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ，ＧＨＯＳＥ Ｄ．Ａ ｇｌｏｗｗｏｒｍ ｓｗａｒｌｎ ｏｐｔｉｍｉｚａｔｉｎｎ ｂａｓｅｄ ｍｕｌｔｉ－ｒｏｂｏｔ ｓｙｓｔｅｍ ｆｏｒ ｓｉｇｎａｌ ｓｏｕｒｃｅ ｌｏｃａｌｉｚａｔｉｏｎ［Ｍ］／／Ｄｅｓｉｇｎ ａｎｄ Ｃｏｎｔｒｏｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｉｃ Ｓｙｓｔｅｍｓ．２００９：４９—６８． ［８］ＫＲＩＳＨＮＡＮＡＮＤ Ｋ Ｎ，ＧＨＯＳＥ Ｄ．Ｔｈｅｏｒｅｔｉｃａｌ ｆｏｕｎｄａｔｉｏｎｓ ｆｏｒ ｒ℃ｎｄｅｚ． ＶＯＵＳ ｏｆ ｇｌｏｗｗｏｒｍ ｉｎｓｐｉｒｅｄ ａｇｅｎｔ ｓｗａｒｌＴｉ￥ａｔ ｍｕｌｔｉｐｌｅ ｌｏｃａｔｉｏｎ『Ｊ］．Ｒｏ． ｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ．２００８．５６（７）：５４９—５６９． ３ 结束语 萤火虫群优化算法作为一种新的智能优化算法，具有捕捉 ［９］严太山，陈专红，陈群，等．一种求解背包ｆ－＊Ｉ题的改进遗传算法 ［Ｊ］．现代计算机：下半月版，２００９（９）：４４ ４７． ［１０］马良，王龙德．背包问题的蚂蚁优化算法［Ｊ］．计算机应用，２００１． ２１（８）：４－５．
