基于多目標(biāo)差分進(jìn)化的測(cè)試封裝掃描鏈設(shè)計(jì)

朱愛(ài)軍，李　智，朱望純，許川佩

(1．桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院，廣西桂林　541004；2．西安電子科技大學(xué)機(jī)電工程學(xué)院，陜西西安　710071)

0　引言

差分進(jìn)化算法由R．Storn[1]在1997年提出的，由于其原理簡(jiǎn)明，控制參數(shù)較少，使用方便，因此在各個(gè)領(lǐng)域得到了廣泛的應(yīng)用。封裝掃描鏈的優(yōu)化設(shè)計(jì)，經(jīng)典的方法是IYENGAR V提出的BFD(Best Fit Decreasing)方法[2]，雖然該方法快速簡(jiǎn)捷，但是它只有局部?jī)?yōu)化的能力，并且它是針對(duì)二維SoC，并沒(méi)有考慮TSV的使用。文獻(xiàn)[3]提出了MVA(Mean Value Approximation)方法來(lái)改善該方法；文獻(xiàn)[4]提出了MVAR(Mean-Value Allowance Residue)方法，但是余量的選擇針對(duì)不同的IP核變化較大；文獻(xiàn)[5]提出了BBO方法，不過(guò)復(fù)雜度也相應(yīng)提高了。以上幾種方法都是針對(duì)二維封裝掃描鏈設(shè)計(jì)的，且沒(méi)有對(duì)測(cè)試時(shí)間與使用TSV資源使用之間的平衡進(jìn)行考慮。

隨著近年來(lái)3D(Three-Dimension)集成電路出現(xiàn)，以及基于嵌入式IP核的設(shè)計(jì)越來(lái)越有可能變成3D集成電路的設(shè)計(jì)風(fēng)格。3D 集成電路多層芯片間采用硅直通(Through Silicon Vias，TSV)技術(shù)，采用垂直的連線(xiàn)方式代替早期的邊緣走線(xiàn)方式，使得3D 集成電路的內(nèi)部連線(xiàn)大大縮短，從而降低了傳輸功耗和傳輸延時(shí)，進(jìn)一步加大了集成芯片的封裝密度。因此迫切需要研究三維封裝掃描鏈設(shè)計(jì)優(yōu)化問(wèn)題。

文中采用群體智能的多目標(biāo)差分進(jìn)化方法，對(duì)三維封裝掃描鏈的設(shè)計(jì)進(jìn)行優(yōu)化。

1　差分進(jìn)化算法

差分進(jìn)化算法采用遺傳算法類(lèi)似的形式[7]，原理也相似，它包括交叉，選擇和變異。標(biāo)準(zhǔn)遺傳算法中的選擇策略一般采用輪盤(pán)賭，而差分進(jìn)化算法算法中采用錦標(biāo)賽選擇策略；對(duì)于交叉操作來(lái)說(shuō)，差分進(jìn)化算法大體上和遺傳算法類(lèi)似，但對(duì)于變異操作來(lái)說(shuō)，差分進(jìn)化算法采用了完全不同的策略：利用兩個(gè)不同個(gè)體之間的差分向量進(jìn)行縮放，從而實(shí)現(xiàn)對(duì)個(gè)體的擾動(dòng)變異，這可以彌補(bǔ)遺傳算法中變異方式的缺點(diǎn)。

一般來(lái)說(shuō)，優(yōu)化問(wèn)題分為最大化和最小化問(wèn)題兩類(lèi)，而最大化問(wèn)題可以轉(zhuǎn)化為最小化問(wèn)題。不失一般性，這里只考慮最小化問(wèn)題：

minf(x1，x2，x3，…，xd)

(1)

差分進(jìn)化算法一般從一個(gè)初始化的種群開(kāi)始，經(jīng)過(guò)變異操作、交叉操作和選擇操作完成當(dāng)前代的操作，直到最大迭代數(shù)進(jìn)化才結(jié)束，得到最優(yōu)解，以下詳細(xì)介紹各個(gè)部分：

(1)初始種群的獲得：一般來(lái)說(shuō)，進(jìn)化計(jì)算中初始種群是通過(guò)隨機(jī)獲得，差分進(jìn)化也不例外。初始種群

R={X1，X2，…，Xk，…，XNP}

則：

(2)

