王樹朋,黃　凱,嚴(yán)曉浪

(1.浙江大學(xué) 信息與電子工程學(xué)系,浙江 杭州 310027； 2. 浙江大學(xué) 超大規(guī)模集成電路研究所,浙江 杭州 310027)

?

基于遺傳算法的覆蓋率驅(qū)動測試產(chǎn)生器

王樹朋1,黃凱1,嚴(yán)曉浪2

(1.浙江大學(xué) 信息與電子工程學(xué)系,浙江 杭州 310027； 2. 浙江大學(xué) 超大規(guī)模集成電路研究所,浙江 杭州 310027)

摘要:為了更好地建立覆蓋率和測試產(chǎn)生器之間的聯(lián)系,產(chǎn)生高質(zhì)量的測試,提出基于遺傳算法的覆蓋率驅(qū)動測試產(chǎn)生器.該測試產(chǎn)生器利用一種簡單、準(zhǔn)確的測試編碼方法對測試進(jìn)行編碼,并利用基于功能覆蓋率的適應(yīng)度函數(shù)評估測試的優(yōu)劣.通過遺傳算法(GA)建立覆蓋率與測試產(chǎn)生器之間的聯(lián)系,分析覆蓋率和測試之間的關(guān)系,根據(jù)分析結(jié)果改變測試產(chǎn)生器的約束和限制,驅(qū)動測試產(chǎn)生器生成新一代的測試,新一代的測試可以覆蓋到上一代的測試無法覆蓋的功能點.實驗結(jié)果表明：在2個高性能的32位多核處理器的驗證環(huán)境中,該測試產(chǎn)生器可以明顯減少仿真時間,提高驗證效率．

關(guān)鍵詞：覆蓋率；測試產(chǎn)生器；遺傳算法(GA)；覆蓋率驅(qū)動測試產(chǎn)生器；適應(yīng)度函數(shù)

隨著嵌入式系統(tǒng)的規(guī)模越來越龐大,功能驗證已經(jīng)成為嵌入式系統(tǒng)設(shè)計周期中最主要的挑戰(zhàn),功能驗證的方法直接決定了嵌入式系統(tǒng)的面市時間.目前主要使用基于仿真的驗證方法驗證嵌入式系統(tǒng)的功能,這種方法是通過仿真大量的測試得到期望的覆蓋率,其效果和所使用的測試的質(zhì)量息息相關(guān).測試的質(zhì)量往往用覆蓋率表征,覆蓋率可以識別和發(fā)現(xiàn)沒有驗證的功能,從而評估驗證工作的進(jìn)展.覆蓋率主要分為代碼覆蓋率和功能覆蓋率,其中代碼覆蓋率通過評估硬件代碼執(zhí)行的情況得到覆蓋率,主要包括語句覆蓋率、判定覆蓋率和條件覆蓋率等；而功能覆蓋率是通過評估功能點的覆蓋情況得到覆蓋率,功能點是用戶自己提取的必須要驗證的特征和一系列事件的組合[1].

高質(zhì)量的測試往往可以在短時間內(nèi)得到較高的覆蓋率,而基于仿真的驗證方法的最大挑戰(zhàn)就在于產(chǎn)生這些可以提高驗證效率的高質(zhì)量測試.測試主要分為人工書寫的測試、隨機(jī)測試和覆蓋率驅(qū)動測試產(chǎn)生器生成的測試.在實際應(yīng)用中,人工書寫的測試和隨機(jī)測試的局限性推動了覆蓋率驅(qū)動測試產(chǎn)生器(coverage direct test generation,CDTG)的發(fā)展和應(yīng)用.CDTG可以在分析覆蓋率后,根據(jù)算法自動修改測試生成器的限制和約束,從而減少人工參與.CDTG可以分為2種,分別是基于形式方法的和基于反饋的GDTG.不管采用哪種方法,CDTG的最終目的都是產(chǎn)生高質(zhì)量的測試,從而提高驗證效率,減少驗證周期.基于形式方法的CDTG需要DUT的一個形式模型(例如:有限狀態(tài)機(jī)),在驗證過程中通過分析這個形式模型的狀態(tài),修改測試生成器的限制和約束.這個方法的最大限制是隨著嵌入式系統(tǒng)越來越復(fù)雜,形式模型也會隨著越來越龐大.基于反饋的CDTG已經(jīng)成為了最常用的測試產(chǎn)生器,其中,進(jìn)行反饋的算法主要分為機(jī)器學(xué)習(xí)以及進(jìn)化算法,用于反饋的機(jī)器學(xué)習(xí)算法主要包括貝葉斯網(wǎng)絡(luò)[2-5],馬爾可夫模型[6-7]以及歸納邏輯程序設(shè)計[8],用機(jī)器學(xué)習(xí)算法進(jìn)行反饋可以得到較好的結(jié)果,但是利用進(jìn)化算法進(jìn)行反饋的CDTG可以在較短的時間內(nèi)得到更好的驗證效果,并且需要的領(lǐng)域知識更少,擁有更好的通用性[9],因此基于進(jìn)化算法尤其是遺傳算法(genetic algorithm,GA)的CDTG吸引了越來越多的研究人員．

