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

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

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

（一）問題描述

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

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

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

那么，是否可以找到更好的回歸隊列分配給各個terminal， ***使得回歸總時間最短*** ？

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

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

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

（三）問題解決

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

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

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

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

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

（四）問題的問題

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

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

審核編輯：劉清