通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法

1、第 21 卷 第 4 期2009 年 4 月計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)JO U RN A L O F COM PU T ER AID ED D ESIG N & COM P U T ER G RA PH ICSVo l. 21, N o. 4 A pr. , 2009通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法1, 21, 211, 2傅 亮1) ( 中國(guó)2) ( 中國(guó)盧 鼎計(jì)算技術(shù)院ac cn)孫 愿微處理器技術(shù)00 90)00049)( ul ang c摘 要覆蓋率驅(qū)動(dòng)的驗(yàn)證是功能驗(yàn)證的重要方法, 但功能覆蓋定義的性和手工調(diào)整驗(yàn)證輸入的冗長(zhǎng)過(guò)程都極大地影響了覆蓋率驅(qū)動(dòng)驗(yàn)證的效率.

2、文中分析了代碼行覆蓋次數(shù)與功能覆蓋率的內(nèi)在聯(lián)系, 建立了基于代碼行覆蓋次數(shù)的概率模型, 提出一種新的通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法) ) F OCDG AG . 通過(guò)代碼行覆蓋次數(shù)計(jì)算驗(yàn)證輸入序列的適應(yīng)度, 選取對(duì)提高功能覆蓋率貢獻(xiàn)較高的輸入序列, 使用遺傳算法自動(dòng)生成新的輸入序列組. 實(shí)驗(yàn)結(jié)果表明, 采用 F OCDGA G 時(shí)不需要功能覆蓋信息, 可以將全隨機(jī)輸入生成的功能覆蓋率收斂速度提高 10 倍以上, 將約束隨機(jī)輸入生成的功能覆蓋率收斂速度提高 20 倍以上.功能覆蓋率; 代碼覆蓋率; 遺傳算法; 自動(dòng)生成; 功能驗(yàn)證中圖法分類(lèi)號(hào) T P302An Automa

3、tic TestCode CoverageGeneration Method for Functional Coverage Improvement byysis1, 2Fu Liang1, 2Lu Ding1Zhang Zhimin1, 2Sun Yuan1) ( Resear ch Center of Microp rosor Technology , I nsti tu te of C omp uting T echnology , ChiA cad emy of S cie n, B eij ing00 90)2) ( Grad uate Univer sit y of ChiAcad

4、emy of S cien, Beij ing00049)AbstractCoverage driv en is an im po rtant technolo gy for functio nal verification. H o wever, theef f iciency of coverage driven v erif icatio n is grey affected bycov erag e definitions and leng thy manual test adjustm ent. T his p the line cov ered times and functio

5、nal coverage. Besides, it alsothe subjectiv it y of the functionalry zes the relationship betnestablishes a sist ical pr obabilitymbased on the line covered t imes. By using this m, a nov el method, i. e. , functio nal coverageoriented, co de coverage driven and genetic algor it hm based automatic t

6、est generatio n ( FOCDGA G) ispresented. T his m ethod selects g enetic algorithm toverification inputs auto matically. FOCDGA G enhanyze the line covered t imes and generate newfunctional cov erag e raly w ithout using theinform at ion of functional co verag e. Ex perimental results showt FOCDGA G

7、can speed up thestrained random test generation m oreverg ence of random test generation m oren 20 t imes.n 10 t im es andKey wordsfunctional coverage; co de coverage; genetic alg orithm ; automatic test generation;functional verification2- 26 基金項(xiàng)目 國(guó)家/ 八六三0 高技術(shù)研究發(fā)展計(jì)劃PCIM S收稿日期 2008- 05- 04; 修回日期 200

8、8-工業(yè)促進(jìn)局項(xiàng)目( 京財(cái)經(jīng)一指 2005 858 號(hào)), 主要研究方向?yàn)?SoC 設(shè)計(jì)驗(yàn)證基金( 2002AA Z 040) ;市傅 亮, 男, 977 年生, 博士, 主要研究方向?yàn)镾oC 設(shè)計(jì)驗(yàn)證 盧 鼎, 男, 983 年生, 男, 963 年生, 博士, 研究員, 博士生導(dǎo)師, 主要研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)、S oC 設(shè)計(jì)驗(yàn)證孫 愿 女, 984 年生, 主要研究方向?yàn)镾 oC 設(shè)計(jì)驗(yàn)證4 期傅 亮等: 通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法455隨著 ASIC 設(shè)計(jì)復(fù)雜度的迅速提高和集成電路制造工藝的快速發(fā)展, 功能驗(yàn)證開(kāi)銷(xiāo)已占到整個(gè)設(shè)計(jì)周期的 60% 80% 1 ,