GA是一種借鑒生物界的適者生存、優(yōu)勝劣汰遺傳機(jī)制演化而來的隨機(jī)化搜索方法,主要特點是直接對結(jié)構(gòu)對象進(jìn)行操作,不存在求導(dǎo)和函數(shù)連續(xù)性的限定[10].GA采用概率化的尋優(yōu)方法,不需要確定的規(guī)則,而是能夠自動獲取和指導(dǎo)優(yōu)化的搜索空間,自適應(yīng)地調(diào)整搜索方向.GA的這些良好的特性使其成為智能計算中的關(guān)鍵技術(shù),已被人們廣泛應(yīng)用于自適應(yīng)控制[11-14]、組合優(yōu)化[15-17]、機(jī)器學(xué)習(xí)、信號處理和人工生命等多個領(lǐng)域．

Smith等[18]最早將GA應(yīng)用于CDTG,實驗結(jié)果表明采用GA可以減少驗證時間.Bose等[19]提出了一種緩沖器的平均利用情況作為功能覆蓋率,然后將這個功能覆蓋率作為適應(yīng)度函數(shù)用于評估測試的價值和效率. Yu等[20]利用語句覆蓋率和路徑覆蓋率分析測試的效率,此外還提出了一種名為錯誤覆蓋率的覆蓋率用于測試缺陷,但是這個方法的缺點在于必須用工具AMLETO將系統(tǒng)設(shè)計從超高速硬件描述語言轉(zhuǎn)換成SystemC.Samarah等[21]提出一種基于細(xì)胞的遺傳算法用于自動產(chǎn)生測試,實驗結(jié)果顯示Samarah等提出的方法比普通的隨機(jī)測試產(chǎn)生器效率高很多,但是這個方法只能用于驗證比較小的系統(tǒng).Habibi等[22]通過將測試產(chǎn)生器抽象到高抽象層,然后利用GA在這個高抽象層產(chǎn)生測試,這樣可以提高仿真速度,但是會犧牲準(zhǔn)確度.Shen等[23]用自定義的字符串基因組作為測試產(chǎn)生器的限制和約束,然后在Godson 1處理器上進(jìn)行大量的實驗,實驗結(jié)果顯示這個方法可以得到更高的功能覆蓋率,但是沒有達(dá)到100%.Subedha等[24]提出一種基于GA的CDTG,利用代碼覆蓋率來評估測試的適應(yīng)度,然后在JAVE工作平臺上進(jìn)行大量的實驗,實驗結(jié)果顯示該方法可以得到更高的覆蓋率,缺點在于所用到的適應(yīng)度函數(shù)是基于覆蓋的代碼行數(shù),無法準(zhǔn)確地評估測試的質(zhì)量.Wang等[25]用功能點的覆蓋情況評估測試的質(zhì)量,在基于C語言的平臺和真實的應(yīng)用(PCIE系統(tǒng))進(jìn)行大量的實驗,實驗結(jié)果表明該方法可以顯著減少驗證時間,但是文中并沒有明確地介紹測試編碼方法.對于基于GA的CDTG來說,測試的編碼方法會直接影響整個遺傳過程和驗證過程,因此測試的編碼方法是至關(guān)重要的.因為多核處理器具有高性能、低功耗的特點,所以多核處理器已經(jīng)發(fā)展成為了嵌入式系統(tǒng)的主流,這就要求測試編碼方法不僅可以用于單核處理器驗證環(huán)境中的測試的編碼工作,而且可以用于編碼多核處理器驗證環(huán)境中的測試.

本文提出一個基于功能覆蓋率的適應(yīng)度函數(shù)用于評估測試的價值和效率,通過遺傳算法建立覆蓋率分析結(jié)果和測試產(chǎn)生器之間的聯(lián)系,自動改變測試產(chǎn)生器的限制和約束,從而產(chǎn)生新的測試用于驗證,以提高驗證效率,減少驗證時間．

1遺傳算法

遺傳算法(GA)是由美國的Holland教授于1975年首先提出的,GA是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型,是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法.GA從代表問題可能潛在的解集的一個種群開始,種群由一定數(shù)量的個體組成,基因在自然進(jìn)化中至關(guān)重要,種群中的個體可以用多個基因組合而成的染色體表示.在GA中,通過編碼組成初始種群以后,基于種群中的染色體對于環(huán)境的適應(yīng)度,通過遺傳算子對染色體進(jìn)行優(yōu)勝劣汰.遺傳算子包括選擇、交叉和變異,選擇是基于種群中染色體的適應(yīng)度進(jìn)行評估,然后將適應(yīng)度高的優(yōu)秀染色體直接保留到下一代. GA中最為重要的遺傳操作是交叉算子,交叉是指把2個父代染色體的部分結(jié)構(gòu)加以替換重組而生成新染色體的操作,可以使GA的搜索能力得到極大提高.變異算子通過選擇群體中的染色體的某些基因位,使得這些基因位上的基因值進(jìn)行突變.GA引入變異的目的有2個：一是使GA具有局部的隨機(jī)搜索能力,當(dāng)GA通過交叉算子已接近最優(yōu)解鄰域時,利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂；二是使GA可維持群體多樣性,以防止出現(xiàn)未成熟收斂現(xiàn)象.設(shè)種群的規(guī)模為popsize,迭代次數(shù)為gen,最大迭次代數(shù)為maxgen,GA的基本流程如下：

Begin

設(shè)置算法參數(shù)；

隨機(jī)產(chǎn)生初始種群；

for (gen = 0; gen < maxgen; gen ++)

