基于精英策略的遗传算法在功能验证中的应用

2016-11-21罗小华夏顺兴

华东理工大学学报(自然科学版) 2016年5期

关键词：覆盖率适应度精英

王磊, 罗小华, 俞淼, 夏顺兴

(浙江大学超大规模集成电路研究所,杭州 310027)

基于精英策略的遗传算法在功能验证中的应用

王磊, 罗小华, 俞淼, 夏顺兴

(浙江大学超大规模集成电路研究所,杭州 310027)

针对集成电路功能验证中覆盖率收敛较慢的问题,通过分析简单遗传算法(SGA)中精英个体的特征,提出了一种应用于功能验证的精英策略。将本代优秀个体和本代适应度高的历史优秀个体视为精英个体,给予额外交叉机会。基于本文策略的精英遗传算法(EGA)可得到覆盖率广、重复性低的验证向量,缩短功能验证的时间。采用互相关函数的硬件计算单元作为验证模型,在Matlab中模拟功能验证的过程,实验结果表明:与SGA相比,EGA使验证时间缩短了14.8%,功能覆盖率从93%提高到 95%,有效地提高了功能验证效率。

集成电路验证; 功能覆盖率; 遗传算法; 精英策略

随着集成电路产业的发展,设计的复杂度越来越高,如何验证功能定义与寄存器传输级 (RTL)描述的一致性,已成为当前设计过程中的关键问题[1]。以功能覆盖率为驱动的验证是当前的主流方法[2-3],这类方法首先定义了验证模型(Design Under Verification,DUV)的功能覆盖点及目标覆盖率,使用高级验证语言搭建层次化验证平台,并自动生成服从均匀分布的全随机受限向量,当覆盖率未达到目标值时对DUV施加激励。但随着功能覆盖率的提升,变小的未覆盖区域使得生成的随机向量落在该区域的概率迅速减小,导致在验证后期功能覆盖率的收敛减慢,从而严重影响了验证效率。

利用遗传算法(Genetic Algorithm,GA)提高功能验证效率是当前的研究热点。文献[4]将功能覆盖率信息反馈给GA进行遗传操作,基于GA收敛速度快、可靠性高的特性产生优秀验证向量。文献[5]提出在每个向量的编码中增加权重、上界、下界3个基因,并将此引入向量适应度的计算。文献[6]将翻转覆盖率引入适应度函数,并根据功能覆盖率的反馈对交叉率、变异率进行自适应调整。文献[7]对GA中不同的选择、交叉、变异算子在功能验证中的性能进行比较,得到了由比例选择算子、均匀交叉算子以及二元变异算子组成的遗传算法。

上述研究将GA应用于集成电路功能验证领域,在一定程度上提升了验证的效率,但所用的GA仅包含选择、交叉、变异操作,属于简单遗传算法(Simple Genetic Algorithm,SGA)。文献[8]利用齐次有限Markov链证明了SGA不具有全局收敛性,这导致在验证后期功能覆盖率收敛速度相对缓慢。文献[9]证明了若保留每一代的最优个体,则GA将收敛到全局最优。精英个体是GA在群体进化过程中适应度最高、拥有最好基因结构的个体,对精英个体的有效利用将加速GA收敛。因此本文对精英个体展开分析,提出了一种由构建精英集、精英交叉等组成的精英策略,并根据该策略获得应用于功能验证中的精英遗传算法(Elite Genetic Algorithm,EGA),用以提升验证效率。

1 遗传算法

1.1 应用于功能验证中的遗传算法

遗传算法模拟了自然界中生物的进化过程,通过自然选择、交叉和变异等遗传操作,实现个体适应度的提高,以达到寻找求解问题最优解的目标。基于GA的功能验证的结构如图1所示。验证中GA根据DUV反馈的功能覆盖率进行遗传操作,并选择适应度较高的验证向量作为DUV的输入进行仿真,仿真结束后将新的功能覆盖率信息反馈给GA,并重复之前的操作。

图1 基于遗传算法的功能验证结构Fig.1 Structure of functional verification based on GA

整个过程的关键在于GA对解空间的搜索性能,其搜索到验证向量的质量决定了功能覆盖率的增长速度。传统方法中用到的SGA不是全局收敛的,传统的交叉、变异算子对优秀基因段具有破坏作用,导致遗传算法的搜索能力在最优解附近降低,不易收敛。为提高功能验证的效率,需要对GA中的优秀基因段进行有效利用。

1.2 遗传算法中的精英个体

