超大规模集成电路布图领域的划分问题是一个NP完全问题,一般采用启发式算法解决。目前,超大规模集成电路划分问题已经得到了广泛而深入的研究,出现了许多较为有效的解决算法。在这些算法当中,组迁移算法以其简单有效得到了最广泛的应用。但是随着电路规模的不断增大,研究人员开始更多的利用多级层次划分策略解决该问题。本文首先对已有的电路划分算法进行了介绍,尤其深入分析了基于多级层次划分策略、运用组迁移算法进行电路划分的思想。在此基础上,提出了一种新的多级层次划分算法。该算法首先从电路连接关系中抽象出超图模型,然后对所得超图模型进行多级层次划分。在层次划分时,采用了多次塌缩优化的策略扩大搜索空间,并在恢复优化时运用了贪婪策略,使得算法在避免局部最优的同时,仍然维持了较低的计算时间。对ISPD98测试数据的仿真实验表明,该算法要比二分法和简单的多块多级层次划分法更为有效。
本文来源: https://www.lw50.cn/article/c8641e1a300312aea953e25b.html