基于精英策略的遺傳算法在功能驗(yàn)證中的應(yīng)用

王 磊, 羅小華, 俞 淼, 夏順興

(浙江大學(xué)超大規(guī)模集成電路研究所,杭州 310027)

?

基于精英策略的遺傳算法在功能驗(yàn)證中的應(yīng)用

王 磊, 羅小華, 俞 淼, 夏順興

(浙江大學(xué)超大規(guī)模集成電路研究所,杭州 310027)

針對集成電路功能驗(yàn)證中覆蓋率收斂較慢的問題,通過分析簡單遺傳算法(SGA)中精英個體的特征,提出了一種應(yīng)用于功能驗(yàn)證的精英策略。將本代優(yōu)秀個體和本代適應(yīng)度高的歷史優(yōu)秀個體視為精英個體,給予額外交叉機(jī)會?；诒疚牟呗缘木⑦z傳算法(EGA)可得到覆蓋率廣、重復(fù)性低的驗(yàn)證向量,縮短功能驗(yàn)證的時間。采用互相關(guān)函數(shù)的硬件計(jì)算單元作為驗(yàn)證模型,在Matlab中模擬功能驗(yàn)證的過程,實(shí)驗(yàn)結(jié)果表明:與SGA相比,EGA使驗(yàn)證時間縮短了14.8%,功能覆蓋率從93%提高到 95%,有效地提高了功能驗(yàn)證效率。

集成電路驗(yàn)證; 功能覆蓋率; 遺傳算法; 精英策略

隨著集成電路產(chǎn)業(yè)的發(fā)展,設(shè)計(jì)的復(fù)雜度越來越高,如何驗(yàn)證功能定義與寄存器傳輸級 (RTL)描述的一致性,已成為當(dāng)前設(shè)計(jì)過程中的關(guān)鍵問題[1]。以功能覆蓋率為驅(qū)動的驗(yàn)證是當(dāng)前的主流方法[2-3],這類方法首先定義了驗(yàn)證模型(Design Under Verification,DUV)的功能覆蓋點(diǎn)及目標(biāo)覆蓋率,使用高級驗(yàn)證語言搭建層次化驗(yàn)證平臺,并自動生成服從均勻分布的全隨機(jī)受限向量,當(dāng)覆蓋率未達(dá)到目標(biāo)值時對DUV施加激勵。但隨著功能覆蓋率的提升,變小的未覆蓋區(qū)域使得生成的隨機(jī)向量落在該區(qū)域的概率迅速減小,導(dǎo)致在驗(yàn)證后期功能覆蓋率的收斂減慢,從而嚴(yán)重影響了驗(yàn)證效率。

利用遺傳算法(Genetic Algorithm,GA)提高功能驗(yàn)證效率是當(dāng)前的研究熱點(diǎn)。文獻(xiàn)[4]將功能覆蓋率信息反饋給GA進(jìn)行遺傳操作,基于GA收斂速度快、可靠性高的特性產(chǎn)生優(yōu)秀驗(yàn)證向量。文獻(xiàn)[5]提出在每個向量的編碼中增加權(quán)重、上界、下界3個基因,并將此引入向量適應(yīng)度的計(jì)算。文獻(xiàn)[6]將翻轉(zhuǎn)覆蓋率引入適應(yīng)度函數(shù),并根據(jù)功能覆蓋率的反饋對交叉率、變異率進(jìn)行自適應(yīng)調(diào)整。文獻(xiàn)[7]對GA中不同的選擇、交叉、變異算子在功能驗(yàn)證中的性能進(jìn)行比較,得到了由比例選擇算子、均勻交叉算子以及二元變異算子組成的遺傳算法。