精英个体是GA群体进化过程中适应度最高的个体,与全局最优解的部分基因相同,具有优秀的基因内容。全局最优解是使功能覆盖率达到收敛的验证向量,设为r(X)=[r1,r2,…,rL],其中L为基因段的长度。群体中的普通个体为s(X)=[s1,s2,…,sL],精英个体为e(X)=[e1,e2,…,eL],其中e(X)与r(X)共有基因段rm,…,rn。

在信息编码中,两个码字中对应比特取值不同的比特数称为这两个码字的海明距离。在GA中个体间的海明距离代表了两者的差异,海明距离越大表明个体间的差别越大。

在随机的验证环境中,个体中每一基因位的取值服从0,1分布,Px=0=Px=1=1/2。由海明距离的定义可得式(1)、式 (2)。

(1)

其中:Hds为s(X)与r(X)的海明距离;Ps为其一步转移概率。

(2)

其中:Hde为e(X)与r(X)的海明距离;Pe为其一步转移概率。

随着种群进化的演进,e(X)与r(X)的共有基因段长度会逐渐增加,在进化后期,n-m+1>>1,则Hx>>He,Px<

2 算法分析与选取

2.1精英策略

2.1.1精英保留与精英交叉精英保留及精英交叉是两种常见的精英策略。

精英保留令本代群体中出现的优质个体不参与交叉和变异操作,直接保留到下一代,过程如图2所示。可以发现它能有效地将优质基因保存下来,防止在交叉和变异操作中较长的精英基因遭到破坏,但对于精英个体仅使用保存操作,未进行充分利用。

图2 精英保留策略Fig.2 Strategy of elite retaining

精英交叉将上一代的最优解保存下来,除对群体实施传统的交叉操作外,根据给定的概率使精英个体与群体中的每一个个体进行交叉,过程如图3所示。它为精英个体提供更多的交叉机会,增加了精英基因在群体中的存有量,但没有良好地保存精英个体,使其在变异过程中造到破坏,无法继续使用。

图3 精英交叉策略Fig.3 Strategy of elite crossing

2.1.2改进的精英策略综合分析上述两种精英策略的优缺点,并结合功能覆盖率仿真的实际过程,本文提出了一种应用于功能验证领域的精英策略,既可以使优秀的精英向量得到保留,又可以对其进行充分的利用。精英策略在第t代的运算过程如图4所示,运算步骤如下:

(1) 对于第t代群体St(X),设功能覆盖率达到ct;对于St(X)中的每个向量,产生一个随机数,若该随机数小于ct,则令精英集Et(X)中的一个向量与St(X)进行交叉;若Et(X)的每个向量均得到使用,则循环使用Et(X)中的元素;

(2) 对于第t代群体St(X),在完成交叉、变异的操作后,计算[St(X),Et(X)]中的每一个向量的适应度,选出所有适应度最高的向量组成新的精英集Et+1(X)。

图4 改进的精英策略在第t代的遗传过程Fig.4 Genetic processes in generation tof improved elite strategy

2.2 功能验证中的精英策略

2.2.1 适应度函数在遗传算法中,个体的适应度决定着该个体被遗传到下一代群体的概率,适应度函数作为计算适应度的标准,对算法的收敛速度和方向至关重要。

本文采用如下适应度函数:

(3)

其中:T表示目标功能覆盖点的数量;Cov(t)-Cov(t-1)表示连续两代的功能覆盖率之差;T[Cov(t)-Cov(t-1)]为新发现的覆盖点数;Count(X)为最近5代中向量X出现的次数。

相较于参考文献[2]中的适应度函数,该适应度函数具有以下优点:

(1) 对覆盖率提升有贡献的精英向量适应度较大,与普通向量区别显著;

(2) 仅保留5代向量数据,计算开销小,有效地加快仿真速度。

2.2.2 精英向量集 SGA中每一代往往只产生单一精英,精英空间的容量为1。而在功能覆盖率仿真中,有较大概率产生多个精英个体,这些个体具有良好的基因结构,均能促进功能覆盖率的收敛。若仅保留1个会造成损失,本文建立精英向量集E(X),将优秀个体有效地保存下来。第t代精英集的构建方式如图5所示。

图5 第t代精英集的构建方式Fig.5 Structure of elite collection in generation t