(2)變異操作的實(shí)現(xiàn)：在大多數(shù)的進(jìn)化算法中，一般采用隨機(jī)化產(chǎn)生一個(gè)可行域中的一個(gè)個(gè)體來(lái)實(shí)現(xiàn)變異操作；而在差分進(jìn)化算法中采用差分策略產(chǎn)生個(gè)體的變異。在標(biāo)準(zhǔn)的差分策略中，首先隨機(jī)選擇3個(gè)不相同的個(gè)體，將其中2個(gè)個(gè)體的向量差采取縮放操作后與第3個(gè)個(gè)體進(jìn)行向量合成，如下

Vi(g+1)=Xr1(g)+F·[Xr2(g)-Xr3(g)]

r1≠r2≠r3≠i

(3)

該差分策略也稱(chēng)為DE/rand/1/bin，它是目前應(yīng)用最廣的差分策略之一，因?yàn)槠湓诒３秩后w多樣性方面有較強(qiáng)的優(yōu)勢(shì)

(3)交叉操作的實(shí)現(xiàn)：對(duì)于第g代種群{X1(g)，X2(g)，…，Xk(g)，…，XNP(g)}和它的變異體Vi(g+1)進(jìn)行個(gè)體之間的交叉，具體如下：

(4)

式中：CR表示交叉概率；jrand為1到d之間產(chǎn)生的隨機(jī)整數(shù)。

(4)選擇操作的實(shí)現(xiàn)：差分進(jìn)化采用貪婪算法的策略對(duì)下一代種群的個(gè)體進(jìn)行選擇，即交叉操作后的個(gè)體如果比原來(lái)的個(gè)體更好，則選取交叉操作后的個(gè)體，否則保持原來(lái)的個(gè)體不變

(5)

(5)非可行域解的操作：在差分進(jìn)化過(guò)程中，為了保證解的有效性，必須判斷每個(gè)個(gè)體的每一個(gè)基因是否在規(guī)定的范圍內(nèi)。如果當(dāng)前個(gè)體存在某個(gè)基因不在可行域內(nèi)，則用類(lèi)似產(chǎn)生初始種群個(gè)體的方法，隨機(jī)產(chǎn)生一個(gè)新個(gè)體來(lái)代替該個(gè)體。

3　基于多目標(biāo)差分進(jìn)化算法的封裝掃描鏈設(shè)計(jì)

多目標(biāo)優(yōu)化問(wèn)題一般有2個(gè)以上的目標(biāo)函數(shù)，通常有最大化和最小化問(wèn)題兩種，文中為最小化問(wèn)題。多目標(biāo)差分是在單目標(biāo)差分的基礎(chǔ)上改變而成，主要區(qū)別在選擇操作上有所不同：?jiǎn)文繕?biāo)差分中交叉操作后的個(gè)體如果比原來(lái)的個(gè)體更好，則選取交叉操作后的個(gè)體，否則保持原來(lái)的個(gè)體不變；而多目標(biāo)差分中交叉操作后的個(gè)體Pateto 支配原來(lái)的個(gè)體，則選取交叉操作后的個(gè)體，否則保持原來(lái)的個(gè)體不變。Pateto 支配定義如下：

定義1：(Pateto 支配)。一個(gè)可行解xsPateto支配另一個(gè)可行解xt，即xs

(1)在全體目標(biāo)函數(shù)中，可行解xs不比可行解xt差，即對(duì)于任意的整數(shù)i，i∈[1，k]，fi(xs)≤fi(xt)，其中k為目標(biāo)函數(shù)的個(gè)數(shù)；

(2)在全體目標(biāo)函數(shù)中，至少存在一個(gè)目標(biāo)函數(shù)，使得可行解xs嚴(yán)格比可行解xt好，即：?整數(shù)i∈[1，k]，fi(xs)

3．1算法描述

基于多目標(biāo)差分進(jìn)化的封裝掃描鏈設(shè)計(jì)算法描述：

Step(1)：根據(jù)IP核的內(nèi)部掃描鏈條數(shù)n確定解空間的維數(shù)d，根據(jù)需要設(shè)計(jì)的封裝掃描鏈的條數(shù)確定w的值，設(shè)置縮放因子F的值，設(shè)置交叉概率Pc的值，設(shè)置種群規(guī)模NP的值，設(shè)置最大迭代代數(shù)MaxG的值。

Step(2)：在可行域內(nèi)隨機(jī)生成一種群規(guī)模為NP的父初始種群，利用式(6)和式(7)，計(jì)算初始種群中每一個(gè)個(gè)體的目標(biāo)函數(shù)值。

