一種改進的基于遺傳算法的測試調度方法

劉　偉，李　斌

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

?

一種改進的基于遺傳算法的測試調度方法

劉偉，李斌

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

摘要：提出了一種改進的基于遺傳算法的SoC測試調度方法，通過該方法可以有效地優化測試總線的劃分，合理調度各個IP核以實現并發測試，能夠有效地縮短芯核測試時間。該算法把測試調度問題的可行解集用種群表示，逐代演化產生出越來越好的近似解。詳細分析了該算法過程，對2002年國際測試會議(ITC’02)所提供的SoC國際基準電路進行測試調度實驗，實驗結果表明，此算法比傳統的整數線性規劃(ILP)和遺傳算法的結果要好。

關鍵詞：遺傳算法；SoC測試；測試調度

0引言

隨著半導體工藝技術的發展，IC設計者越來越傾向于使用內嵌的IP(intellectual property)核設計系統級芯片(system on chip,SoC)。這很大程度地縮短了產品進入市場的時間，同時也給SoC的測試帶來很多新的挑戰。通常，在一個SoC芯片上有幾十個IP核，因此，為了減少測試時間，降低測試成本，如何分配測試資源和安排各個IP核的測試順序成為一個很重要的問題。很多研究人員在測試調度方面做了很多工作。K.Chakrabarty把測試調度問題看成線性規劃問題使測試時間最小化[1-3]。Lei Jia等提出了一種用遺傳算法(genetic algorithm,GA)解決測試調度問題的方法[4]。

本文基于對傳統遺傳算法的分析，提出了一種改進的遺傳算法，問題的解通過序列對表示。

1SoC測試優化問題劃分

在IEEE1500標準中，提出了一種基于測試外殼(Wrapper)的測試結構。測試外殼是一個連接芯核與TAM的接口，提供對芯核的常規功能存取和通過TAM對芯核進行測試數據的存取。為了有效解決Wrapper和TAM之間的組合優化，按照復雜度的不同，V.Iyengar等人將這種組合優化問題劃分為PW、PAW、PPAW和PNPAW[1]4個問題：

① PW問題：對給定的IP核設計測試外殼，使得這個核的測試時間和TAM寬度最小。

② PAW問題：給定NC個IP核和B條測試總線，每條測試總線的寬度分別為ω1，ω2，…，ωn，B條測試總線的總寬度為W，確定一種最優的組合將每一個核連接到各組測試總線上，使得SoC總的測試時間最少。

③ PPAW問題：給定NC個IP核，測試總線的總寬度為W，需要將W條測試總線劃分為B組，將每一個核連接到各組測試總線上,使得芯片的總測試時間最少。PAW問題與PPAW問題的區別是PAW問題給定了每條測試總線的寬度，而PPAW問題要自己劃分每條測試總線的寬度。

④ PNPAW問題：只給定了NC個IP核和測試總線的總寬度為W，需要確定總線劃分成多少組，每組測試總線的寬度是多少，使得將每一個核連接到各組測試總線上使得芯片的總測試時間最少。

PW問題與背包問題類似，用BFD啟發式算法可以比較好地解決[1,5]，對于PAW、PPAW和PNPAW問題，可以映射為整數線性規劃(ILP)問題[2,3,6]；也可以映射為平面規劃問題并結合各種啟發類算法解決，本文重點研究PPAW問題。

2SoC 的測試調度

給定NC個IP核和測試總線的總寬度為W，則每個IP核Ci(1iNC)的測試配置可以用一個數組(Wij,T(Wij))表示，Wij表示第j組測試總線上IP核Ci的測試總線寬度，T(Wij)表示對應的測試時間。SoC測試調度的目標是決定每個IP核的測試開始時間和結束時間,以使總的測試時間最小。

這個問題可以映射為平面規劃問題[7]，平面的高表示固定的總線寬度W，平面的寬表示總的SoC的測試時間。這時每個IP核的測試可以用一個高為Wij，寬為T(Wij)的矩形表示。目標就變為對每個IP核Ci設計一個矩形，并把所有的矩形都放在平面內，以使在總的高度不超過W的情況下總的寬度最小。且此時平面中的矩形不能相互重疊，因為任一測試總線在同一時間只能連接一個IP核。SoC測試調度問題轉變為平面規劃問題示意圖如圖1所示。

圖1　平面規劃問題示意圖

3用遺傳算法解決SoC的測試調度問題

3.1序列對結構

序列對結構是一種表示平面規劃問題中矩形相對位置的十分有效的方法[8]。因為SoC的測試調度問題能夠映射為平面規劃問題，所以也可以用序列對來描述SoC的測試調度。

一組矩形的序列對(T+,T-)是2個序列，每個序列都包含所有的矩形。例如，(a b c ,c b a)是矩形a，b和c的一個序列對。序列對中矩形的相對位置可以通過下面2個規則確定。

