VLSI标准单元布局问题的增强型混合遗传模拟退火算法

An Enhanced Hybrid Genetic Simulated Annealing Algorithm for VLSI Standard Cell Placement

提出有效处理百万个VLSI标准单元布局问题的混合遗传模拟退火算法.首先采用小规模种群、动态更新种群和交叉局部化策略,并协调全局与局部搜索,使遗传算法可处理超大规模标准单元布局问题.然后为进一步提高算法进化效率和布局结果质量,将爬山和模拟退火方法引入遗传算法框架及其算子内部流程,设计高效的线网-循环交叉算子和局部搜索算法.标准单元阵列布局侧重使用爬山法,非阵列布局侧重使用模拟退火方法.Peko suite3、Peko suite4和ISPD04标准测试电路的实验结果表明,该算法可在合理运行时间内有效提高布局结果质量.

A hybrid genetic simulated annealing algorithm is presented for solving the problem of VLSI standard cell placement with up to millions of cells. Firstly,to make genetic algorithm be capable of handling very large scale of standard cell placement, the strategies of small size population, dynamic updating population,and crossover localization are adopted,and the global search and local search of genetic algorithm are coordinated. Then,by introducing hill climbing（HC） and simulated annealing（SA） into the framework of genetic algorithm and the internal procedure of its operators,an effective crossover operator named Net Cycle Crossover and local search algorithms for the placement problem are designed to further improve the evolutionary efficiency of the algorithm and the quality of its placement results. In the algorithm procedure,HC method and SA method focus on array placement and non-array placement respectively. The experimental results on Peko suite3,Peko suite4 and ISPD04 benchmark circuits show that the proposed algorithm can handle array and non-array placements with 10,000 ~ 1,600,000 cells and 10,000 ~ 210,000 cells respectively,and can effectively improve the quality of placement results in a reasonable running time.