上述研究將GA應(yīng)用于集成電路功能驗(yàn)證領(lǐng)域,在一定程度上提升了驗(yàn)證的效率,但所用的GA僅包含選擇、交叉、變異操作,屬于簡單遺傳算法(Simple Genetic Algorithm,SGA)。文獻(xiàn)[8]利用齊次有限Markov鏈證明了SGA不具有全局收斂性,這導(dǎo)致在驗(yàn)證后期功能覆蓋率收斂速度相對緩慢。文獻(xiàn)[9]證明了若保留每一代的最優(yōu)個體,則GA將收斂到全局最優(yōu)。精英個體是GA在群體進(jìn)化過程中適應(yīng)度最高、擁有最好基因結(jié)構(gòu)的個體,對精英個體的有效利用將加速GA收斂。因此本文對精英個體展開分析,提出了一種由構(gòu)建精英集、精英交叉等組成的精英策略,并根據(jù)該策略獲得應(yīng)用于功能驗(yàn)證中的精英遺傳算法(Elite Genetic Algorithm,EGA),用以提升驗(yàn)證效率。

1 遺傳算法

1.1 應(yīng)用于功能驗(yàn)證中的遺傳算法

遺傳算法模擬了自然界中生物的進(jìn)化過程,通過自然選擇、交叉和變異等遺傳操作,實(shí)現(xiàn)個體適應(yīng)度的提高,以達(dá)到尋找求解問題最優(yōu)解的目標(biāo)?；贕A的功能驗(yàn)證的結(jié)構(gòu)如圖1所示。驗(yàn)證中GA根據(jù)DUV反饋的功能覆蓋率進(jìn)行遺傳操作,并選擇適應(yīng)度較高的驗(yàn)證向量作為DUV的輸入進(jìn)行仿真,仿真結(jié)束后將新的功能覆蓋率信息反饋給GA,并重復(fù)之前的操作。

圖1 基于遺傳算法的功能驗(yàn)證結(jié)構(gòu)Fig.1 Structure of functional verification based on GA

整個過程的關(guān)鍵在于GA對解空間的搜索性能,其搜索到驗(yàn)證向量的質(zhì)量決定了功能覆蓋率的增長速度。傳統(tǒng)方法中用到的SGA不是全局收斂的,傳統(tǒng)的交叉、變異算子對優(yōu)秀基因段具有破壞作用,導(dǎo)致遺傳算法的搜索能力在最優(yōu)解附近降低,不易收斂。為提高功能驗(yàn)證的效率,需要對GA中的優(yōu)秀基因段進(jìn)行有效利用。

1.2 遺傳算法中的精英個體

精英個體是GA群體進(jìn)化過程中適應(yīng)度最高的個體,與全局最優(yōu)解的部分基因相同,具有優(yōu)秀的基因內(nèi)容。全局最優(yōu)解是使功能覆蓋率達(dá)到收斂的驗(yàn)證向量,設(shè)為r(X)=[r1,r2,…,rL],其中L為基因段的長度。群體中的普通個體為s(X)=[s1,s2,…,sL],精英個體為e(X)=[e1,e2,…,eL],其中e(X)與r(X)共有基因段rm,…,rn。

在信息編碼中,兩個碼字中對應(yīng)比特取值不同的比特?cái)?shù)稱為這兩個碼字的海明距離。在GA中個體間的海明距離代表了兩者的差異,海明距離越大表明個體間的差別越大。

在隨機(jī)的驗(yàn)證環(huán)境中,個體中每一基因位的取值服從0,1分布,Px=0=Px=1=1/2。由海明距離的定義可得式(1)、式 (2)。

(1)

其中:Hds為s(X)與r(X)的海明距離;Ps為其一步轉(zhuǎn)移概率。

(2)

其中:Hde為e(X)與r(X)的海明距離;Pe為其一步轉(zhuǎn)移概率。

隨著種群進(jìn)化的演進(jìn),e(X)與r(X)的共有基因段長度會逐漸增加,在進(jìn)化后期,n-m+1>>1,則Hx>>He,Px<

2 算法分析與選取

2.1精英策略

2.1.1精英保留與精英交叉 精英保留及精英交叉是兩種常見的精英策略。

精英保留令本代群體中出現(xiàn)的優(yōu)質(zhì)個體不參與交叉和變異操作,直接保留到下一代,過程如圖2所示?？梢园l(fā)現(xiàn)它能有效地將優(yōu)質(zhì)基因保存下來,防止在交叉和變異操作中較長的精英基因遭到破壞,但對于精英個體僅使用保存操作,未進(jìn)行充分利用。

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