9、 在導(dǎo)致首次流片失敗的原因中存在功能錯(cuò)誤的比例達(dá)到了 70% 2 , 功能驗(yàn)證已經(jīng)成為A SIC 設(shè)計(jì)流程的主要瓶頸. 如何提高驗(yàn)證效率, 更快地達(dá)到更高的驗(yàn)證質(zhì)量是ASIC 設(shè)計(jì)oriented, code coverage driven and genetic algorit hmbased automatic test g eneration, FOCDGAG) , 基于代碼覆蓋次數(shù)與功能覆蓋點(diǎn)之間的內(nèi)在聯(lián)系, 統(tǒng)計(jì)代碼行覆蓋次數(shù), 選擇對(duì)功能覆蓋率貢獻(xiàn)較大的驗(yàn)證輸入序列, 通過(guò)遺傳算法自動(dòng)生成新的驗(yàn)證輸入序列組, 經(jīng)過(guò)有限次迭代迅速收斂于較高的功能覆蓋率. 該方法不需要事先定義功能覆蓋

10、點(diǎn)、不需要功能覆蓋率統(tǒng)計(jì)信息, 不依賴于隨機(jī)約束的定義, 即的一項(xiàng)巨大.在功能驗(yàn)證中, 代碼覆蓋率目前只作為設(shè)計(jì)驗(yàn)證質(zhì)量的參考. 一般來(lái)說(shuō), 代碼覆蓋率并不能直接反映功能覆蓋率, 即便 100% 的代碼覆蓋率也不能保證功能正確, 整個(gè)驗(yàn)證過(guò)程中達(dá)到的功能覆蓋率才是衡量驗(yàn)證進(jìn)行程度和驗(yàn)證質(zhì)量的最重要標(biāo)準(zhǔn). 目前主流的覆蓋率驅(qū)動(dòng)驗(yàn)證方法是通過(guò)約束隨機(jī)生成使對(duì)隨機(jī)生成使用FO CD GA G 也可以迅速收斂于較高的功能覆蓋率.1遺傳算法簡(jiǎn)介驗(yàn)證輸入序列, 仿真后依據(jù)覆蓋率人工分析覆遺傳算法是由教授于 1975 年首先Michig an 大學(xué)的 H o lland蓋空洞產(chǎn)生原因, 然后手工調(diào)整約束、再

11、次仿真檢查結(jié)果, 經(jīng)多次迭代直到覆蓋空洞被覆蓋到. 然而這種方法有很大的缺陷: 1) 設(shè)計(jì)中由設(shè)計(jì)規(guī)約確定的和實(shí)現(xiàn)過(guò)程產(chǎn)生的潛在功能點(diǎn)的數(shù)量隨設(shè)計(jì)復(fù)雜度的提高而呈指數(shù)級(jí)增長(zhǎng), 在現(xiàn)有條件下要窮盡地定義出所有潛在功能點(diǎn)是不切實(shí)際的. 因此, 功能覆蓋點(diǎn) 9, 它依據(jù)遺傳變異理論在迭代過(guò)程中保持已有結(jié)構(gòu), 通過(guò)模擬文優(yōu)勝劣汰、適者生存進(jìn)化原理選擇好的結(jié)構(gòu), 同時(shí)尋找更好的結(jié)構(gòu). 遺傳算法中, 問(wèn)題的一個(gè)解定義為一個(gè)一組中的每一個(gè)分量定義為, 由,組成的集合稱為種群, 種群中每一個(gè)染的定義具有很強(qiáng)的性, 往往依賴于定義者的經(jīng)色體稱為種群的一個(gè). 遺傳算法從一組隨機(jī)產(chǎn)驗(yàn)豐富與否、對(duì)設(shè)計(jì)規(guī)約的理解程度、

12、對(duì)設(shè)計(jì)者實(shí)現(xiàn)方式的掌握程度、對(duì)各潛在功能點(diǎn)的重要性判斷和取舍, 以及定義者的耐心程度和上市時(shí)機(jī)的時(shí)間壓生的初始分開(kāi)始搜索, 選擇適應(yīng)度較高的一部, 通過(guò)以 P cr oss 為概率的交叉e 為概率的變異操作后, 得到后作為操作和以 P mu力等. 這些都使功能覆蓋定義的質(zhì)量并不代種群; 種群規(guī)模固定的種群稱為種群.總是能夠得到保證, 以這些功能覆蓋定義得到的功能覆蓋率為指導(dǎo)來(lái)提高驗(yàn)證質(zhì)量也有較強(qiáng)的經(jīng)過(guò)若干次迭代后, 算法收斂于適應(yīng)度最高的染色體.性. 2) 隨機(jī)約束的設(shè)定本身也有很強(qiáng)的性. 約束過(guò)松會(huì)產(chǎn)生大量重復(fù)或無(wú)效輸入, 使功能覆蓋率長(zhǎng)時(shí)間無(wú)法收斂; 約束過(guò)緊則產(chǎn)生的輸入過(guò)于專注部分功能點(diǎn)