Step(3)：根據(jù)利用公式(3)產(chǎn)生變異體種群，其種群規(guī)模為NP.

Step(4)：對(duì)變異體種群中每一個(gè)個(gè)體的每一個(gè)基因進(jìn)行邊界檢測(cè)，如果小于1則將其值修改為1，如果大于w，則將其值修改為w.

Step(5)：對(duì)NP個(gè)個(gè)體的每一個(gè)基因，產(chǎn)生隨機(jī)數(shù)rand(0，1)，如果rand(0，1)大于交叉概率Pc，則子種群當(dāng)前個(gè)體的該基因值選取父種群相應(yīng)個(gè)體對(duì)應(yīng)的基因值，否則子種群當(dāng)前個(gè)體的該基因值選取變異種群相應(yīng)個(gè)體對(duì)應(yīng)的基因值。

Step(6)：根據(jù)式(6)和式(7)計(jì)算子種群NP個(gè)個(gè)體的目標(biāo)函數(shù)值。

Step(7)：對(duì)NP個(gè)父種群個(gè)體，如果子種群的當(dāng)前個(gè)體Pateto 支配父種群相應(yīng)個(gè)體，則用子種群的當(dāng)前個(gè)體代替父種群相應(yīng)個(gè)體，否則保持不變。

Step(8)：由Step(7)得到新一代的種群：父種群，根據(jù)式(6)和式(7)計(jì)算父種群NP個(gè)個(gè)體的目標(biāo)函數(shù)值。

Step(9)：迭代代數(shù)到達(dá)MaxG否，沒(méi)有達(dá)到則轉(zhuǎn)Step(3)。

Step(10)：將父種群NP個(gè)個(gè)體按照成本函數(shù)值非支配排序，得到Pateto最優(yōu)解。

3．2整數(shù)向量編碼

定義2：每一個(gè)個(gè)體定義為一個(gè)可行解，即

式中：i=1，2，…NP；d為解空間的維數(shù)；NP為群體規(guī)模。

文中采用整數(shù)向量編碼方案，具體見(jiàn)文獻(xiàn)[6]

3．3目標(biāo)函數(shù)……

定義3：ObjectiveF1目標(biāo)函數(shù)1，使得封裝掃描鏈中的最長(zhǎng)掃描鏈最短，從而減少測(cè)試時(shí)間，定義為：

(6)

式中：L(Pi)表示第i條封裝掃描鏈的長(zhǎng)度；L(Si)表示第j條內(nèi)部掃描鏈的長(zhǎng)度；k∈[1，NP]。

目標(biāo)函數(shù)1的值越小，表示適應(yīng)度越大，該待選可行解越好。

定義4：ObjectiveF2目標(biāo)函數(shù)2，使得總的使用TSV數(shù)量最少，定義為：

(7)

式中，NTSVi表示第i條封裝掃描鏈?zhǔn)褂肨SV的數(shù)目；k∈[1，NP]；i∈[1，w]。

NTSVi的計(jì)算如式(8)：

NTSVi=2×Max1≤j≤x(Layij)

(8)

式中：Layij為第i條封裝掃描中第j條內(nèi)部掃描鏈所在的層數(shù)；x為第i條封裝掃描中內(nèi)部掃描鏈的條數(shù)，封裝掃描鏈的起始處都是最底層，假設(shè)最底層的所在層為第0層。

4　試驗(yàn)結(jié)果

為了比較各種方法的性能，驗(yàn)證該方法的有效性，文中采用國(guó)際標(biāo)準(zhǔn)ITC’02 benchmarks[5]。由于大多數(shù)的IP核內(nèi)部掃描鏈的長(zhǎng)度都比較均衡，因此難以比較那種方法更好。為了證明該方法的有效性，文中在ITC’02 benchmarks中選取兩個(gè)不平衡IP核 (p34392 IP Module 2 和p22810 IP Module 5)。由于ITC’02 benchmarks中不包含內(nèi)部掃描鏈所處的層信息，因此文中假設(shè)IP核的各個(gè)內(nèi)部掃描鏈隨機(jī)分布在三層上，最底層為第0層，依次往上遞增，每條封裝掃描鏈的起始處都在第0層。

