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

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.

Scatter Search Algorithm for VLSI Circuit Partitioning

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 NP-hard combinatorial optimization problem.In this paper,we propose a scatter search method for the problem,which incorporates the single-vertex-move based Fiduccia-Mattheyses algorithm(FM) within the scatter search framework.The FM algorithm is used for local exploitation,while the scatter search strategy 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.Experimental results show that the proposed scatter search algorithm is capable of partitioning large benchmark circuits,and yields results better than those of the well-known multilevel partitioning package hMetis.