电子学报2012，Vol.40Issue(6)：1207-1212,6.DOI:10.3969/j.issn.0372-2112.2012.06.023
VLSI电路划分问题的分散搜索算法
Scatter Search Algorithm for VLSI Circuit Partitioning
摘要
Abstract
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-Matthey-ses 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.关键词
分散搜索/GRASP/FM算法/电路划分Key words
scatter search/ GRASP/ FM algorithm/ circuit partitioning分类
信息技术与安全科学引用本文复制引用
朱文兴,程泓..VLSI电路划分问题的分散搜索算法[J].电子学报,2012,40(6):1207-1212,6.基金项目
国家重点基础研究发展规划(973计划)项目(No.2011CB808000) （973计划）
国家自然科学基金(No.61170308,No.61070020,No.10931003) （No.61170308,No.61070020,No.10931003）
教育部高校博士点专项科研基金(No.20093514110004) （No.20093514110004）