{

for (i = 0; i < popsize; i ++)

{

計算種群中第i個個體的適應(yīng)度；

計算種群中第i個個體的目標(biāo)值；

}

根據(jù)適應(yīng)度,將選擇算子作用于群體；

根據(jù)交叉概率進(jìn)行交叉操作；

根據(jù)變異概率進(jìn)行變異操作；

}

End

要將GA用于CDTG中,需要將驗證環(huán)境中的測試當(dāng)作種群中的個體,然后找到合適的測試編碼方法,用由特征矢量按照一定結(jié)構(gòu)組成的染色體表示測試,要求染色體編碼可以準(zhǔn)確地表示測試的特征,才能在GA的作用下產(chǎn)生質(zhì)量越來越高的測試.

2測試編碼方法

本文提出的測試編碼方法通過提取測試的特征,可以將測試轉(zhuǎn)換為特征矢量,從而得到可以表征測試特征的染色體編碼.該測試編碼方法不僅可以用于單核處理器的驗證環(huán)境的測試的編碼工作,而且可以對多核處理器的驗證環(huán)境中的測試進(jìn)行編碼.對于測試來說,其特征主要來自于3個方面：一是控制寄存器的配置情況,控制寄存器的配置情況會顯著地影響系統(tǒng)狀態(tài)；二是測試所包含的每一條指令的信息和特征,例如：操作碼和相關(guān)的地址.因為不管一個測試多么復(fù)雜,也是由一條條簡單的指令組成的,所以單條指令的特征會顯著影響測試的特征,分析單條指令的特征是必要的；三是多條指令形成的指令流,這些指令流可能會得到很多不同的仿真情景和覆蓋情況．

將一個測試轉(zhuǎn)換為一個特征矢量的過程可以分為2個步驟：第一個步驟是將測試中包含的每條指令轉(zhuǎn)換為一個小矢量,第二個步驟是將這些小的矢量結(jié)合形成表示測試的完整特征矢量.在第一步中,每條指令可以轉(zhuǎn)換為一個5元素的特征向量,控制寄存器的配置情況用第一個元素表示；指令集中的所有操作碼會被編碼,然后用第二個元素表示；第三個元素用于表示這條指令的相關(guān)地址所在的地址域；第四個元素用于表示這條指令是否和在它之前的指令有依賴關(guān)系；這條指令和離其最近的有依賴關(guān)系的指令之間的距離用第五個元素表示.這樣就可以將每條指令轉(zhuǎn)換為一個5元素的特征向量,將這些特征矢量結(jié)合就可以形成表示測試特征的完整特征矢量,從而形成測試的染色體編碼.如果一個驗證環(huán)境中的多個測試的長度不一致,即這些測試包含的指令數(shù)目不一致的話,需要將一些零向量添加到比較短的特征矢量后面,使得整個驗證環(huán)境中的所有特征矢量長度相同．

圖1中介紹了一個簡單的測試編碼過程,假設(shè)共有2個測試,分別是測試 1和測試2,其中測試1包含10個指令,而測試2包含8個指令.因為測試1的第3個指令是配置系統(tǒng)控制寄存器,將系統(tǒng)的狀態(tài)從SLEEP(低功耗狀態(tài))修改為ACTIVE(正常工作狀態(tài)),所以第三個特征矢量的第一個元素置為1；第四個特征矢量的第二個元素置為2,因為測試1的第四個指令的操作碼是ldw.這個特征矢量的第三個元素置為2,因為第四個指令相關(guān)地址的地址域是可緩存的但是不可共享的.因為第四條指令與第一條指令具有依賴關(guān)系,所以第四個特征矢量的第四個元素置為1,表示第四條指令與其之前的指令有依賴關(guān)系.與此同時,將第五個元素置為3,表示其與第1條指令有依賴關(guān)系.因為測試2只包含8條指令,所以需要在特征矢量后面添加2個零向量以得到1個50元素的特征向量,這樣可以和測試1的特征矢量長度相同.通過使用這個編碼方法,得到2個測試的染色體編碼,而且得到的染色體編碼可以準(zhǔn)確地表示測試的特征．

圖1　測試編碼示例Fig.1　Simple example of test encoding

3基于遺傳算法的覆蓋率驅(qū)動測試產(chǎn)生器

圖2介紹了將GA用于CDTG的過程,整個過程從測試產(chǎn)生器隨機(jī)生成的M個測試組成的初始測試集合開始,當(dāng)這M個測試經(jīng)過仿真以后,通過分析覆蓋率,得到每個測試的適應(yīng)度,測試的適應(yīng)度和覆蓋率息息相關(guān).如果此時滿足終止條件,那么整個仿真過程終止；如果不滿足終止條件,那么根據(jù)選擇算法進(jìn)行選擇,隨后根據(jù)交叉率和交叉算法進(jìn)行交叉操作,最后根據(jù)變異率和變異算法進(jìn)行變異操作,可以得到新的測試集合中每一個測試的染色體編碼,反饋給測試產(chǎn)生器.測試產(chǎn)生器可以根據(jù)這些染色體編碼產(chǎn)生新的測試,新產(chǎn)生的測試往往比原來的測試擁有更高的適應(yīng)度,可以覆蓋到原來的測試無法覆蓋的功能點.重復(fù)以上過程直到滿足終止條件,終止條件一般是功能覆蓋率達(dá)到要求．

圖2　基于遺傳算法的覆蓋率驅(qū)動測試產(chǎn)生器Fig.2　Coverage directed test generation based on genetic algorithm