13、, 導(dǎo)致功能覆蓋率到達(dá)一定程度后無(wú)法繼2隨時(shí)間衰減的代碼行覆蓋次數(shù)概率模型2. 1 代碼行覆蓋次數(shù)與功能覆蓋率的關(guān)系代碼行覆蓋次數(shù)與功能覆蓋率的一種常見(jiàn)聯(lián)系如Verilog H DL 代碼所示:續(xù)提高. 3) 驗(yàn)證輸入對(duì)功能點(diǎn)的可控性, 依據(jù)覆蓋率試探性調(diào)整約束后還要反復(fù)進(jìn)行仿真、修改, 才能使功能覆蓋率得到有效長(zhǎng)了驗(yàn)證周期., 大大延alw ay s (edg e clk )if(a b c) & d) sement1;else sement2;假設(shè)條件 a, b, c 為待驗(yàn)證設(shè)計(jì)( design under verification, DU V ) 內(nèi)的 3 個(gè)相關(guān)寄存器狀態(tài), 定義 a

14、& b& d 為功能覆蓋點(diǎn) 1, b& c& d 為功能覆蓋點(diǎn) 2, c& a& d 為功能覆蓋點(diǎn) 3. 進(jìn)行 10 個(gè)驗(yàn)證輸入序列的仿真: 每個(gè)輸入序列 100 個(gè)有效時(shí)鐘周期; 在 10針對(duì)這些問(wèn)題, 人們提出了很多覆蓋率驅(qū)動(dòng)的驗(yàn)證輸入生成方法, 如基于網(wǎng)絡(luò)反饋模型的輸入自動(dòng)生成方法 3- , 使用遺傳算法分析關(guān)鍵路徑覆蓋率、提高代碼覆蓋率的自動(dòng)生成方法 5 , 用遺傳算法分析功能覆蓋率、提高功能覆蓋率的自動(dòng)生成方法 6, 用遺傳算法生成微處理器匯編程序的方法 7, 從代碼中抽取功能覆蓋點(diǎn)的方法 8 .本文提出一種通過(guò)分析代碼覆蓋提高功能覆蓋個(gè)驗(yàn)證輸入序列中, 有 8 個(gè)序列的 semen

15、t 1 執(zhí)行率的驗(yàn)證輸入自動(dòng)生成方法( functional cov erag e次數(shù)為 1, 另外 2 個(gè)序列的 sement 1 執(zhí)行次數(shù)計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)2009 年456分別為 6 和 8. 使用代碼行覆蓋率分析時(shí), 雖然所有入序列組, 以前迭代過(guò)程中相隔代數(shù)越多的統(tǒng)計(jì)結(jié)果對(duì)本代的影響越小, 因此建立隨時(shí)間衰減的代碼行覆蓋次數(shù)概率模型. 隨時(shí)間衰減的代碼行覆蓋次數(shù)記入數(shù)組 S um M ,Sum m = ( 1 - Attenuat e rat e) Sum p ev ous m + N驗(yàn)證輸入序列的行覆蓋率相同, 但顯然 s執(zhí)行次數(shù)為 6 和 8 的 2 個(gè)序列可能覆蓋到em

16、ent1的功能點(diǎn). 選擇 sem ent 1 執(zhí)行次數(shù)為 6 和 8 的 2 個(gè)驗(yàn)證輸入序列為基礎(chǔ), 改變序列中部分驗(yàn)證輸入得到的新輸入序列和 3 個(gè)功能覆蓋點(diǎn)的相關(guān)性更強(qiáng). 與單純以行覆蓋率為依據(jù)選擇輸入序列的方法相比,Ecov n m ;n 1其中 M 是代碼行覆蓋點(diǎn)總數(shù). 當(dāng)一次迭代仿真周期選擇覆蓋了較難到達(dá)的代碼行次數(shù)的輸入序列數(shù)為 CYC N UM 時(shí), 對(duì)應(yīng)概率為 P s的方法, 可以生成覆蓋到序列.2. 2輸入序列的選擇功能覆蓋點(diǎn)的新輸入i sti c m =S um m PC YC N UM, 其中 m 是第 m 個(gè)代碼行覆蓋點(diǎn). 因?yàn)?C YC N UM 在統(tǒng)計(jì)過(guò)程中是定值,

