朱愛軍，李　智，朱望純，許川佩

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

0　引言

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

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

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

1　差分進化算法

差分進化算法采用遺傳算法類似的形式[7]，原理也相似，它包括交叉，選擇和變異。標準遺傳算法中的選擇策略一般采用輪盤賭，而差分進化算法算法中采用錦標賽選擇策略；對于交叉操作來說，差分進化算法大體上和遺傳算法類似，但對于變異操作來說，差分進化算法采用了完全不同的策略：利用兩個不同個體之間的差分向量進行縮放，從而實現(xiàn)對個體的擾動變異，這可以彌補遺傳算法中變異方式的缺點。

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

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

(1)

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

(1)初始種群的獲得：一般來說，進化計算中初始種群是通過隨機獲得，差分進化也不例外。初始種群

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

則：

(2)

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

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

r1≠r2≠r3≠i

(3)

該差分策略也稱為DE/rand/1/bin，它是目前應用最廣的差分策略之一，因為其在保持群體多樣性方面有較強的優(yōu)勢

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

(4)

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

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

(5)

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

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

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

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

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

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

3．1算法描述

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

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

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

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

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

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

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

Step(7)：對NP個父種群個體，如果子種群的當前個體Pateto 支配父種群相應個體，則用子種群的當前個體代替父種群相應個體，否則保持不變。

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

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

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

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

定義2：每一個個體定義為一個可行解，即

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

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

3．3目標函數(shù)……

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

(6)

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

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

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

(7)

式中，NTSVi表示第i條封裝掃描鏈使用TSV的數(shù)目；k∈[1，NP]；i∈[1，w]。

NTSVi的計算如式(8)：

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

(8)

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

4　試驗結(jié)果

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

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

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

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

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

表1p22810IP核Module5實驗結(jié)果，w=2

表2　p34392 IP核 Module 2 實驗結(jié)果，w=2

5　結(jié)論

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

參考文獻：

[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掃描鏈平衡算法．儀器儀表學報，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]朱愛軍，李智，許川佩，等．基于Biogeography的SoC測試Wrapper掃描鏈設(shè)計算法．儀器儀表學報，2012，33(12)：2774-2780．

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

[8]潘明，曾春華．基于IP核復用技術(shù)的CAN總線SOPC設(shè)計．儀表技術(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．