精英交叉將上一代的最優(yōu)解保存下來,除對群體實(shí)施傳統(tǒng)的交叉操作外,根據(jù)給定的概率使精英個體與群體中的每一個個體進(jìn)行交叉,過程如圖3所示。它為精英個體提供更多的交叉機(jī)會,增加了精英基因在群體中的存有量,但沒有良好地保存精英個體,使其在變異過程中造到破壞,無法繼續(xù)使用。

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

2.1.2改進(jìn)的精英策略 綜合分析上述兩種精英策略的優(yōu)缺點(diǎn),并結(jié)合功能覆蓋率仿真的實(shí)際過程,本文提出了一種應(yīng)用于功能驗(yàn)證領(lǐng)域的精英策略,既可以使優(yōu)秀的精英向量得到保留,又可以對其進(jìn)行充分的利用。精英策略在第t代的運(yùn)算過程如圖4所示,運(yùn)算步驟如下:

(1) 對于第t代群體St(X),設(shè)功能覆蓋率達(dá)到ct;對于St(X)中的每個向量,產(chǎn)生一個隨機(jī)數(shù),若該隨機(jī)數(shù)小于ct,則令精英集Et(X)中的一個向量與St(X)進(jìn)行交叉;若Et(X)的每個向量均得到使用,則循環(huán)使用Et(X)中的元素;

(2) 對于第t代群體St(X),在完成交叉、變異的操作后,計(jì)算[St(X),Et(X)]中的每一個向量的適應(yīng)度,選出所有適應(yīng)度最高的向量組成新的精英集Et+1(X)。

圖4 改進(jìn)的精英策略在第t代的遺傳過程Fig.4 Genetic processes in generation tof improved elite strategy

2.2 功能驗(yàn)證中的精英策略

2.2.1 適應(yīng)度函數(shù) 在遺傳算法中,個體的適應(yīng)度決定著該個體被遺傳到下一代群體的概率,適應(yīng)度函數(shù)作為計(jì)算適應(yīng)度的標(biāo)準(zhǔn),對算法的收斂速度和方向至關(guān)重要。

本文采用如下適應(yīng)度函數(shù):

(3)

其中:T表示目標(biāo)功能覆蓋點(diǎn)的數(shù)量;Cov(t)-Cov(t-1)表示連續(xù)兩代的功能覆蓋率之差;T[Cov(t)-Cov(t-1)]為新發(fā)現(xiàn)的覆蓋點(diǎn)數(shù);Count(X)為最近5代中向量X出現(xiàn)的次數(shù)。

相較于參考文獻(xiàn)[2]中的適應(yīng)度函數(shù),該適應(yīng)度函數(shù)具有以下優(yōu)點(diǎn):

(1) 對覆蓋率提升有貢獻(xiàn)的精英向量適應(yīng)度較大,與普通向量區(qū)別顯著;

(2) 僅保留5代向量數(shù)據(jù),計(jì)算開銷小,有效地加快仿真速度。

2.2.2 精英向量集 SGA中每一代往往只產(chǎn)生單一精英,精英空間的容量為1。而在功能覆蓋率仿真中,有較大概率產(chǎn)生多個精英個體,這些個體具有良好的基因結(jié)構(gòu),均能促進(jìn)功能覆蓋率的收斂。若僅保留1個會造成損失,本文建立精英向量集E(X),將優(yōu)秀個體有效地保存下來。第t代精英集的構(gòu)建方式如圖5所示。

圖5 第t代精英集的構(gòu)建方式Fig.5 Structure of elite collection in generation t

(1) 精英向量集E(X)中的元素 。 本代向量組成的精英集P(X),即P(X)?St(X);P(X)包含兩種向量,一種是直接造成覆蓋率提升的向量;另一種是功能覆蓋率未提升時,在近5代遺傳過程中出現(xiàn)次數(shù)少的向量。這是因?yàn)槌霈F(xiàn)頻繁但未能提高覆蓋率的向量,其發(fā)現(xiàn)新向量的能力較差;而出現(xiàn)次數(shù)較少的向量則具有提高覆蓋率的潛質(zhì),可作為精英向量。