17、 所以下面直接使用Sum m 代替 P sisti c m 參與計(jì)算, 不影如圖 1 所示, 因?yàn)楦采w到條件分支節(jié)點(diǎn)的輸入一定覆蓋到了其父節(jié)點(diǎn), 所以節(jié)點(diǎn)被覆蓋到的概率一定有 P7 P5 P 3 P 1 .響每個(gè)行覆蓋點(diǎn)概率的相對(duì)大小.的各代碼行覆蓋次數(shù)記入數(shù)組 cov N M , 其中 cov n m 中的是第 n 個(gè)驗(yàn)證輸入序列對(duì)于代碼行覆蓋點(diǎn)m的覆蓋次數(shù). 在每次迭代后新的代碼行覆蓋次數(shù)統(tǒng)計(jì)值加入概率模型前, 以前的代碼行覆蓋次數(shù)統(tǒng)計(jì)值先以 A t tenuate rate 的速率衰減.3FOCDGAG 方法圖 1 條件分支二叉樹(shù)3. 1 輸入序列的定義組合電路驗(yàn)證過(guò)程中 DU V 的輸

18、出與驗(yàn)證向量的輸入次序無(wú)關(guān), 而時(shí)序電路的每一個(gè)驗(yàn)證輸入都引理 1. 相同邏輯通被覆蓋到的概率越小.邏輯深度越深的節(jié)點(diǎn)定義 1. 事件 A 表示節(jié)點(diǎn)被覆蓋, 事件 Bi 表示可能引起電路狀態(tài)改變. DUV 對(duì)于驗(yàn)證輸入的響應(yīng)不僅取決于驗(yàn)證輸入本身, 還取決于此前驗(yàn)節(jié)點(diǎn)的邏輯深度為 i ; 則相同邏輯通節(jié)點(diǎn)邏輯證輸入序列導(dǎo)致的電路狀態(tài)變化. 對(duì)于帶有復(fù)深度為 i 的節(jié)點(diǎn)被覆蓋到的概率為 P ( A Bi ) , 在節(jié)點(diǎn)邏輯深度為 i 的前提下被覆蓋到的概率為 P (A Bi ) .位邏輯的時(shí)序電路, 每一次復(fù)位后電路將進(jìn)入相同的起始狀態(tài), 因此可選擇以復(fù)位為起始的一個(gè)驗(yàn)證輸入序列作為獨(dú)立, 使用

19、遺傳算法時(shí)利用輸入P ( A Bi )P ( Bi )1) 由條件概率公式 P( A和全Bi ) =序列的相關(guān)性提高算法效率.FOCDGAG 方法流程FOCDGAG 方法中, 使用種群規(guī)模固定為 N 的種群, 以復(fù)位為起始的驗(yàn)證輸入序列作為染色, 驗(yàn)證輸入序列中每個(gè)總線交易請(qǐng)求作為基3. 2E概率公式 P ( A ) =P ( Bj ) P ( A Bj ) 可知:i 1節(jié)點(diǎn)邏輯深度不確定時(shí), P( A ) 為定值.2) 根據(jù)引理 1 和公式, P (B iA ) =體P ( Bi ) P ( A Bi ) = P( AB i ) .因, 每個(gè)中數(shù)相同. 第 n 個(gè)的第P( A)P ( A )

20、m 個(gè)代碼行覆蓋點(diǎn)的適應(yīng)度函數(shù)F it l ine n m 取值為/ 隨時(shí)間衰減的代碼行覆蓋次數(shù)統(tǒng)計(jì)值0的倒數(shù)可以得到如下結(jié)論: 相同邏輯通, 被覆蓋概率小的節(jié)點(diǎn)對(duì)應(yīng)的邏輯深度更深的概率更大.根據(jù)此結(jié)論, 優(yōu)先選擇那些覆蓋到/ 被覆蓋概率乘以對(duì)該代碼行的覆蓋次數(shù), 若該行以前從未被覆蓋過(guò), 適應(yīng)度取固定值 3, 即小的節(jié)點(diǎn)0的輸入序列作為基礎(chǔ), 生成的新輸入0,Sum m = 0,Sum m = 0,cov n m = 0序列更容易覆蓋到邏輯深度較深的節(jié)點(diǎn).2. 3建立概率模型cov n m X 03,Fit line n m =.cov n mSum m, 其他情況遺傳算法通過(guò)選擇出的生成下