(1) 精英向量集E(X)中的元素。本代向量组成的精英集P(X),即P(X)⊆St(X);P(X)包含两种向量,一种是直接造成覆盖率提升的向量;另一种是功能覆盖率未提升时,在近5代遗传过程中出现次数少的向量。这是因为出现频繁但未能提高覆盖率的向量,其发现新向量的能力较差;而出现次数较少的向量则具有提高覆盖率的潜质,可作为精英向量。

(2) 构建上一代精英组成的精英集Q(X),即Q(X)⊆Et-1(X)。第t-1代精英向量进行交叉、变异操作后,有可能不被保留在第t代群体中,其基因仅利用了一代。由于与第t代群体仅仅相隔一代,上述精英基因很可能适用于第t代群体的环境,如果此时将其抛弃,则其无法将精英基因充分地传递给子代。本文对第t-1代的精英向量进行考察,计算它们在第t代的适应度,筛选出适应于本代环境的精英向量加以使用。

表1 精英向量集的结构Table 1 Structure of elite collection

表2示出了选用3种精英集结构,在达到90%功能覆盖率时所需要的仿真时间(10次实验均值)。可观察到选用结构1时的性能最优。

表2 不同的精英向量集结构与验证速度Table 2 Relationship of different structures of elite collection and velocity of verification

2.2.3 精英交叉概率精英交叉概率Pkc是指群体中的个体产生一个随机数,若该随机数小于精英交叉概率,则该个体与精英向量发生精英交叉。Pkc决定了精英向量在算法中的参与程度,大小合适的Pkc能够有效促进功能覆盖率收敛。在功能覆盖率仿真的过程中,e(X)与s(X)的海明距离Hd=Hde+Hds,其中Hde为e(X)和s(X)在精英基因段的海明距离,Hds为非精英基因段的海明距离。

精英基因段更为优良且不易获得,普通基因需要进化为精英基因时,在该基因段位置内每一位的平均转移概率Pe要大于0.5;令Pe=(1+α)/2,其中0<α<1,则可得公式(4)。

(4)

在仿真初期覆盖率较低,n-m+1较小,导致Hd较小,说明精英个体与普通个体差别不大,此时普通交叉功能可基本实现精英交叉的功能。在仿真后期覆盖率较高,n-m+1较大,导致Hd较大,精英个体相对于普通个体优势很大,为了使精英基因迅速作用于种群进化,需要尽可能多地进行精英交叉运算。为加快功能覆盖率收敛,Pkc需要在仿真期间进行自适应调整,Pkc应是以功能覆盖率为变量的增函数。

表3示出了使用3种常见函数作为Pkc,功能覆盖率达到90%时的仿真时间(10次实验均值),可以发现单调性递增的函数仿真速度更快。

表3 不同的精英交叉覆盖率与验证速度Table 3 Relationship of different elite-crossing probability and verification velocity

2.3 精英策略在功能验证中的实现

相较于SGA,EGA除了进行交叉、变异操作外还需构建精英集,进行精英交叉。算法流程如图6所示,具体步骤如下:

(1) 初始化种群。

(a) 根据具体的验证问题确定合适的种群大小popsize,popsize若取太大,会增加计算开销;若取太小,会丧失种群多样性,影响进化速度;

(b) 随机生成popsize个二进制向量。

(2) 建立初始精英集。

(a) 通过VCS的统计工具或自有逻辑计算覆盖率Cov1,用以控制循环过程,并作为适应度函数f(X)的输入;

(b) 根据f(X)计算向量的适应度fitness,优秀的f(X)可以有效地区分向量的优劣,并具有较低的计算开销;

(3) 进行计算循环。

(a) 进行交叉操作,交叉率Pc在遗传进化中取值较大,一般为0.7～0.9;

(b) 进行精英交叉操作,精英交叉概率Pkc根据功能覆盖率进行自适应调整;

(d) 构建新一代的精英向量集;

(e) 判断是否达到目标覆盖率Covtarget,若满足则停止仿真。

图6 功能仿真中精英策略的实现Fig.6 Realization of elite strategy in functional verification

3 实验与结果分析

3.1 实验对象及参数选取

实验以10位NCC(互相关函数)运算单元作为验证模型,该运算单元主要为实时跟踪系统中的互相关函数进行加速。

NCC运算单元的验证目的是确保其运算结果功能定义一致,功能覆盖率达到较高程度。本文在Matlab中搭建如图1所示的验证环境,包括计算单元的软件模型、覆盖率统计模型和GA,进行功能覆盖率验证。参数设置为染色体链长L=10,种群大小popsize=500;采用单点交叉、单点变异算子,其中Pc=0.8,Pm=0.15;采用结构1构建精英集,精英交叉概率为Pkc=Cov。