規則1：序列對形式為(…a…b…，…a…b…)時，a在b的左邊。

規則2：序列對形式為(…b…a…，…a…b…)時，a在b的下邊。

給定一個序列對，根據序列對(T+,T-)中序列的順序畫斜線構建網格結構，則所有矩形分布在具有相同坐標的網線的交點處，序列對(a b c d e,d b e a c)對應的網格結構如圖2所示。

圖2　序列對網格結構

每個序列對對應2個加權連接圖，水平連接圖和垂直連接圖。這2個圖可以由網格中的頂點位置確定。在水平連接圖Gh中，當且僅當a在b的左邊時，存在一條由a到b的連線；在垂直連接圖Gv中，當且僅當a在b下面時，存在一條由a指向b的連線；此外每個連接圖中都存在源節點和宿節點。水平連接圖Gh中連接線的權重代表對應矩形的寬，垂直連接圖Gv中連接線的權重代表對應矩形的高。所以，Gh和Gv中最長路徑的長度分別代表平面規劃的寬和高。也就是SoC測試調度問題中總的測試時間和測試總線帶寬。序列對(a b c d e,d b e a c)的水平連接圖Gh和垂直連接圖Gv如圖3和圖4所示。

圖3　水平連接圖Gh

圖4　垂直連接圖Gv

3.2遺傳算法

遺傳算法是從代表問題可能潛在解集的一個種群開始，按照適者生存、優勝劣汰的原理，逐漸進化產生近似最優解[9]。在每一代中，根據個體適應度大小進行篩選，并借助自然遺傳學的遺傳算子進行交叉組合和變異，生成代表新的解集的種群。這個過程使種群像自然進化一樣越來越適應環境，其對應的解也越來越接近最優解[10-12]。最后，末代種群的最優個體經過解碼，可作為問題的近似最優解。

遺傳算法包括選擇、交叉和變異3種基本操作，遺傳算法的基本流程圖如圖5[13]所示。

圖5　遺傳算法流程圖

遺傳算法的結果由序列對表示，目標是在總線寬度不超過Wmax的情況下，使測試時間最小化。傳統遺傳算法的偽代碼為：

① 設置適應度C為水平連接圖Gh中最長路徑的長度；限制條件為Gv≤Wmax;

② 設置Gen=0,隨機產生可能解的初始種群；

③ 計算每個解的適應度C；

④ 通過2個初始解的交叉組合產生2個子代Ⅰ和Ⅱ；

⑤ 通過對子代Ⅰ和Ⅱ進行變異操作產生2個子代Ⅲ和Ⅳ，選擇4個中最好的2個解作為下一代；

⑥ 計算當前種群的解，選出最優方案；

⑦Gen=Gen+1，如果Gen<1 000，進入第④步；

⑧ 得出最優解；

⑨ 結束。

對于交叉組合操作，選擇2個序列對，隨機選擇一個位置l(1≤l≤Nc)，交換2個序列對T+中l位置的IP核和對應T-位置的IP核。例如，在序列對Ⅰ的T+中，l位置對應的IP核為P，在序列對Ⅱ中l位置對應的IP核為Q。交叉組合操作就會交換P和Q在T+和T-中的位置。

變異操作通過下面幾種方法施行，每個方法使用的概率分別為0.3,0.1,0.2,0.2,0.2。

① 交換T+中2個相鄰IP核的位置；

② 在T-中隨機選擇2個IP核，交換它們的位置；

③ 在T+中隨機選擇連個位置，顛倒2個位置之間的IP核的順序；

④ 隨機選擇一個IP核，在T+中隨機選擇一個位置插入。

⑤ 改變矩形的寬和高。

分析算法可以發現，在產生后代的過程中，是通過對子代適應度的排序，選擇適應度最好的2個進入下一代母本，在這個過程中，并沒有把母本的方案考慮進去，也就是說，子代方案不一定比上一代好，即下一代方案測試時間不一定比上一代更少。

針對以上情況，提出一種改進的遺傳算法(improved genetic algorithm,IGA)，偽代碼如下：

① 設置代價函數C為水平連接圖Gh中最長路徑的長度；限制條件為Gv≤Wmax;

② 設置Gen=0,隨機產生可能解的初始種群；

③ 計算每個解的適應度C；

④ 通過2個初始解的交叉組合產生2個子代Ⅰ和Ⅱ；

⑤ 通過對子代Ⅰ和Ⅱ進行變異操作產生2個子代Ⅲ和Ⅳ，計算母代與4個子代的適應度，選擇最好的2個解作為下一代；

⑥ 計算當前種群的解，選出最優方案；

⑦Gen=Gen+1，如果Gen<1 000，進入第④步；

⑧ 得出最優解；

⑨ 結束。