(2) 構(gòu)建上一代精英組成的精英集Q(X),即Q(X)?Et-1(X)。第t-1代精英向量進(jìn)行交叉、變異操作后,有可能不被保留在第t代群體中,其基因僅利用了一代。由于與第t代群體僅僅相隔一代,上述精英基因很可能適用于第t代群體的環(huán)境,如果此時將其拋棄,則其無法將精英基因充分地傳遞給子代。本文對第t-1代的精英向量進(jìn)行考察,計(jì)算它們在第t代的適應(yīng)度,篩選出適應(yīng)于本代環(huán)境的精英向量加以使用。

表1 精英向量集的結(jié)構(gòu)Table 1 Structure of elite collection

表2示出了選用3種精英集結(jié)構(gòu),在達(dá)到90%功能覆蓋率時所需要的仿真時間(10次實(shí)驗(yàn)均值)?？捎^察到選用結(jié)構(gòu)1時的性能最優(yōu)。

表2 不同的精英向量集結(jié)構(gòu)與驗(yàn)證速度Table 2 Relationship of different structures of elite collection and velocity of verification

2.2.3 精英交叉概率 精英交叉概率Pkc是指群體中的個體產(chǎn)生一個隨機(jī)數(shù),若該隨機(jī)數(shù)小于精英交叉概率,則該個體與精英向量發(fā)生精英交叉。Pkc決定了精英向量在算法中的參與程度,大小合適的Pkc能夠有效促進(jìn)功能覆蓋率收斂。在功能覆蓋率仿真的過程中,e(X)與s(X)的海明距離Hd=Hde+Hds,其中Hde為e(X)和s(X)在精英基因段的海明距離,Hds為非精英基因段的海明距離。

精英基因段更為優(yōu)良且不易獲得,普通基因需要進(jìn)化為精英基因時,在該基因段位置內(nèi)每一位的平均轉(zhuǎn)移概率Pe要大于0.5;令Pe=(1+α)/2,其中0<α<1,則可得公式(4)。

(4)

在仿真初期覆蓋率較低,n-m+1較小,導(dǎo)致Hd較小,說明精英個體與普通個體差別不大,此時普通交叉功能可基本實(shí)現(xiàn)精英交叉的功能。在仿真后期覆蓋率較高,n-m+1較大,導(dǎo)致Hd較大,精英個體相對于普通個體優(yōu)勢很大,為了使精英基因迅速作用于種群進(jìn)化,需要盡可能多地進(jìn)行精英交叉運(yùn)算。為加快功能覆蓋率收斂,Pkc需要在仿真期間進(jìn)行自適應(yīng)調(diào)整,Pkc應(yīng)是以功能覆蓋率為變量的增函數(shù)。

表3示出了使用3種常見函數(shù)作為Pkc,功能覆蓋率達(dá)到90%時的仿真時間(10次實(shí)驗(yàn)均值),可以發(fā)現(xiàn)單調(diào)性遞增的函數(shù)仿真速度更快。

表3 不同的精英交叉覆蓋率與驗(yàn)證速度Table 3 Relationship of different elite-crossing probability and verification velocity

2.3 精英策略在功能驗(yàn)證中的實(shí)現(xiàn)

相較于SGA,EGA除了進(jìn)行交叉、變異操作外還需構(gòu)建精英集,進(jìn)行精英交叉。算法流程如圖6所示,具體步驟如下:

(1) 初始化種群。

(a) 根據(jù)具體的驗(yàn)證問題確定合適的種群大小popsize,popsize若取太大,會增加計(jì)算開銷;若取太小,會喪失種群多樣性,影響進(jìn)化速度;

(b) 隨機(jī)生成popsize個二進(jìn)制向量。

(2) 建立初始精英集。

(a) 通過VCS的統(tǒng)計(jì)工具或自有邏輯計(jì)算覆蓋率Cov1,用以控制循環(huán)過程,并作為適應(yīng)度函數(shù)f(X)的輸入;

(b) 根據(jù)f(X)計(jì)算向量的適應(yīng)度fitness,優(yōu)秀的f(X)可以有效地區(qū)分向量的優(yōu)劣,并具有較低的計(jì)算開銷;

(c) 將fitness最大測試向量保存在精英集。

(3) 進(jìn)行計(jì)算循環(huán)。

