一種改進的基于遺傳算法的測試調(diào)度方法

劉　偉，李　斌

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

?

一種改進的基于遺傳算法的測試調(diào)度方法

劉偉，李斌

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

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

關(guān)鍵詞：遺傳算法；SoC測試；測試調(diào)度

0引言

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

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

1SoC測試優(yōu)化問題劃分

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

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

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

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

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

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

2SoC 的測試調(diào)度

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

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

圖1　平面規(guī)劃問題示意圖

3用遺傳算法解決SoC的測試調(diào)度問題

3.1序列對結(jié)構(gòu)

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

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

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

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

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

圖2　序列對網(wǎng)格結(jié)構(gòu)

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

圖3　水平連接圖Gh

圖4　垂直連接圖Gv

3.2遺傳算法

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

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

圖5　遺傳算法流程圖

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

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

② 設(shè)置Gen=0,隨機產(chǎn)生可能解的初始種群；

③ 計算每個解的適應(yīng)度C；

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

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

⑥ 計算當前種群的解，選出最優(yōu)方案；

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

⑧ 得出最優(yōu)解；

⑨ 結(jié)束。

對于交叉組合操作，選擇2個序列對，隨機選擇一個位置l(1≤l≤Nc)，交換2個序列對T+中l(wèi)位置的IP核和對應(yīng)T-位置的IP核。例如，在序列對Ⅰ的T+中，l位置對應(yīng)的IP核為P，在序列對Ⅱ中l(wèi)位置對應(yīng)的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+中隨機選擇一個位置插入。

⑤ 改變矩形的寬和高。

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

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

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

② 設(shè)置Gen=0,隨機產(chǎn)生可能解的初始種群；

③ 計算每個解的適應(yīng)度C；

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

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

⑥ 計算當前種群的解，選出最優(yōu)方案；

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

⑧ 得出最優(yōu)解；

⑨ 結(jié)束。

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

4實驗結(jié)果

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

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

5結(jié)束語

通過研究Wrapper/TAM組合優(yōu)化算法，提出了一種改進的遺傳算法解決SoC的測試調(diào)度問題。測試調(diào)度問題被映射成平面規(guī)劃問題，并通過序列對表示，然后用遺傳算法尋找最優(yōu)解。實驗結(jié)果表明，算法的測試周期比ILP算法和傳統(tǒng)遺傳算法的測試周期要少。所以，此改進的遺傳算法在減少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測試調(diào)度方法[J].儀器儀表學(xué)報,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測試調(diào)度方法[J].儀器儀表學(xué)報，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].無線電通信技術(shù),2011,37(4):28-30.

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

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

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

[13]王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社,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—)，男，碩士研究生,主要研究方向：數(shù)字集成電路設(shè)計。李斌(1972—)，男，研究員,主要研究方向：集成電路設(shè)計。

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

收稿日期：2015-11-10

doi:10.3969/j.issn.1003-3114.2016.02.09

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