VLSI标准单元阵列布局问题的一个高效遗传算法  

An Effective Genetic Algorithm for VLSI Standard Cell Array Placement

作　　者：陈雄峰[1] 吴景岚[1,2] 朱文兴[2] 

机构地区：[1]闽江学院计算机科学系,福建福州350108 [2]福州大学离散数学与理论计算机科学研究中心,福建福州350108

出　　处：《厦门大学学报（自然科学版）》2014年第6期797-803,共7页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(61170308)

摘　　要：研究可有效处理几万至百万个单元规模VLSI标准单元阵列布局问题的遗传算法,使之能在合理的时间内获得高质量的布局结果.为了提高布局质量,针对布局的二维特性设计了新型线网交叉算子和局部搜索技术,并提出了三阶段算法框架以协调算法的全局搜索和局部搜索.为了降低算法的时间和空间复杂度,使算法可处理大规模问题,采用了交叉算子局部化和小规模种群的思想,同时使用了多种保持种群多样性的策略以提高小规模种群的进化性能.对Peko suite3、4标准测试电路的实验结果表明,基于这些策略的遗传算法是有效的.This paper presents a genetic algorithm for solving the problem of VLSI standard cell array placement with up to tens of thousands to millions of cells,and for obtaining high quality placement results in a reasonable running time.For producing high quality placement results,a new kind of crossover operator on nets and a new type of local search method for the 2-D placement problem are designed,and an innovative algorithm framework with three phases is proposed to coordinate the global search and the local search of this algorithm.For the purpose of enabling the algorithm to hundle large-scale problem,the ideas of crossover localization,and small size population are adopted to reduce time and space complexities of the genetic algorithm.Meanwhile,various strategies for maintaining population diversity are used to improve the evolution performance of a small size population.Experimental results on Peko suite3 and suite4benchmark circuits verify that the genetic algorithm with these strategies is efficient.

关 键 词：标准单元阵列布局 遗传算法 线网交叉 局部搜索. 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]