21、一代驗(yàn)證輸4 期傅 亮等: 通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法457第 n 個(gè)適應(yīng)度f(wàn) it ne ss n 為其對(duì)應(yīng)各代碼行的功能驗(yàn)證中采用了 FOCDGA G 的方法. 實(shí)驗(yàn)硬件平適應(yīng)度函數(shù)的代數(shù)和, 即M臺(tái)為Dell Linux EnterEdge 2950 服務(wù)器, 8 GB 內(nèi)存; SU SErise edition 9 操作系統(tǒng), 仿真是f i tness n =E Fitline n m .Synopsy s V CS- 0606- SP1- 18.4. 2 實(shí)驗(yàn)對(duì)象聚芯SoC 是一款面向m 1代碼行被覆蓋次數(shù)越少, Sum m 越小, 對(duì)應(yīng)代碼行覆蓋點(diǎn)的適應(yīng)度

22、越大. FOCDGAG 利用代碼行覆蓋次數(shù)與功能覆蓋率的內(nèi)在聯(lián)系, 優(yōu)先選擇那些的高端 32 位So C,它通過(guò) L Bus 總線將龍芯 CPU 核、PCI 控制器、DM A 控制器、L CD 控制器、內(nèi)存控制器、L ocal 總線、A Cp97, PS2, CAN bus, MAC, U SB 主機(jī)控制器覆蓋到/ 被覆蓋概率小0的代碼行的輸入序列作為, 通過(guò)遺傳算法自動(dòng)生成驗(yàn)證輸入, 快速提高功能覆蓋率. FO CD GAG 采用以適應(yīng)度較大為標(biāo)準(zhǔn)以及UART 等集成到一塊上, 片上一級(jí)總線的的最優(yōu)選擇, 每次迭成新種群時(shí)引入外來(lái)種群,讀P寫(xiě)數(shù)據(jù)線分開(kāi), 支持兩級(jí)地址流水方式的讀P寫(xiě)功能;

23、64 位數(shù)據(jù)總線寬度, 32 位地址空間; 支持 Sing le, Line 和不定長(zhǎng) burs t 交易模式 10 . SDRAM 內(nèi)存控制器為提高效率實(shí)現(xiàn)了復(fù)雜的預(yù)讀和讀P寫(xiě)以避免種群或算法長(zhǎng)時(shí)間陷入空間. 該方法的基本流程如圖 2 所示.地址邏輯, 在整個(gè)中的復(fù)雜度和重要性僅次于CPU 核.4. 3 功能驗(yàn)證SDRAM 內(nèi)存控制器的功能驗(yàn)證是使用VM M 11的驗(yàn)證方法和SystemV erilo g 語(yǔ)言搭建的總線交易請(qǐng)求約束隨機(jī)生成驗(yàn)證. 該驗(yàn)證每個(gè)時(shí)鐘周期按照約束生成一個(gè)總線交易請(qǐng)求, 生成的總線交易請(qǐng)求通過(guò)總線功能模型模擬總線行為, 轉(zhuǎn)換成 SDRAM 內(nèi)存控制器的總線接口輸入信

24、圖 2 F OCDG AG 方法的基本流程示意圖基于隨時(shí)間衰減的代碼行覆蓋次數(shù)概率模型的FOCDGAG 方法步驟如下:St ep1. 使用隨機(jī)方法生成初始種群, 依據(jù)代碼行覆蓋次數(shù)初始化各代碼行覆蓋概率.號(hào). 在 FOCDGAG 方法實(shí)現(xiàn)過(guò)程中,的變異操作及引入外來(lái)種群時(shí)所需驗(yàn)證輸入都由驗(yàn)證隨機(jī)生成. 實(shí)驗(yàn)中使用的功能覆蓋定義包括總線接口所有合法操作部FIFO 所有合法狀態(tài)存接口所有可能操作.狀態(tài)機(jī)所有狀態(tài)遷移、內(nèi)重要寄存器狀態(tài)和內(nèi)St ep2. 通過(guò)蓋次數(shù).DU V 功能正確性得到代碼行覆每個(gè)輸入序列的各代碼行覆蓋次數(shù)并記入St ep3.實(shí)驗(yàn)中直接在 RT L 代碼中代碼覆蓋點(diǎn)統(tǒng)數(shù)組 co