(a) 進(jìn)行交叉操作,交叉率Pc在遺傳進(jìn)化中取值較大,一般為0.7～0.9;

(b) 進(jìn)行精英交叉操作,精英交叉概率Pkc根據(jù)功能覆蓋率進(jìn)行自適應(yīng)調(diào)整;

(c) 進(jìn)行變異操作,突變率Pm在遺傳進(jìn)化中取值較小,一般為0.01～0.2;

(d) 構(gòu)建新一代的精英向量集;

(e) 判斷是否達(dá)到目標(biāo)覆蓋率Covtarget,若滿足則停止仿真。

圖6 功能仿真中精英策略的實(shí)現(xiàn)Fig.6 Realization of elite strategy in functional verification

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)對象及參數(shù)選取

實(shí)驗(yàn)以10位NCC(互相關(guān)函數(shù))運(yùn)算單元作為驗(yàn)證模型,該運(yùn)算單元主要為實(shí)時跟蹤系統(tǒng)中的互相關(guān)函數(shù)進(jìn)行加速。

NCC運(yùn)算單元的驗(yàn)證目的是確保其運(yùn)算結(jié)果功能定義一致,功能覆蓋率達(dá)到較高程度。本文在Matlab中搭建如圖1所示的驗(yàn)證環(huán)境,包括計(jì)算單元的軟件模型、覆蓋率統(tǒng)計(jì)模型和GA,進(jìn)行功能覆蓋率驗(yàn)證。參數(shù)設(shè)置為染色體鏈長L=10,種群大小popsize=500;采用單點(diǎn)交叉、單點(diǎn)變異算子,其中Pc=0.8,Pm=0.15;采用結(jié)構(gòu)1構(gòu)建精英集,精英交叉概率為Pkc=Cov。

3.2 結(jié)果分析

圖7示出了SGA和EGA在達(dá)到相同功能覆蓋率所用的仿真時間。由圖7得到,當(dāng)功能覆蓋率達(dá)到50%時,EGA消耗的時間略大于SGA;當(dāng)功能覆蓋率大于50%時,EGA消耗的時間比SGA更少,并且隨著功能覆蓋率逐漸收斂,EGA帶來時間上的優(yōu)化逐漸明顯;業(yè)內(nèi)常用90%作為功能覆蓋率的收斂目標(biāo),在本實(shí)驗(yàn)中,當(dāng)功能覆蓋率為90%時,相較于SGA,EGA所用的時間減少約14.8%。

圖7 兩種方法驗(yàn)證速度的比較Fig.7 Comparison of verification velocity between EGA and SGA

圖8示出了功能覆蓋率在進(jìn)入緩慢增長的狀態(tài)前,SGA能達(dá)到的覆蓋率約為93%,EGA達(dá)到的覆蓋率約為95%,較SGA提升了約2%,收斂效果更好。

圖8 兩種方法功能覆蓋率的比較Fig.8 Comparison of functional coverage between EGA and SGA

4 結(jié) 論

本文首先對遺傳算法中的精英個體進(jìn)行分析,以精英保留、精英交叉為基礎(chǔ)提出了一種改進(jìn)型的

精英策略,并結(jié)合功能驗(yàn)證的具體環(huán)境,得到了適用于功能驗(yàn)證的精英遺傳算法(EGA)。實(shí)驗(yàn)結(jié)果顯示,EGA相較于SGA在收斂速度和達(dá)到的功能覆蓋率上均有所提升,約減少了14.8%的仿真時間,功能覆蓋率從約93%提高到約95%,顯著提高了驗(yàn)證效率。

[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] 蘇琳琳,張曉林.利用自適應(yīng)遺傳算法的芯片功能驗(yàn)證自動測試[J].應(yīng)用科學(xué)學(xué)報(bào),2011,29(6):631-636.

[7] 高史義,羅小華,盧宇峰,等.基于遺傳算法的功能覆蓋率收斂技術(shù)[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),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

浙江省自然科學(xué)基金(LY15F040001)

王 磊(1992-),男,碩士生,從事超大規(guī)模集成電路研究。E-mail:wanglei@vlsi.zju.edu.cn

羅小華,E-mail:luoxh@vlsi.zju.edu.cn

TN47

A