基于切分结构的快速布图规划算法-计算机应用研究.PDFVIP

第３０卷第４期 计 算 机 应 用 研 究 Ｖｏｌ．３０Ｎｏ．４ ２０１３年４月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｐｒ．２０１３ 基于切分结构的快速布图规划算法 ａ，ｂ ａ ａ 杜世民 ，夏银水 ，罗　佐 （宁波大学ａ．信息科学与工程学院；ｂ．科学技术学院，浙江 宁波３１５２１１） 摘　要：分析了切分（Ｓｌｉｃｉｎｇ）结构的布图产生空白面积的原因，提出了一种直观、快速的确定模块方向的方法， 改进了正则波兰表达式的一个邻域构造算子，并采用模拟退火算法实现了Ｓｌｉｃｉｎｇ结构布图规划。对ＭＣＮＣ和 ＧＳＲＣ的标准电路进行了测试，结果表明所提出的算法在解决Ｓｌｉｃｉｎｇ结构的布图规划方面是有效的。 关键词：布图规划；Ｓｌｉｃｉｎｇ结构；正则波兰表达式；模块方向；模拟退火算法 中图分类号：ＴＰ３９１　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１３）０４０９９５０４ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１３．０４．００９ ＦａｓｔｆｌｏｏｒｐｌａｎｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＳｌｉｃｉｎｇｓｔｒｕｃｔｕｒｅ ａ，ｂ ａ ａ ＤＵＳｈｉｍｉｎ ，ＸＩＡＹｉｎｓｈｕｉ，ＬＵＯＺｕｏ （ａ．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，ｂ．ＣｏｌｌｅｇｅｏｆＳｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，ＮｉｎｇｂｏＵｎｉｖｅｒｓｉｔｙ，ＮｉｎｇｂｏＺｈｅｊｉａｎｇ３１５２１１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｄｔｈｅｒｅａｓｏｎｗｈｉｃｈｃａｕｓｅｄｄｅａｄａｒｅａ，ａｎｄｐｒｏｐｏｓｅｄａｎｉｎｔｕｉｔｉｖｅａｎｄｆａｓｔａｐｐｒｏａｃｈｔｏｄｅｔｅｒｍｉｎｅ ｔｈｅｄｉｒｅｃｔｉｏｎｏｆｅａｃｈｍｏｄｕｌｅ．Ｉｔｉｍｐｒｏｖｅｄａｎｏｐｅｒａｔｏｒｔｏｐｅｒｔｕｒｂｎｏｒｍａｌｉｚｅｄｐｏｌｉｓｈｅｘｐｒｅｓｓｉｏｎｔｏｇｅｎｅｒａｔｅｎｅｉｇｈｂｏｒｈｏｏｄｓｏｌｕ ｔｉｏｎ，ａｎｄｅｘｐｌｏｉｔｅｄｓｉｍｕｌａｔｉｏｎａｎｎｅａｌｉｎｇａｌｇｏｒｉｔｈｍｔｏｉｍｐｌｅｍｅｎｔｔｈｅＳｌｉｃｉｎｇｆｌｏｏｒｐｌａｎｎｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎｔｈｅｃｏｍ ｍｏｎｌｙｕｓｅＭＣＮＣａｎｄＧＳＲＣｂｅｎｃｈｍａｒｋｃｉｒｃｕｉｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅａｎｄｅｆｆｉｃｉｅｎｔｔｏｓｏｌｖｅｔｈｅＳｌｉｃｉｎｇ ｆｌｏｏｒｐｌａｎｉｎｇｐｒｏｂｌｅｍｓ． Ｋｅｙｗｏｒｄｓ：ｆｌｏｏｒｐｌａｎｎｉｎｇ；Ｓｌｉｃｉｎｇｓｔｒｕｃｔｕｒｅ；ｎｏｒｍａｌｉｚｅｄｐｏｌｉｓｈｅｘｐｒｅｓｓｉｏｎ；ｍｏｄｕｌｅ’ｓｄｉｒｅｃｔｉｏｎ；ｓｉｍｕｌａｔｅｄａｎｎｅａｌｉｎｇａｌｇｏ ｒｉｔｈｍ 芯片面积是除总线长之外传统布图规划要优化的主要指 　引言 标之一。在Ｓｌｉｃｉｎｇ结构的布图规划中，即使所有宏模块的尺 寸和面积都是固定的，但只要宏模块的方向不固定，则当模块 布图规划是 ＶＬＳＩ（ｖｅｒｙｌａｒｇｅｓｃａｌｅｉｎｔｅｇｒａｔｉｏｎ）设计中一个 取不同方向时同一布图表示所计算得到的面积可能相差很大， 关键步骤。作为集成电路物理设计流程的第一步，它不仅决定