25、v n m .St ep4. 計(jì)算每個(gè)輸入序列的適應(yīng)度 f itness n . 計(jì)數(shù)組, 并使用 SystemVerilog 語(yǔ)言在驗(yàn)證內(nèi)St ep5. 選擇適應(yīng)度最高的若干作為交叉.以 P.部實(shí)現(xiàn)遺傳算法所有操作, 避免了在仿真中使用仿以 P cross 為概率進(jìn)行St ep6. St ep7.概率變異.真工具統(tǒng)計(jì)行覆蓋次數(shù)和通過(guò) DPI 接口仿真交叉后得到的的各mue 為器數(shù)據(jù)庫(kù). 所以, 加入 FOCDGAG 方法對(duì)整個(gè)仿真的效率影響很小. 實(shí)驗(yàn)結(jié)果表明, FOCDGAGSt ep8. 引入與初始種群相同方式生成的外來(lái)種群.方法運(yùn)行時(shí)對(duì)驗(yàn)證仿真速度降低10% , 因St ep9. 合并

26、外來(lái)種群和遺傳操作得到的新一代種群 Pop new ., 生成此可以直接使用仿真周期數(shù)來(lái)衡量各種驗(yàn)證輸入生St ep10. 根據(jù)隨時(shí)間衰減的代碼行覆蓋次數(shù)概率模型更新各代碼行覆蓋概率.St ep11. 重復(fù) Step2 Step10, 直到滿足仿真結(jié)束條件.成方法對(duì)功能覆蓋率的效率.4. 4 FOCDGAG 方法參數(shù)選擇FOCDGAG 方法中, 種群規(guī)模、外來(lái)種群規(guī)模、交叉概率 P cr oss、變異概率 P mue 和統(tǒng)計(jì)次數(shù)4實(shí)驗(yàn)結(jié)果與分析衰減率A t tenuate rate 等對(duì)算法的效率有綜合性影響. 各種參數(shù)組合的大量對(duì)比實(shí)驗(yàn)結(jié)果表明: 聚芯 SoC 的 SDRAM 控制器使用 F

27、OCDGAG 方法4. 1實(shí)驗(yàn)環(huán)境計(jì)算技術(shù)聚芯 SoC計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)2009 年458進(jìn)行功能驗(yàn)證時(shí), 種群規(guī)模在 36 120 之間都可以在較短的仿真周期內(nèi)得到較高的功能覆蓋率. 外來(lái)隨機(jī)種群的規(guī)模為遺傳算法種群規(guī)模的 1P3, 并固根據(jù)以上實(shí)驗(yàn)結(jié)果, 在隨后的實(shí)驗(yàn)中固定種群規(guī)模N = 72, 外來(lái)種群規(guī)模 24, 選取概率 P cr oss= 18% , 變異概率 P mu計(jì)次數(shù)衰減率 Attenuate r ate= 2% .4. 5 輸入序列長(zhǎng)度選擇數(shù) 24, 交叉e = 5%, 統(tǒng)定選擇種群規(guī)模 1P3 的適應(yīng)度最大的作為種子, 以保證算法有較高的穩(wěn)定性. A t ten

28、uate rate 取值 2% 3% 時(shí), 穩(wěn)定性和有效性較好. 交叉概率 P以復(fù)位為起始的驗(yàn)證輸入序列作為獨(dú)立時(shí), FOCDGAG 方法效率并不隨序列長(zhǎng)度增加而單調(diào)增加. 這是因?yàn)樾蛄兄泻罄m(xù)輸入的結(jié)果依賴于之cross 和變異概率 P較小時(shí), 需要 P mumue 相互影響, 當(dāng) P cr osse 較大才可以得到較高的算法效率. P cr oss 在 10% 25% 區(qū)間內(nèi)每降低 2% , P mue 大約需要增加 1% 才能得到相似的算法效率. P cross 在 5% 10% 區(qū)間時(shí), 算法效率隨 P mue 增加呈雙峰型分布, 即 P mue 增加到 8%左右時(shí)算法效率達(dá)到最高值,

29、其后逐漸下降, 但在增加到 16% 左右時(shí)又上升到一個(gè)低于最高值的局部極值. 無(wú)論 P cr oss 取值為多少, P mue 增加到前的輸入序列導(dǎo)致的DUV狀態(tài), 若序列長(zhǎng)度過(guò)長(zhǎng), 會(huì)造成輸入序列中各個(gè)輸入間的依賴性呈指數(shù)級(jí)增長(zhǎng), 經(jīng)過(guò)交叉、變異后得到的新輸入序列與原輸入序列相關(guān)性降低, 使得遺傳算法的優(yōu)化效率無(wú)法穩(wěn)定提高. 當(dāng)輸入序列長(zhǎng)度在 10 360 之間變化時(shí), 1 600次迭代內(nèi)達(dá)到的功能覆蓋率如圖 3 所示.序列長(zhǎng)度小于 40 時(shí), FOCDGAG 方法效率隨序列長(zhǎng)度增加而增加; 序列長(zhǎng)度為 40 時(shí), 算法效率最高;序列長(zhǎng)度大于 40 時(shí), 算法效率逐漸降低; 序列長(zhǎng)度30%

