劉　偉，李　斌

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

?

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

劉偉，李斌

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

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

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

0引言

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

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

1SoC測(cè)試優(yōu)化問(wèn)題劃分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3　水平連接圖Gh

圖4　垂直連接圖Gv

3.2遺傳算法

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

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

圖5　遺傳算法流程圖

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

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

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

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

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

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

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

⑦Gen=Gen+1，如果Gen<1 000，進(jìn)入第④步；

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

⑨ 結(jié)束。

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

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

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

② 在T-中隨機(jī)選擇2個(gè)IP核，交換它們的位置；

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

④ 隨機(jī)選擇一個(gè)IP核，在T+中隨機(jī)選擇一個(gè)位置插入。

⑤ 改變矩形的寬和高。

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

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

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

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

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

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

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

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

⑦Gen=Gen+1，如果Gen<1 000，進(jìn)入第④步；

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

⑨ 結(jié)束。

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

4實(shí)驗(yàn)結(jié)果

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

表1　基準(zhǔn)電路OTC’02(D695)上的實(shí)驗(yàn)結(jié)果

5結(jié)束語(yǔ)

通過(guò)研究Wrapper/TAM組合優(yōu)化算法，提出了一種改進(jìn)的遺傳算法解決SoC的測(cè)試調(diào)度問(wèn)題。測(cè)試調(diào)度問(wèn)題被映射成平面規(guī)劃問(wèn)題，并通過(guò)序列對(duì)表示，然后用遺傳算法尋找最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，算法的測(cè)試周期比ILP算法和傳統(tǒng)遺傳算法的測(cè)試周期要少。所以，此改進(jìn)的遺傳算法在減少SoC測(cè)試時(shí)間上是有效的。

參考文獻(xiàn)

[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測(cè)試調(diào)度方法[J].儀器儀表學(xué)報(bào),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測(cè)試調(diào)度方法[J].儀器儀表學(xué)報(bào)，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].無(wú)線電通信技術(shù),2011,37(4):28-30.

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

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

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

[13]王小平,曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(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

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

收稿日期：2015-11-10

doi:10.3969/j.issn.1003-3114.2016.02.09

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