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

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

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

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

（一）問題描述

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

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

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

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

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

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

上面是從時(shí)間角度進(jìn)行的問題轉(zhuǎn)化，也可以從空間角度考慮，把用例耗時(shí)對應(yīng)空間大小，把問題轉(zhuǎ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（鍵-用例名，值-用例對應(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ì)說明，這里不再贅述。 最終，蟻群算法會得到最優(yōu)的任務(wù)分配矩陣，我們通過這個(gè)矩陣就可以知道每個(gè)隊(duì)列分配了那幾個(gè)用例。

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

4）自動回歸：剛剛生成了sub_makefile，我們再新建一個(gè)腳本，實(shí)現(xiàn)“自動打開指定個(gè)數(shù)terminal，在每個(gè)terminal自動輸入相應(yīng)回歸命令（make）即可”。

（四）問題的問題

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

另外，在實(shí)際應(yīng)用中，蟻群算法有以下問題①在有限迭代次數(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ù)分配方案。*

審核編輯：劉清