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

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

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

?

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

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

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

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

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

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

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

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

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

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

1遺傳算法

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

{

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

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

}

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

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

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

}

End

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

2測試編碼方法

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

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

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

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

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

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

圖2　基于遺傳算法的覆蓋率驅(qū)動(dòng)測試產(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分別表示初始的測試集合和測試集合中測試的個(gè)數(shù)；F、G和Y分別表示選擇算子、交叉算子和變異算子；T表示終止的條件和規(guī)則.為了在分析覆蓋率以后,用遺傳算法驅(qū)動(dòng)測試產(chǎn)生器生成質(zhì)量更高的測試,需要確定這8個(gè)變量.第2章介紹了測試的染色體編碼方法C,本章主要介紹其他7個(gè)變量．

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

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

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

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

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

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

圖4　單點(diǎn)交叉的簡單示例Fig.4　Simple example of one-point crossover

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

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

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

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

4實(shí)驗(yàn)結(jié)果及分析

4.1實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

4.2基于CK810雙核處理器的實(shí)驗(yàn)

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

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

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

圖8　基于不同適應(yīng)度函數(shù)的CDTG雙核處理器讀寫單元的覆蓋率對(duì)比情況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四核處理器的實(shí)驗(yàn)

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

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

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

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

5結(jié)語

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

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

參考文獻(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ì)算機(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é)報(bào): 工學(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] 壽涌毅, 彭曉峰, 李菲, 等. 搶占式資源受限項(xiàng)目調(diào)度問題的遺傳算法[J]. 浙江大學(xué)學(xué)報(bào): 工學(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.

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

作者簡介：王樹朋(1990-), 男, 博士生, 從事多核處理器驗(yàn)證研究.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

中圖分類號(hào)：TN 47

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

文章編號(hào)：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