摘要
电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.
Circuit partitioning is an important stage in the very large scale integration (VLSI) physical design automation, which influences further circuit design. The VLSI circuit partitioning problem is an NPhard combinatorial optimization problem. In this paper, we propose a scatter search method for the problem, which incorporates the singlevertexmove based FiducciaMatthey ses algorithm (F'M) within the scatter search framework. The FM algorithm is used for local exploitation, while the scatter search sWategy is used for global exploration. To meet the quality and diversity of initial solutions required by the scatter search method, we incorporate the greedy randomized adaptive search procedure (GRASP) with the clustering method to generate initial solutions.Ex perimental results show that the proposed scatter search algorithm is capable of partitioning large benchmark circuits,and yields re suits better than those of the wellknown multilevel partitioning package hMetis.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2012年第6期1207-1212,共6页
Acta Electronica Sinica
基金
国家重点基础研究发展规划(973计划)项目(No.2011CB808000)
国家自然科学基金(No.61170308
No.61070020
No.10931003)
教育部高校博士点专项科研基金(No.20093514110004)