通常來說,遺傳算法可以表示為GA=(C,E,P0,M,F,G,Y,T), 其中C和E分別表示染色體編碼方法和適應(yīng)度函數(shù)；P0和M分別表示初始種群和種群大小,在本研究的應(yīng)用中,P0和M分別表示初始的測試集合和測試集合中測試的個數(shù)；F、G和Y分別表示選擇算子、交叉算子和變異算子；T表示終止的條件和規(guī)則.為了在分析覆蓋率以后,用遺傳算法驅(qū)動測試產(chǎn)生器生成質(zhì)量更高的測試,需要確定這8個變量.第2章介紹了測試的染色體編碼方法C,本章主要介紹其他7個變量．

GA中的適應(yīng)度函數(shù)E用來判斷種群中的染色體的優(yōu)劣,適應(yīng)度函數(shù)直接影響到GA的性能.基于仿真的驗證方法的目標(biāo)是在短時間內(nèi)得到最大的覆蓋率,而多次覆蓋功能點可以提高驗證的完整性和魯棒性,因此在本研究的應(yīng)用中,適應(yīng)度函數(shù)E和功能點的覆蓋情況密切相關(guān).首先確定被測試的設(shè)計中需要覆蓋的功能點,這些功能點是要驗證的處理器特征和一系列的事件組成,假設(shè)共有g(shù)個功能點.當(dāng)完成一個測試的仿真以后,這個測試的適應(yīng)度可以表示為

式中：wi表示第i個功能點的權(quán)重和重要程度,其值可以根據(jù)被測試的設(shè)計的特征進(jìn)行調(diào)整,例如：當(dāng)只測試某一個模塊時,可以將其他模塊的功能點的權(quán)重設(shè)置為0；ti表示第i個功能點被覆蓋的次數(shù)．

需要確定測試集合的大小,即測試集合包含的測試的數(shù)目M.當(dāng)M的取值較小時,算法的計算時間較短,但是算法收斂到最優(yōu)解的可能性較低,即全局搜索能力較小,可能會得到局部最優(yōu)解,而非全局最優(yōu)解.隨著M值的增大,算法收斂到最優(yōu)解的可能性會隨之增加,但是算法的計算時間也會隨之顯著增加.在現(xiàn)實應(yīng)用中,研究人員往往需要根據(jù)應(yīng)用特點和個人經(jīng)驗設(shè)定M的取值.在本研究的應(yīng)用中,M的取值不宜很大,舉一個比較極端的例子來說明這一點.假設(shè)一個驗證環(huán)境中共有5 000個測試,如果將M的值取為5 000,那么這5 000個測試會組成初始測試集合,需要將這5 000個測試都進(jìn)行仿真,就失去了使用GA的意義.據(jù)筆者所知,目前還沒有一種大家認(rèn)可的方法可以通過理論計算確定M的取值,由于在大多數(shù)的文獻(xiàn)和研究中,M的取值范圍為20～100,在本研究的應(yīng)用中,也將M的取值范圍設(shè)定為20～100．

選擇算子F是從測試集合中淘汰掉劣質(zhì)的測試,將優(yōu)良的特征遺傳到新一代的測試集合.選擇最簡單也是最常見的選擇方法——輪盤賭選擇法作為選擇算法,在該方法中,各個測試的選擇概率和其適應(yīng)度值成比例.假設(shè)測試集合中的測試個數(shù)為M,測試i的適應(yīng)度是fi,那么i被選擇的概率為

顯然,選擇概率反映了測試i的適應(yīng)度在整個測試集的測試適應(yīng)度總和中所占的比例,測試的適應(yīng)度越大,其被選擇的概率越高,反之亦然.計算出每個測試的選擇概率以后,可以根據(jù)選擇概率賦予每個測試一個取值范圍.每一輪都會產(chǎn)生一個隨機(jī)數(shù)R,R∈[0, 1).將R作為選擇指針來確定被選擇的測試,在進(jìn)行M輪選擇以后就可以選擇出M個測試,形成新的測試集合.圖3顯示了一個輪盤賭選擇法的示例,假設(shè)4個測試被選擇的概率分別是36%、28%、21%和15%,根據(jù)測試的選擇概率可以賦予相應(yīng)的取值范圍,選擇范圍和選擇概率相對應(yīng),每輪產(chǎn)生一個隨機(jī)數(shù)R,R在哪個測試的取值范圍之中,那么此輪就選中這個測試.例如,在某一輪中R的值為0.4,那么測試 2即被選中．

圖3　 輪盤賭選擇法Fig.3　Roulette wheel selection method

圖4　單點交叉的簡單示例Fig.4　Simple example of one-point crossover

變異算子Y是根據(jù)變異率對測試染色體中的某些特征位的值進(jìn)行改動,一般來說,變異操作的基本步驟如下：

1) 對測試集合中所有測試以事先設(shè)定的變異率判斷是否進(jìn)行變異；

2) 對進(jìn)行變異的測試的染色體編碼隨機(jī)選擇變異位進(jìn)行變異．

圖5　變異的簡單示例Fig.5　Simple example of mutation

4實驗結(jié)果及分析

4.1實驗設(shè)置