30、后算法效率開(kāi)始迅速降低, 直至為普通隨機(jī)生成算法. 當(dāng) P cr oss 在15% 20% 區(qū)間內(nèi)、Pmue 取值在 3% 最穩(wěn)定.6% 區(qū)間內(nèi)時(shí), 算法效率最高也超過(guò) 180 后, 本文方法逐漸為序列長(zhǎng)度與效率正相關(guān)的普通隨機(jī)輸入生成算法.圖 3 輸入序列長(zhǎng)度對(duì)算法性能的影響4. 6實(shí)驗(yàn)結(jié)果圖 4 所示為在 SDRAM 控制器常用配置模式下, 6 種驗(yàn)證輸入生成方法隨仿真周期的增加達(dá)到的功能覆蓋率比較. 其中, 全隨機(jī)生成為約束隨機(jī)生成除去所有為了提高覆蓋率而添加的約束, 基隨機(jī)生成的 FOCDGAG 為在全隨機(jī)生成基礎(chǔ)上加入FOCDGAG 方法, 基于約束隨機(jī)生成的FOCDGAG為在約束隨

31、機(jī)生成基礎(chǔ)上加入 FOCDGAG 方法, 基隨機(jī)的傳統(tǒng)遺傳算法為在全隨機(jī)生成基礎(chǔ)上加入以代碼覆蓋率為適應(yīng)度函數(shù)的遺傳算法, 基于約束隨機(jī)的傳統(tǒng)遺傳算法為在約束隨機(jī)生成基礎(chǔ)上加入以代碼覆蓋率為適應(yīng)度函數(shù)的遺傳算法.如圖 4 所示, 基隨機(jī)的FOCDGAG 在一定仿真周期后, 功能覆蓋率提高的速度是全隨機(jī)生成的 2 14 倍, 達(dá)到 85% 功能覆蓋率的速度比全隨機(jī)生成的方法快 5 倍以上; 基于約束隨機(jī)的FOCDGAG在一定仿真周期后, 功能覆蓋率提高的速度是約束隨機(jī)生成的 4 15 倍, 達(dá)到 85% 功能覆蓋率的速度快 10 倍以上. 2 種傳統(tǒng)遺傳算法提高功能覆蓋率的效率和在可接受仿真周期

32、內(nèi)最終達(dá)到的功能覆蓋率4 期傅 亮等: 通過(guò)分析代碼覆蓋提高功能覆蓋率的驗(yàn)證輸入自動(dòng)生成方法459明顯低于 2 種FOCDGAG 方法. 基隨機(jī)的速度慢, 隨著仿真周期的增加, 兩者差距逐步縮小, 在可接受仿真周期內(nèi)達(dá)到的最高覆蓋率明顯高于后者.FOCDGAG 對(duì)功能覆蓋率的速度僅在開(kāi)始階段比基于約束隨機(jī)的 FOCDGAG 對(duì)功能覆蓋率的圖 4 6 種驗(yàn)證輸入生成方法比較表 1 所示為在 SDRAM 控制器常用配置模式下,4 種驗(yàn)證輸入生成方法在 15 106 仿真周期內(nèi)達(dá)到的最高功能覆蓋率、初次達(dá)到最高功能覆蓋率所需的仿真周期數(shù)和 15 106 仿真周期最終消耗的服務(wù)器 CP U 總機(jī)器時(shí)間

33、. 表 1 中, 基于約束隨機(jī)的 FOCDGAG 的功能覆蓋率收斂所需仿真周期數(shù)最少, 約束隨機(jī)生成和全隨機(jī)生成在 15 106 仿真周期內(nèi)始終無(wú)法達(dá)到 87% 的功能覆蓋率. 由于實(shí)驗(yàn)中全隨機(jī)和約束隨機(jī)生成的功能覆蓋率在可接受仿真周期內(nèi)無(wú)法收斂, 結(jié)合圖 4 和表 1, 保守判斷基隨機(jī)的 FO CD GAG 功能覆蓋率收斂速度是全隨機(jī)生成的 10 倍以上, 基于約束隨機(jī)的FO CD GAG 功能覆蓋率收斂速度是約束隨機(jī)生成的 20 倍以上.表 1 4 種驗(yàn)證輸入生成方法比較達(dá)到的最高功能覆蓋率P%初次達(dá)到最高覆蓋率的仿真周期數(shù)Pk仿真消耗總機(jī)器時(shí)間Ph生成方法全隨機(jī)生成85 256 3867

