VLSI电路划分问题的分散搜索算法

Scatter Search Algorithm for VLSI Circuit Partitioning

电路划分是超大规模集成电路(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.