多目標(biāo)差分優(yōu)化系統(tǒng)參數(shù)設(shè)置：群體規(guī)模NP為 50；最大迭代代數(shù)MaxG為500；縮放因子F為0．5；交叉概率Pc為0．2；根據(jù)封裝掃描鏈的條數(shù)設(shè)置w；根據(jù)IP核中相應(yīng)的內(nèi)部掃描鏈的條數(shù)設(shè)置解空間的維數(shù)d；w為封裝掃描鏈的條數(shù)，表1當(dāng)中，第1列M表示所采用的多目標(biāo)方法，為了驗(yàn)證該方法MODE (Muti-Objective Differential Evolution )的有效性，文中還采用了多目標(biāo)算法中廣泛使用的NSGAII(Nondominated Sorting Genetic Algorithm II )[9]方法進(jìn)行對(duì)比。NSGAII的使用參數(shù)為：最大迭代代數(shù)為500，每一代的群體規(guī)模為50，子代的交叉概率為0．9。第二列為各種方法獲得的Pateto 最優(yōu)解，第三列和第四列為各種方法獲得的Pateto前沿，其中L表示最長(zhǎng)封裝掃描鏈的長(zhǎng)度，Ntsv表示使用的TSV數(shù)目。為了便于對(duì)比，在所有的方法中，使得相同內(nèi)部掃描鏈所處的層均相同，以下實(shí)驗(yàn)參數(shù)都采用相同的設(shè)置。

從表1，可得當(dāng)使用相同的TSV個(gè)數(shù)時(shí)，MODE方法能夠得到更短的最長(zhǎng)封裝掃描鏈。

從表2，同樣可得當(dāng)使用相同的TSV個(gè)數(shù)時(shí)，MODE方法能夠得到更短的最長(zhǎng)封裝掃描鏈。

……為了比較當(dāng)w取不同值的時(shí)候，兩種方法的整體優(yōu)劣，分別取w=3，…，16，同樣得到使用相同的TSV個(gè)數(shù)時(shí)MODE方法能夠得到更短的最長(zhǎng)封裝掃描鏈。

表1p22810IP核Module5實(shí)驗(yàn)結(jié)果，w=2

表2　p34392 IP核 Module 2 實(shí)驗(yàn)結(jié)果，w=2

5　結(jié)論

文中提出了一種基于多目標(biāo)差分進(jìn)化的方法，用來(lái)縮短最長(zhǎng)封裝掃描鏈的長(zhǎng)度和減少使用TSV數(shù)目，從而縮短IP核的測(cè)試時(shí)間和減少使用TSV使用資源。實(shí)驗(yàn)結(jié)果表明該方法總體上能夠獲得更短的封裝掃描鏈和更少的TSV資源。

參考文獻(xiàn)：

[1]STORN R，PRICE K.Differential Evolution—A Simple and Efficient Heuristic for Global optimization over Continuous Spaces．Journal of Global ptimization，1997，11 (4 )：341-359．

[2]IYENGAR V，CHAKRABARTY K，MARINISSEN E J．Test Wrapper and test access mechanism co-optimization for system-on-chip．Journal of Electronic testing：Theory and Application，2002，18(2)：213-230．

[3]NIU D H，WANG H，YANG S Y，et al．Re-optimization algorithm for SoC Wrapper-chain balance using mean-value approximation．Tsinghua Science and Technology，2007，12( S1) ：61-66．

[4]俞洋，陳葉富，彭宇．基于平均值余量的Wrapper掃描鏈平衡算法．儀器儀表學(xué)報(bào)，2011，32 (10)：2290-2296．

[5]MARINISSEN E J，IYENGAR V，CHAKRABARTY K．A set of benchmarks for modular testing of SOCs．International Test Conference，2002：519-528．

[6]朱愛(ài)軍，李智，許川佩，等．基于Biogeography的SoC測(cè)試Wrapper掃描鏈設(shè)計(jì)算法．儀器儀表學(xué)報(bào)，2012，33(12)：2774-2780．

[7]楊啟文，蔡亮，薛云燦．差分進(jìn)化算法綜述．模式識(shí)別與人工智能.2008，21(4)：506-513．

[8]潘明，曾春華．基于IP核復(fù)用技術(shù)的CAN總線(xiàn)SOPC設(shè)計(jì)．儀表技術(shù)與傳感器，2011(5)：55-58

[9]DEB K，PRATAP A，AGARWAL S，et al．A fast and elitist multi-objective genetic algorithm NSGA-II．IEEE Transactions on Evolutionary Computation，2002，6(2)：182-197．