34、 45約束隨機(jī)生成86 934 5735 2基隨機(jī)的FOCDGAG956 4387 55基于約束隨機(jī)的 FOCDGAG90 306235 944. 7進(jìn)一步分析從表 1 可以看到, 隨機(jī)輸入生成過(guò)程是否使用約束對(duì)仿真速度的影響非常大, 這是因?yàn)榉抡婀ぞ邔?duì)于隨機(jī)約束的求解過(guò)程需要消耗大量的時(shí)間. 本文實(shí)驗(yàn)中, 約束隨機(jī)生成為了快速達(dá)到較高覆蓋率,對(duì)各種輸入類(lèi)型賦予相應(yīng)權(quán)重, 并通過(guò)約束盡快生成能夠覆蓋各種邊角情況的輸入序列, 而全隨機(jī)輸入中沒(méi)有這些約束. 實(shí)驗(yàn)結(jié)果表明, 2 種情況下仿真消耗機(jī)器時(shí)間相差近 5 倍.圖 5 所示為在 SDRAM 控制器常用配置模式的功能覆蓋率. 從圖 5 中容易看

35、出, 以仿真所需的機(jī)器時(shí)間為標(biāo)準(zhǔn)時(shí), 基隨機(jī)的 FO CD GAG 對(duì)功能覆蓋率的速度和達(dá)到收斂時(shí)的功能覆蓋率,下, 基隨機(jī)的 FOCDGAG 和基于約束隨機(jī)的FOCDGAG 隨仿真消耗的 CPU 機(jī)器時(shí)間增加達(dá)到圖 5 F OCDG AG 基于 2 種隨機(jī)生成方法的比較計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)2009 年460都比基于約束隨機(jī)的 FOCDGAG 高. 因此, 在驗(yàn)證過(guò)程中不必開(kāi)發(fā)太多隨機(jī)約束, 可以使用 FOCDGAG方法自動(dòng)生成驗(yàn)證輸入, 以快速達(dá)到較高的功能覆蓋率, 盡早發(fā)現(xiàn)設(shè)計(jì)中的錯(cuò)誤, 縮短驗(yàn)證周期.o s ula on vecen era on us ng Bayes an ne

36、 w ork JJourn al o Co pu er A d ed Des gn & Co pu er Graph cs,2007,(9( 5), 佟6 6 62 ( n Ch)冬, 程 旭 使用網(wǎng)絡(luò)的高效模擬矢量生成方法 J計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007, 9( 5)6 6 62 ) 5結(jié)論 5Y J ang ang, based on crDes gn & CoT ong Don g, Chen g Xu Pa h coverage e r ccal s gnals JJ ou rnal o Co pu er A dedpu er Graph cs, 2006, 8( 8 )08

37、5 09 ( n本文分析了代碼行覆蓋次數(shù)與功能覆蓋率的內(nèi)在聯(lián)系, 把以往相互獨(dú)立的代碼覆蓋率和功能覆蓋率有機(jī)結(jié)合起來(lái), 提出了通過(guò)統(tǒng)計(jì)代碼行覆蓋次數(shù),使用遺傳算法自動(dòng)生成驗(yàn)證輸入序列, 快速提高功能覆蓋率的FO CD GAG 方法. 研究表明, 依據(jù)隨時(shí)Ch ( J), 佟冬, 程 旭 基于關(guān)鍵信號(hào)的路徑覆蓋率模型計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 8 ( 8 )08509 )Luo C,gen era on or un 6Jun, L ng M ng Coverage d rec ed vec oral ver ca on u s ng gene c alg or h間的代碼行覆蓋次數(shù)

38、概率模型得到的概率, 選 JCh ( 羅Journal o)春,Appl ed S c en, 2005, 23( 4) 375 379 ( n擇以復(fù)位為起始的驗(yàn)證輸入序列作為,FOCDGAG 方法不依賴于功能覆蓋定義與否和定義質(zhì)量高低就可以快速提高功能覆蓋率. 進(jìn)一步的, 凌 明 基于遺傳算法和覆蓋率驅(qū)動(dòng)的功能驗(yàn)證向量自動(dòng)生成算法 J 應(yīng)用科學(xué)學(xué)報(bào), 2005, 23( 4)375 379)實(shí)驗(yàn)表明, 基隨機(jī)的 FO CD GAG 不需要定義隨 7Corno F,prograCu an G,gen era onReorda M S , et alor p pel ned proAu os or sa C PPpu ng,機(jī)約束, 可在相同機(jī)器時(shí)間內(nèi)提高功能覆蓋率的效率, 最終達(dá)到的功能覆蓋率均可高于基于約束隨機(jī)的FOCDGAG.Proceed n