蟻群算法在驗(yàn)證用例自動(dòng)化回歸中的應(yīng)用有哪些？

背景：如今的芯片規(guī)模越來(lái)越大，功能也愈加復(fù)雜。相應(yīng)的驗(yàn)證用例也越來(lái)越復(fù)雜，用例動(dòng)態(tài)仿真耗時(shí)也隨之增加，而且個(gè)數(shù)有時(shí)動(dòng)輒上百個(gè)。

在驗(yàn)證回歸過(guò)程中，如何提高效率成為廣大驗(yàn)證工程師不得不考慮的問(wèn)題。

本文嘗試在驗(yàn)證工作中，通過(guò)蟻群算法優(yōu)化用例回歸序列，盡量縮短回歸時(shí)間，同時(shí)提高用例回歸的自動(dòng)化程度。

（一）問(wèn)題描述

假設(shè)當(dāng)前有108個(gè)用例需要回歸，并且我們有先前用例仿真的日志文件：日志文件中有該用例仿真的耗時(shí)信息。

按照傳統(tǒng)做法，我們可能首先打開(kāi)十多個(gè)terminal（比如15個(gè)），平均每個(gè)terminal分配若干用例（比如7個(gè)），根據(jù)用例名的字典序回歸用例。

在大多數(shù)情況下，會(huì)有個(gè)別terminal中分配的用例很快或較快的回歸完，而其余幾個(gè)terminal時(shí)間卻又很長(zhǎng)，遲遲不能完成，時(shí)間最長(zhǎng)的那個(gè)terminal決定了一次回歸所用的總時(shí)間。

那么，是否可以找到更好的回歸隊(duì)列分配給各個(gè)terminal， ***使得回歸總時(shí)間最短*** ？

（二）問(wèn)題轉(zhuǎn)化

現(xiàn)在，問(wèn)題就可以轉(zhuǎn)化為：108個(gè)耗時(shí)不等的任務(wù)，分配給15個(gè)并行隊(duì)列，求15個(gè)隊(duì)列的任務(wù)序列組合，使得15個(gè)隊(duì)列的總耗時(shí)最小；這個(gè)任務(wù)分配問(wèn)題可以進(jìn)一步引申為**負(fù)載調(diào)度**問(wèn)題，108個(gè)任務(wù)分配給15臺(tái)性能各異（或同等）的服務(wù)器。

上面是從時(shí)間角度進(jìn)行的問(wèn)題轉(zhuǎn)化，也可以從空間角度考慮，把用例耗時(shí)對(duì)應(yīng)空間大小，把問(wèn)題轉(zhuǎn)化為 **存儲(chǔ)問(wèn)題** ，本文暫不研究。

（三）問(wèn)題解決

我們參考作者的JavaScript代碼，考慮用perl實(shí)現(xiàn)算法的核心代碼。具體步驟如下：

1）提取時(shí)間信息：即從仿真日志里提取時(shí)間信息，分兩步①粗提取，這個(gè)使用shell命令即可，可以放到makefile中；②準(zhǔn)確提取，在剛剛的makefile中調(diào)用perl腳本，在perl腳本中利用perl強(qiáng)大的文本處理能力提取準(zhǔn)確的時(shí)間信息，存入一個(gè)哈希%Case_hash（鍵-用例名，值-用例對(duì)應(yīng)的時(shí)間）中。

2）蟻群算法的perl實(shí)現(xiàn)：除了剛剛得到的哈希數(shù)組%Case_hash，我們還要給定隊(duì)列數(shù)目QueneNum，這是蟻群算法的輸入。同時(shí)，蟻群算法還涉及螞蟻數(shù)量AntNum，迭代次數(shù)ItNum，隨機(jī)因子等參數(shù)，參考文獻(xiàn)[1]中有詳細(xì)說(shuō)明，這里不再贅述。 最終，蟻群算法會(huì)得到最優(yōu)的任務(wù)分配矩陣，我們通過(guò)這個(gè)矩陣就可以知道每個(gè)隊(duì)列分配了那幾個(gè)用例。

3）回歸隊(duì)列生成：得到用例回歸隊(duì)列后，將這些隊(duì)列以target形式寫(xiě)入新的makefile中（sub_makefile，在主makefile中include這個(gè)sub_makefile）。

4）自動(dòng)回歸：剛剛生成了sub_makefile，我們?cè)傩陆ㄒ粋€(gè)腳本，實(shí)現(xiàn)“自動(dòng)打開(kāi)指定個(gè)數(shù)terminal，在每個(gè)terminal自動(dòng)輸入相應(yīng)回歸命令（make）即可”。

（四）問(wèn)題的問(wèn)題

在perl實(shí)現(xiàn)蟻群算法時(shí)，矩陣的處理可能會(huì)稍微麻煩一些，這里使用了哈希嵌套的做法[2]。

另外，在實(shí)際應(yīng)用中，蟻群算法有以下問(wèn)題①在有限迭代次數(shù)內(nèi)，算法不收斂；②算法收斂，但得到的最優(yōu)解是**局部最優(yōu)解**，非全局最優(yōu)解。局部最優(yōu)解是傳統(tǒng)蟻群算法的缺點(diǎn)之一。實(shí)際使用時(shí)可以折衷考慮，適當(dāng) *增大迭代次數(shù)* ，同時(shí)提高蟻群的 *隨機(jī)性* ，在有限的迭代次數(shù)內(nèi)*持續(xù)搜尋最短時(shí)間的任務(wù)分配方案。*

審核編輯：劉清