3.2 结果分析

图7示出了SGA和EGA在达到相同功能覆盖率所用的仿真时间。由图7得到,当功能覆盖率达到50%时,EGA消耗的时间略大于SGA;当功能覆盖率大于50%时,EGA消耗的时间比SGA更少,并且随着功能覆盖率逐渐收敛,EGA带来时间上的优化逐渐明显;业内常用90%作为功能覆盖率的收敛目标,在本实验中,当功能覆盖率为90%时,相较于SGA,EGA所用的时间减少约14.8%。

图7 两种方法验证速度的比较Fig.7 Comparison of verification velocity between EGA and SGA

图8示出了功能覆盖率在进入缓慢增长的状态前,SGA能达到的覆盖率约为93%,EGA达到的覆盖率约为95%,较SGA提升了约2%,收敛效果更好。

图8 两种方法功能覆盖率的比较Fig.8 Comparison of functional coverage between EGA and SGA

4 结论

本文首先对遗传算法中的精英个体进行分析,以精英保留、精英交叉为基础提出了一种改进型的

精英策略,并结合功能验证的具体环境,得到了适用于功能验证的精英遗传算法(EGA)。实验结果显示,EGA相较于SGA在收敛速度和达到的功能覆盖率上均有所提升,约减少了14.8%的仿真时间,功能覆盖率从约93%提高到约95%,显著提高了验证效率。

[1] VENERIS A,KENG B,SAFARPOUR S.From RTL to silicon:The case for automated debug[C]//2011 16th Asia and South Pacific Design Automation Conference (ASP-DAC).Yokohama,Japan: IEEE,2011:306-310.

[2] YUN Y N,KIM J B,KIM N D,etal.Beyond UVM for practical SoC verification[C]// 2011 International SoC Design Conference (ISOCC).Jeju: IEEE,2011:158-162.

[3] XU M H,YU Q,GUO A Y.Design and realization of efficient verification platform based on system verilog[J].Advanced Materials Research,2014,945:1903-1907.

[4] YANG R,WU L,GUO J,etal. The research and implement of an advanced function coverage based verification environment[C]// 7th International Conference on ASIC,2007.ASICON′07.USA:IEEE,2007:1253-1256.

[5] SAMARAH A,HABIBI A,TAHAR S,etal. Automated coverage directed test generation using a cell-based genetic algorithm[C]//IEEE International High Level Design Validation and Test Workshop.Piscataway:IEEE,2006:19-26.

[6] 苏琳琳,张晓林.利用自适应遗传算法的芯片功能验证自动测试[J].应用科学学报,2011,29(6):631-636.

[7] 高史义,罗小华,卢宇峰,等.基于遗传算法的功能覆盖率收敛技术[J].浙江大学学报(工学版),2015,49(8):1509-1515.

[8] RUDOLPH G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks,1994,5(1):96-101.

[9] EIBEN A E,AARTS E H L,VAN HEE K M.Global Convergence of Genetic Algorithms:A Markov Chain Analysis[M]//Parallel Problem Solving from Nature.Berlin Heidelberg :Springer,1991:3-12.

Genetic Algorithm Used in Functional Verification Based on Elite Strategy

WANG Lei, LUO Xiao-hua, YU Miao, XIA Shun-xing

(Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China)

This paper addresses the problem of slow convergence occurring in integrated circuit functional verification.By analyzing the features of elites in simple genetic algorithm (SGA),this paper proposes an elite strategy for functional coverage,in which elites are selected in the qualified group and crossed by normal group.Elite genetic algorithm (EGA) based on elite strategy may generate verification vectors with high coverage and low reproducibility such that the functional verification can be accelerated.By adopting an NCC-computing cell as the verification model,the simulation on the function verification process in Matlab is made,whose results show that compared with SGA,EGA can reduce simulation time for 14.8% and functional coverage increase from 93% to 95%.The efficiency of integrated circuit functional verification is effectively raised.

integrated circuit verification; functional coverage; genetic algorithm; elite strategy

1006-3080(2016)05-0676-06

10.14135/j.cnki.1006-3080.2016.05.0114

2015-11-26

浙江省自然科学基金(LY15F040001)

王磊(1992-),男,硕士生,从事超大规模集成电路研究。E-mail:wanglei@vlsi.zju.edu.cn

罗小华,E-mail:luoxh@vlsi.zju.edu.cn

TN47