為了評估本文提出的方法的可實行性,選用杭州中天微系統(tǒng)公司的CK810MP多核處理器進(jìn)行大量的實驗.如圖6所示,CK810MP多核處理器由修改后的CK810 處理器、核間互連以及主存儲單元組成,并支持2～8個處理器的配置，其中CK810是高性能的32位嵌入式處理器.根據(jù)設(shè)計規(guī)則,修改CK810的讀寫單元的部分邏輯,使其支持緩存一致性協(xié)議；將修改后的多個CK810通過核間互連進(jìn)行通信,核間互連不僅需要維護(hù)整個多核處理器系統(tǒng)的緩存一致性,還需要負(fù)責(zé)處理對共享存儲器的請求；為了提高帶寬,將數(shù)據(jù)通道和指令通道分開；再加上主存儲單元,從而得到高性能的CK810MP多核處理器．

圖6　CK810MP多核處理器總體架構(gòu)Fig.6　Architecture of CK810MP multi-core processor

為了利用GA驅(qū)動測試產(chǎn)生器生成高質(zhì)量的測試,首先需要設(shè)置GA的參數(shù).參數(shù)設(shè)置情況如表1所示,將測試集合的大小M設(shè)置為50,交叉率Pc和變異率Pn分別設(shè)置為0.9和0.1．

表1　遺傳算法的參數(shù)設(shè)置

為了評估本文所提出的基于GA的CDTG的效率,在CK810MP的驗證環(huán)境中建立一個隨機(jī)測試產(chǎn)生器(random test generator,RTG)作對比,并分別基于文獻(xiàn)[24]和[25]中提出的適應(yīng)度函數(shù)建立2個CDTG.其中,文獻(xiàn)[24]提出的適應(yīng)度函數(shù)是基于代碼覆蓋率的,可以表示為

式中：L表示被覆蓋的代碼行數(shù),N表示代碼的總行數(shù).另外,文獻(xiàn)[25]提出的適應(yīng)度函數(shù)是基于功能覆蓋率的,是利用某一個指定的功能點的覆蓋情況評估測試的適應(yīng)度．

4.2基于CK810雙核處理器的實驗

本節(jié)中的第一個實驗關(guān)注整個雙核處理器的功能覆蓋率.定義文獻(xiàn)[24]的適應(yīng)度函數(shù)為整個雙核處理器的語句覆蓋率.讀寫單元和核間互連一起維護(hù)多核處理器系統(tǒng)的高速緩存一致性,是CK810MP系統(tǒng)中最復(fù)雜也是最重要的單元之一.選定讀寫單元中的一個非常重要的功能點,用于產(chǎn)生文獻(xiàn)[25]的適應(yīng)度函數(shù),這個功能點的作用是觀測緩沖器的使用情況.如圖7所示為整個雙盒處理器的功能覆蓋率的對比情況,其中c表示功能覆蓋率,t表示測試的數(shù)量.從圖7可以看出,使用本文提出的測試產(chǎn)生器大約需要297個測試可以得到100%的功能覆蓋率；使用基于文獻(xiàn)[24]的適應(yīng)度函數(shù)的CDTG大約需要375個測試可以得到100%的功能覆蓋率；使用基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG和隨機(jī)測試產(chǎn)生器都需要1 000個測試才可以得到大約97%的覆蓋率.這表示本文提出的測試產(chǎn)生器可以覆蓋到隨機(jī)測試產(chǎn)生器無法覆蓋的功能點,而且驗證時間可以減少大約70%.同時,本文提出的適應(yīng)度函數(shù)比文獻(xiàn)[24]提出的適應(yīng)度函數(shù)可以更準(zhǔn)確地評估測試的質(zhì)量,因為文獻(xiàn)[24]的適應(yīng)度函數(shù)是基于代碼覆蓋率的.在此,舉一個簡單的示例來說明這一點,假設(shè)測試M可以覆蓋7行代碼,但是這7代碼覆蓋不到任何功能點；雖然另一個測試N只能覆蓋3行代碼,但是這3行代碼可以覆蓋到一個之前的測試從來覆蓋過的重要功能點.顯然,測試N比測試M更有價值,但是按照文獻(xiàn)[24]提出的適應(yīng)度函數(shù)計算,測試M比測試N的適應(yīng)度更高.實驗結(jié)果還說明,相對于隨機(jī)測試產(chǎn)生器,使用基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG無法明顯地減少需要仿真的測試數(shù)量,因為文獻(xiàn)[25]提出的適應(yīng)度函數(shù)不能很好地用于評估測試的質(zhì)量,原因在于該函數(shù)只關(guān)注一個選定的功能點的覆蓋情況,但是在龐大的多核處理器系統(tǒng)中,肯定不止有一個需要覆蓋的功能點．

圖7　基于不同適應(yīng)度函數(shù)的CDTG雙核處理器系統(tǒng)覆蓋率對比情況Fig.7　Comparison of coverage curves of dual-core processor system based on CDTGs of different fitness functions

