基于修正模拟退火算法及溢出面积模型的固定边界布图规划

2016年第17卷第11期

摘要

关键词

相关研究

回顶部

《信息与电子工程前沿（英文）》 >> 2016年第17卷第11期 doi: 10.1631/FITEE.1500386

基于修正模拟退火算法及溢出面积模型的固定边界布图规划

. School of Electrical Engineering and Automation, Jiangsu Normal University, Xuzhou 221116, China.. School of Computer Science and Technology, Jiangsu Normal University, Xuzhou 221116, China

发布日期： 2016-12-08

HTML38 PDF 3 收藏 0

摘要

无边界布图规划研究面积及线长减少问题很难满足现代设计需求，因此通常被认为是无意义的。我们关注一种难度更大且更有意义的问题--固定边界布图规划。该问题将固定边界约束条件加入无边界布图规划中，使其在实体设计中更有趣、更具挑战性。本文的工作主要分为两部分。第一，提出了一种修正模拟退火算法（Modified simulated annealing algorithm, MSA）。在进化过程初期，用一种新的衰减方程来缓慢减小温度，以增强MSA的全局搜索能力。然后，用传统衰减方程来快速减小温度，以维持MSA的局部搜索能力。第二，设计了一种溢出面积模型来引导MSA寻找可行解，为精炼可行解节省了大量时间。另外，B*-tree是一种有效的布图规划表示法，它被用来执行MSA的扰动操作。最后，以六组带有不同空置率及高宽比的benchmark为例，证实本文所提方法在解决固定边界布图规划问题上的效率，这些问题包括电路n10，n30，n50，n100，n200和n300。与几种现有方法相比，本方法能够更有效地获得令人满意的目标函数值，它们与芯片面积、线长和固定边界约束有关。

关键词

固定边界布图规划 ; 修正的模拟退火算法 ; 全局搜索 ; 溢出面积模型 ; B*-tree表示法