在選擇下一代的過程中，通過把母本方案考慮進去，保證了下一代的適應度比上一代更好，即測試時間更少，因此算法在理論上可以得到更好的近似最優解，使測試時間更短。當然，算法的復雜度也略有增加。本算法以50個隨機產生的父母作為初始種群，每一個父母對應一個序列對。通過上述的交叉組合，變異和選擇產生后代種群。

4實驗結果

采用ITC’02所提供的SoC測試基準電路d695作為實驗電路。用C語言實現了遺傳算法程序，同時也實現了文獻[1]所描述的ILP(integer linear programming)算法，最后得到的測試時間如表1所示。從表1可以看出，GA算法的測試周期幾乎都小于ILP算法的測試周期，而IGA算法的測試周期又比以上2種算法小。

表1　基準電路OTC’02(D695)上的實驗結果

5結束語

通過研究Wrapper/TAM組合優化算法，提出了一種改進的遺傳算法解決SoC的測試調度問題。測試調度問題被映射成平面規劃問題，并通過序列對表示，然后用遺傳算法尋找最優解。實驗結果表明，算法的測試周期比ILP算法和傳統遺傳算法的測試周期要少。所以，此改進的遺傳算法在減少SoC測試時間上是有效的。

參考文獻

[1]Iyengar V,Chakrabarty K,Marinisen J.Test Wrapper and Test Access Mechanism Co-Optimization for System-on-chip[C]∥J.Electronic Testing:Theory and Applicaton,2002:213-230.

[2]Chakrabarty K.Design of System on Chip Test Access Architectures Using Integer Programming[C]∥Proc.VLSI Symposium,2000:127-134.

[3]Chakrabarty K.Test Scheduling for Core-based Systems Using Mixed-integer Linear Programming[J].IEEE Trans.CAD,2000,19(10):1163-1174.

[4]雷加,方剛.一種基于遺傳算法的SoC測試調度方法[J].儀器儀表學報,2007,28(4):15-17.

[5]Garey M R,Johnson D S.Computers and Intractability-a Guide to the Theory of NP-completeness[M].San Francisco:W.H.Freeman and company,1980:221-281.

[6]Papachristou N C.An ILP Formulation to Optimize Test Access Mechanism in System-on-chip Testing[C]∥Proc.Int.Test conf,2000:902-910.

[7]鄧立寶,俞洋,彭喜元.一種靈活TAM總線分配的SoC測試調度方法[J].儀器儀表學報，2011,32(6):1238-1240.

[8]Murata H,Fujiyoshi K,Nakatake S,et al.VLSI Module Placement Based on Rectangle-packing by the Sequence-pair[C]∥IEEE Trans.on Computer-Aided Design,1996:1518-1524.

[9]張旺,王黎莉,伍洋.基于遺傳算法的陣列天線綜合及分析[J].無線電通信技術,2011,37(4):28-30.

[10]周磊,李大鵬,朱峰.基于遺傳算法的多偵查傳感器目標優化分配[J].無線電工程,2012,42(6):55-57.

[11]談敏,蔡鈞.基于改進遺傳算法的雙頻濾波器自動設計[J].無線電工程,2012,42(10):48-50.

[12]高朝暉,岳群彬,李偉.遺傳算法在成像衛星計劃編制中的應用[J].無線電工程,2013,43(12):37-40,60.

[13]王小平,曹立明.遺傳算法—理論、應用與軟件實現[M].西安：西安交通大學出版社,2002.

An Improved Test Scheduling Method of SoC Based on Genetic Algorithm

LIU Wei ,LI Bin

(The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China)

Abstract：This paper proposes an improved SoC test scheduling method based on genetic algorithm,which can efficiently optimize the division of testing bus,reasonably schedule each core to realize parallel test,and efficiently shorten the test time of core.Representing feasible solution of test scheduling with population,based on “survival of the fitness”,and beginning with the initial population,this algorithm evolves by generation to produce approximation solution.Utilizing international reference circuit provided by International Test Conference 2002 (ITC’02),we execute the test scheduling experiment.And the results suggest that this algorithm be superior to conventional integer linear programming (ILP) algorithm and conventional genetic algorithm.

Key words：genetic algorithm; test scheduling; optimization test

中圖分類號：TP18

文獻標識碼：A

文章編號：1003-3114(2016)02-37-4

作者簡介：劉偉(1989—)，男，碩士研究生,主要研究方向：數字集成電路設計。李斌(1972—)，男，研究員,主要研究方向：集成電路設計。

基金項目：核高基重大專項(2009ZX01031-001-007)

收稿日期：2015-11-10

doi:10.3969/j.issn.1003-3114.2016.02.09

引用格式：劉偉，李斌.一種改進的基于遺傳算法的測試調度方法[J].無線電通信技術,2016,42(2):37-40.