本節(jié)中的第2個實驗只關(guān)注讀寫單元的功能覆蓋率.如圖8所示為讀寫單元覆蓋率的對比情況.在圖8(a)中,將雙核處理器所有功能點的權(quán)重都設(shè)置為1,用于評估測試的質(zhì)量和價值.同時,文獻(xiàn)[24]的適應(yīng)度函數(shù)與第4.2節(jié)的第一個實驗相同.從圖8(a)可以看出,使用隨機(jī)測試產(chǎn)生器需要1 000個測試才能得到大約95%的覆蓋率,驗證效率非常低；使用基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG需要1 000個測試可以得到大約96%的覆蓋率,這說明相對于隨機(jī)測試產(chǎn)生器,基于文獻(xiàn)[25]提出的適應(yīng)度函數(shù)的CDTG無法明顯地提高驗證效率；使用基于文獻(xiàn)[24]的適應(yīng)度函數(shù)的CDTG大約需要309個測試可以得到100%的功能覆蓋率,驗證效率得到了極大的提高；而使用本文提出的測試產(chǎn)生器需要大約243個測試就可以得到100%的覆蓋率,這表示讀寫單元的驗證效率在使用本文提出的方法以后得到了進(jìn)一步提高.因為本節(jié)只須關(guān)注讀寫單元的功能覆蓋情況,而不需要關(guān)心其他單元的覆蓋情況,所以可以通過調(diào)整其他單元的功能點的權(quán)重優(yōu)化適應(yīng)度函數(shù),進(jìn)一步提高算法的效率.在圖8(b)中,將讀寫單元中的功能點的權(quán)重設(shè)置為1,而將其他功能點的權(quán)重設(shè)置為0,優(yōu)化適應(yīng)度函數(shù),對測試的質(zhì)量進(jìn)行更加準(zhǔn)確地評估.同時,定義文獻(xiàn)[24]中提出的適應(yīng)度函數(shù)為讀寫單元的語句覆蓋率.從圖8(b)可以看出,使用文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG和隨機(jī)測試產(chǎn)生器需要仿真1000個測試,此時讀寫單元的覆蓋率大約是96%；在對適應(yīng)度函數(shù)進(jìn)行優(yōu)化以后,使用本文提出的覆蓋率驅(qū)動測試產(chǎn)生器,大約需要194個測試就可以得到100%的覆蓋率；而使用文獻(xiàn)[24]提出的適應(yīng)度函數(shù)大約需要237個測試才可以得到100%的覆蓋率.這說明當(dāng)只關(guān)注于某一個單元的功能點覆蓋情況時,可以對適應(yīng)函數(shù)中的功能點權(quán)重進(jìn)行調(diào)整,將不需要關(guān)注的單元的功能點的權(quán)重設(shè)置為0,這樣測試的質(zhì)量的評估情況只會受被測試單元的功能點覆蓋情況的影響,而減少甚至屏蔽其他單元的影響,可以更加準(zhǔn)確地評估測試的價值和質(zhì)量,使得反饋的信息更加準(zhǔn)確,提高算法的準(zhǔn)確度和系統(tǒng)的驗證效率.同時,實驗結(jié)果再次說明,和文獻(xiàn)[24]中提出的基于代碼覆蓋率的適應(yīng)度函數(shù)以及文獻(xiàn)[25]提出的適應(yīng)度函數(shù)相比,本文提出的適應(yīng)度函數(shù)的選擇效率更高,可以更加準(zhǔn)確地選出高質(zhì)量的測試．

圖8　基于不同適應(yīng)度函數(shù)的CDTG雙核處理器讀寫單元的覆蓋率對比情況Fig.8　Comparison of coverage curves of Load Store Unit in dual-core processor system based on CDTGs of different fitness functions

4.3基于CK810四核處理器的實驗

圖9　基于不同適應(yīng)度函數(shù)的CDTG系統(tǒng)覆蓋率對比情況Fig.9　Comparison of coverage curves of quad-core processor system based on CDTGs of different fitness functions

本節(jié)的第一個實驗關(guān)注一個CK810四核處理器的所有功能點的覆蓋情況，定義文獻(xiàn)[24]提出的適應(yīng)度函數(shù)為整個四核處理器的語句覆蓋率.如圖9所示為功能覆蓋率的對比情況.從圖9可以看出,使用基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG和隨機(jī)測試產(chǎn)生器都需要2 000個測試才可以得到大約93%的覆蓋率；使用基于代碼覆蓋率的適應(yīng)度函數(shù)的CDTG大約需要633個測試可以得到100%的功能覆蓋率；而使用本文提出的測試產(chǎn)生器大約需要552個測試就可以得到100%的功能覆蓋率；實驗數(shù)據(jù)說明,在四核處理器的驗證環(huán)境中,本文提出的適應(yīng)度函數(shù)依舊比文獻(xiàn)[24]和[25]提出的適應(yīng)度函數(shù)高效,可以更加準(zhǔn)確地選出高質(zhì)量的測試.而且,在四核處理器的驗證環(huán)境中,本文提出的方法同樣可以覆蓋到隨機(jī)測試產(chǎn)生器無法覆蓋的功能點,可以在短時間內(nèi)得到更高的功能覆蓋率,提高驗證效率．

圖10　基于不同適應(yīng)度函數(shù)的CDTG四核處理器讀寫單元的覆蓋率對比情況Fig.10　Comparison of coverage curves of load store unit in quad-core processor system based on CDTGs of different fitness functions

本節(jié)的第二個實驗關(guān)注讀寫單元的功能點的覆蓋情況,文獻(xiàn)[25]的適應(yīng)度函數(shù)和以上實驗相同.如圖10所示為讀寫單元的功能覆蓋情況.在圖10(a)中,將整個四核處理器的所有功能點的權(quán)重都設(shè)置為1,用于評估測試的質(zhì)量和價值.同時,和第3個實驗相同,用整個四核處理器系統(tǒng)的代碼覆蓋比例作為文獻(xiàn)[24]提出的適應(yīng)度函數(shù).從圖10(a)可以看出,使用本文提出的方法需要大約419個測試可以得到100%的功能覆蓋率；使用基于文獻(xiàn)[24]的適應(yīng)度函數(shù)的CDTG大約需要505個測試；而使用基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG和隨機(jī)測試產(chǎn)生器需要2 000個測試才可以得到大約90%的功能覆蓋率.實驗數(shù)據(jù)說明,當(dāng)只關(guān)注讀寫單元時,本文提出的方法和隨機(jī)測試產(chǎn)生器相比,本文提出的方法可以明顯減少CK810四核處理器的讀寫單元的驗證時間.在圖10(b)中,將讀寫單元的功能點的權(quán)重設(shè)置為1,將其他單元的功能點的權(quán)重設(shè)置為0,優(yōu)化適應(yīng)度函數(shù).同時,定義文獻(xiàn)[24]提出的適應(yīng)度函數(shù)為讀寫單元的語句覆蓋率.從圖10(b)可以看出,隨機(jī)測試測試產(chǎn)生器和基于文獻(xiàn)[25]的適應(yīng)度函數(shù)的CDTG最終只能得到大約90%的功能覆蓋率；使用基于文獻(xiàn)[24]提出的適應(yīng)度函數(shù)的CDTG需要大約437個測試得到100%的功能覆蓋率,驗證效率得到了極大的提高；而使用本文提出的方法驗證效率可以得到進(jìn)一步提高,得到100%的功能覆蓋率只需要大約356個測試.實驗數(shù)據(jù)說明,當(dāng)根據(jù)驗證的需要適當(dāng)調(diào)整和優(yōu)化適應(yīng)度函數(shù)以后,本文提出的測試產(chǎn)生器的效率可以得到進(jìn)一步提高．

5結(jié)語

本文提出了一種基于遺傳算法的覆蓋率驅(qū)動測試產(chǎn)生器,利用一個基于功能覆蓋率的適應(yīng)度函數(shù)評估測試的質(zhì)量和價值,通過遺傳算法建立覆蓋率分析結(jié)果和測試產(chǎn)生器之間的聯(lián)系,驅(qū)動測試產(chǎn)生器生成質(zhì)量更高的測試,新一代的測試具有更高的適應(yīng)度,可以覆蓋到上一代的測試無法覆蓋的功能點.實驗結(jié)果表明,和隨機(jī)測試產(chǎn)生器相比,本文提出的測試產(chǎn)生器可以在短時間內(nèi)得到更高的功能點覆蓋率,減少了驗證時間,提高了驗證效率.另外,本文提出的適應(yīng)度函數(shù)和基于語句覆蓋率的適應(yīng)度函數(shù)相比,可以更加準(zhǔn)確地評估測試的質(zhì)量和價值,從而選出高質(zhì)量的測試．

在本文中,遺傳算法的參數(shù)是固定不變的,這樣容易造成遺傳算法陷入局部最優(yōu)解.今后,將對遺傳算法的參數(shù)和測試的權(quán)重的自適應(yīng)做進(jìn)一步的研究,以得到遺傳算法的局部最優(yōu)解,產(chǎn)生質(zhì)量更高的測試,提高驗證效率．

參考文獻(xiàn)(References)：

[1] WANG S, HUANG K, XIE T, et al. Hybrid model: an efficient symmetric multiprocessor reference model [J]. Journal of Electrical and Computer Engineering, 2015,2015:23.

[2] FINE S, ZIV A. Coverage directed test generation for functional verification using Bayesian networks [C] ∥Proceeding of the 40th Annual Design Automation Conference. New York: IEEE, 2003: 286-291．

[3] BRAUN M, FINE S, ZIV A. Enhancing the efficiency of Bayesian network based coverage directed test generation [C] ∥ Proceeding of IEEE International Workshop on High-Level Design Validation and Test. New York: IEEE, 2004: 75-80．

[4] FINE S, FREUND A, JAEGER I, et al. Harnessing machine learning to improve the success rate of stimuli generation [J]. IEEE Transaction on Computers, 2006, 55(11): 1344-1355．

[5] BARAS D, FINE S, FOURNIER L, et al. Automatic boosting of cross-product coverage using Bayesian networks [J]. International Journal on Software Tools for Technology Transfer, 2011, 13(3): 247-261．

[6] WAGBER I, BERTACCO V, AUSTIN T. StressTest: an automatic approach to test generation via activity monitors [C]∥ Proceeding of the 42nd annual Design Automation Conference. New York: ACM, 2005: 783-788．[7] WAGBER I, BERTACCO V, AUSTIN T. Microprocessor verification via feedback-adjusted Markov models [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(6): 1126-1138．[8] EDER K, FLACH P, HSUEH H W. Towards automating simulation-based design verification using ILP [C]∥ Proceeding of the 16th International Conference, ILP 2006. Berlin: Springer Press, 2007: 154-168．

[9] IOANNIDES C, EDER K I. Coverage directed test generation automated by machine learning-a review [J]. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2012, 17(1): 1-23．

[10] 馬永杰, 云文霞. 遺傳算法研究進(jìn)展[J]. 計算機(jī)應(yīng)用研究, 2012, 29(4): 1201-1210．

MA Yong-jie, YUN Wen-xia. Research progress of genetic algorithm [J]. Application Research of Computers, 2012, 29(4): 1201-1210．

[11] ARABALI A, GHOFRANI M, ETEZADI-AMOLI M, et al. Genetic-algorithm-based optimization approach for energy management [J]. IEEE Transactions on Power Delivery, 2012, 28(1): 162-170．

[12] CHA Y J, AGRAWAL A K. Decentralized output feedback polynomial control of seismically excited structures using genetic algorithm [J]. Structural Control and Health Monitoring, 2013, 20(3): 241-258．

[13] 方水良, 姚嫣菲, 趙詩奎. 柔性車間調(diào)度的改進(jìn)遺傳算法[J]. 浙江大學(xué)學(xué)報: 工學(xué)版, 2012, 46(4): 629-635．

FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling [J]. Journal of Zhejiang University: Engineering Science, 2012, 46(4): 629-635．

[14] 壽涌毅, 彭曉峰, 李菲, 等. 搶占式資源受限項目調(diào)度問題的遺傳算法[J]. 浙江大學(xué)學(xué)報: 工學(xué)版, 2014, 48(8): 1473-1480．

SHOU Yong-yi, PENG Xiao-feng, LI Fei, et al. Genetic algorithm for the preemptive resource-constrained project scheduling problem [J]. Journal of Zhejiang University: Engineering Science, 2014, 48(8): 1473-1480．

[15]TONELLA P, SUSI A, PALMA F. Interactive requirements prioritization using a genetic algorithm [J]. Information and Software Technology, 2013, 55(1): 173-187．[16] MA Y, CUI X. Solving the fuel transportation problem based on the improved genetic algorithm [C] ∥ Proceeding of the 10th International Conference on Natural Computation (ICNC). New York: IEEE, 2014: 584-588．[17] TORRES J, GUARDADO J L, RIVAS-DAVALOS F, et al. A genetic algorithm based on the edge window decoder technique to optimize power distribution systems reconfiguration [J]. Electrical Power and Energy Systems, 2013, 45(1): 28-34．

[18] SMITH J E, BARTLEY M, FOGARTY T C. Microprocessor design verification by two-phase evolution of variable length tests [C] ∥Proceeding of IEEE International Conference on Evolutionary Computation. New York: IEEE, 1997: 453-458．

[19] BOSE M, SHIN J, RUDNICK E M, et al. A genetic approach to automatic bias generation for biased random instruction generation [C] ∥ Proceeding of the 2001 Congress on Evolutionary Computation. New York: IEEE, 2001: 442-448．

[20]YU X, FIN A, FUMMI F, et al. A genetic testing framework for digital integrated circuits [C] ∥ Proceeding of the 14th IEEE International Conference on Tools with Artificial Intelligence. New York: IEEE, 2002: 521-526．

[21] SAMARAH A, HABIBI A, TAHAR S, et al. Automated coverage directed test generation using a cell-based genetic algorithm [C] ∥ Proceeding of the 11th Annual IEEE International High-Level Design Validation and Test Workshop. New York: IEEE, 2006: 19-26．

[22] HABIBI A, TAHAR S, SAMARAH A, et al. Efficient assertion based verification using TLM [C] ∥ Proceeding of Design, Automation and Test in Europe. New York: IEEE, 2006: 1-6．

[23] SHEN H, WEI W, CHEN Y, et al. Coverage directed test generation: godson experience [C] ∥ Proceeding of the 17th Asian Test Symposium. New York: IEEE, 2008: 321-326．

[24]SUBEDHA V, SRIDHAR S. An efficient coverage driven functional verification system based on genetic algorithm [J]. European Journal of Scientific Research, 2012, 81(4): 321-326．

[25] WANG J, LIU Z, WANG S, et al. Coverage-directed stimulus generation using a genetic algorithm [C] ∥ Proceeding of the 2013 International SoC Design Conference (ISOCC). New York: IEEE, 2013: 17-19．

DOI:10.3785/j.issn.1008-973X.2016.03.024

收稿日期：2012-10-17.

基金項目：國家自然科學(xué)基金資助項目(61100074),核高基國家科技重大專項資助項目(2012ZX01039-004)；中央高?；A(chǔ)研究基金資助項目(2013QNA5008).

作者簡介：王樹朋(1990-), 男, 博士生, 從事多核處理器驗證研究.ORCID: 0000-0003-2322-2856. E-mail: wangsp@vlsi.zju.edu.cn 通信聯(lián)系人：黃凱, 男, 副教授.ORCID: 0000-0002-5034-7171. E-mail: huangk@vlsi.zju.edu.cn

中圖分類號：TN 47

文獻(xiàn)標(biāo)志碼：A

文章編號：1008-973X(2016)03-09-0580

Coverage directed test generation based on genetic algorithm

WANG Shu-peng1, HUANG Kai1, YAN Xiao-lang2

(1.DepartmentofInformationScienceandElectronicEngineering,ZhejiangUniversity,Hangzhou310027,China; 2.InstituteofVLSIDesign,ZhejiangUniversity,Hangzhou310027,China)

Abstract:Coverage directed test generation based on genetic algorithm (GA)was proposed to close the loop between coverage analysis and test generation and produce the tests of good quality. A simple and accurate test encoding method was proposed. A fitness function based on functional coverage was used to evaluate the quality of tests. GA was used to close the loop between coverage analysis and test generation. The coverage results were evaluated and the constraints for test generation were modified to direct the test generation to produce the new tests, which can cover the functions that the old tests can’t cover. The experiments were conducted based on the simulation environment for verifying two high-performance 32-bit multi-core processors. Results show that the proposed method can significantly reduce simulation time and improve verification efficiency．

Key words:coverage; test generation; genetic algorithm (GA); coverage directed test generation; fitness function