基于云模型進(jìn)化算法的硅通孔數(shù)量受約束的3D NoC測(cè)試規(guī)劃研究

許川佩 陳家棟萬(wàn)春霆

(桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院 桂林 541004)

基于云模型進(jìn)化算法的硅通孔數(shù)量受約束的3D NoC測(cè)試規(guī)劃研究

許川佩 陳家棟*萬(wàn)春霆

(桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院 桂林 541004)

針對(duì)硅通孔(TSV)價(jià)格昂貴、占用芯片面積大等問(wèn)題，該文采用基于云模型的進(jìn)化算法對(duì)TSV數(shù)量受約束的3維片上網(wǎng)絡(luò)(3D NoC)進(jìn)行測(cè)試規(guī)劃研究，以?xún)?yōu)化測(cè)試時(shí)間，并探討TSV的分配對(duì)3D NoC測(cè)試的影響，進(jìn)一步優(yōu)化3D NoC在測(cè)試模式下的TSV數(shù)量。該方法將基于云模型的進(jìn)化算法、小生境技術(shù)以及遺傳算法的雜交技術(shù)結(jié)合起來(lái)，有效運(yùn)用遺傳、優(yōu)勝劣汰以及保持群落的多樣性等理念，以提高算法的尋優(yōu)速度和尋優(yōu)精度。研究結(jié)果表明，該算法既能有效避免陷入局部最優(yōu)解，又能提高全局尋優(yōu)能力和收斂速度，縮短了測(cè)試時(shí)間，并且優(yōu)化了3D NoC的測(cè)試TSV數(shù)量，提高了TSV的利用率。

3維片上網(wǎng)絡(luò)；硅通孔；云模型；進(jìn)化算法

1 引言

隨著集成電路技術(shù)的發(fā)展，3維片上網(wǎng)絡(luò)(Three-Dimensional Network-on-Chip, 3D NoC)的思想逐步出現(xiàn)在集成電路設(shè)計(jì)中。3D NoC通過(guò)硅通孔(Through-Silicon-Via, TSV)技術(shù)將各層2維結(jié)構(gòu)芯片互連起來(lái)，其優(yōu)點(diǎn)表現(xiàn)為：一是縮短了全局互連；二是降低了延遲，提高了系統(tǒng)性能；三是由于縮短了連接線(xiàn)的長(zhǎng)度而降低了功耗；四是增加了封裝密度，減小了芯片面積[1]。然而，由于TSV占用了芯片大量區(qū)域(特別是為T(mén)SV需要而留出的“禁用區(qū)”)，使得芯片上的IP核數(shù)量大大減少，另外，生產(chǎn)TSV的開(kāi)銷(xiāo)很大[1]，這些因素使得設(shè)計(jì)者在設(shè)計(jì)3D NoC時(shí)需要考慮TSV數(shù)量問(wèn)題，而對(duì)于數(shù)量受約束的3D NoC測(cè)試，需要有針對(duì)性的測(cè)試方案，從而提高TSV的利用率，優(yōu)化測(cè)試時(shí)間。

目前對(duì)于3維集成電路的測(cè)試規(guī)劃研究，文獻(xiàn)[2]提出了在各層均衡分布IP核，并對(duì)IP核進(jìn)行測(cè)試調(diào)度的方法，減小了芯片的測(cè)試時(shí)間；文獻(xiàn)[3]提出了在TSV數(shù)量受約束條件下，如何減少3D SoC中分立電路測(cè)試時(shí)間的方法，但不能保證優(yōu)化全局的測(cè)試時(shí)間；文獻(xiàn)[4]研究了在TSV數(shù)量一定的情況下減少3D SoCs測(cè)試時(shí)間的方法，以及提出優(yōu)化TSV數(shù)量的方法。國(guó)內(nèi)外學(xué)者針對(duì)NoC的測(cè)試研究主要集中在2D NoC，例如文獻(xiàn)[5]探討了NoC重用對(duì)系統(tǒng)測(cè)試的影響，并提出了搶占式和非搶占式測(cè)試調(diào)度的測(cè)試方法，但該方法缺乏快速有效的規(guī)劃算法；文獻(xiàn)[6]在文獻(xiàn)[5]的研究基礎(chǔ)上，將NoC測(cè)試規(guī)劃與遺傳算法結(jié)合起來(lái)，從而優(yōu)化了測(cè)試時(shí)間。

由于3D NoC的測(cè)試規(guī)劃問(wèn)題是一個(gè)NP難問(wèn)題，本文基于高精度尋優(yōu)的云模型進(jìn)化算法，研究3D NoC 測(cè)試資源(I/O端口，TSV)分配策略，以提高資源利用率，優(yōu)化測(cè)試時(shí)間，并探討TSV數(shù)量及其在各層間的分配對(duì)3D NoC測(cè)試的影響。

2 3D NoC結(jié)構(gòu)

3D NoC結(jié)構(gòu)主要有3D mesh 結(jié)構(gòu)，蝶形胖樹(shù)結(jié)構(gòu)，XnoTs結(jié)構(gòu)等。目前學(xué)者主要研究的是3D mesh 結(jié)構(gòu)。典型的3D mesh結(jié)構(gòu)NoC如圖1(a)所示，相鄰兩層對(duì)應(yīng)的上、下兩個(gè)路由節(jié)點(diǎn)均由TSV連接起來(lái)。

3D NoC的一個(gè)基本單元如圖1(b)所示。其中R表示路由節(jié)點(diǎn)(Router)，每個(gè)路由節(jié)點(diǎn)有7對(duì)I/O端口，其中一對(duì)端口與本地芯核(core)相連，其余6對(duì)分別與相鄰的東(E)，南(S)，西(W)，北(N)，上(U)以及下(D)6個(gè)方向的路由節(jié)點(diǎn)相連，垂直方向U和D的互連線(xiàn)由TSV構(gòu)成，U和D方向均包含up-to-down TSV和down-to-up TSV[7]，為了便于研究，文中稱(chēng)一個(gè)垂直方向含有1束TSV?；ミB的兩個(gè)節(jié)點(diǎn)之間的通信可以采用全雙工的通信方式。core表示一個(gè)資源節(jié)點(diǎn)，可以是處理器內(nèi)核、存儲(chǔ)器、FPGA或IP核等。NI表示網(wǎng)絡(luò)接口，是路由節(jié)點(diǎn)與資源節(jié)點(diǎn)的通信接口。

很明顯，TSV越多，各層資源節(jié)點(diǎn)之間的通信就越便捷。然而，由于芯片生產(chǎn)開(kāi)銷(xiāo)以及芯片面積的限制，3D NoC在設(shè)計(jì)和使用時(shí)需要考慮TSV數(shù)量問(wèn)題。本文在TSV數(shù)量受約束的前提下對(duì)3D NoC進(jìn)行測(cè)試規(guī)劃研究。

圖1 3D mesh 結(jié)構(gòu)NoC及其基本單元

3 TSV數(shù)量受約束的3D NoC測(cè)試規(guī)劃

3.1 NoC測(cè)試規(guī)劃

為減少硬件開(kāi)銷(xiāo)，NoC測(cè)試采用重用片上網(wǎng)絡(luò)的測(cè)試訪問(wèn)機(jī)制[6,8,9]，即復(fù)用片上網(wǎng)絡(luò)的路由節(jié)點(diǎn)和通道(channel)等資源，實(shí)施并行測(cè)試以提高測(cè)試效率。在測(cè)試core時(shí)，測(cè)試矢量由輸入端口送入網(wǎng)絡(luò)，按一定的路由算法到達(dá)core，生成的測(cè)試響應(yīng)以同樣的路由算法到達(dá)輸出端，由外部的測(cè)試響應(yīng)接收并分析，完成一個(gè)核的測(cè)試。

本文采用非搶占式的測(cè)試策略，給每個(gè)測(cè)試核分配一條測(cè)試路徑，包括輸入端口、輸出端口，以及相應(yīng)的通道，一旦某測(cè)試核的測(cè)試路徑確定之后，該路徑上的所有資源(輸入/輸出端口，通道)將預(yù)留給該測(cè)試核，其他核的測(cè)試矢量以及測(cè)試響應(yīng)不得搶占，直到該核測(cè)試完畢為止。

TSV數(shù)量受約束的3D NoC測(cè)試時(shí)，測(cè)試數(shù)據(jù)需要經(jīng)過(guò)特定的I/O端口以及特定的TSV才能完成芯核的測(cè)試，因此，本文研究的測(cè)試規(guī)劃問(wèn)題可描述為：給定NC個(gè)待測(cè)核core, NIO對(duì)I/O端口，各層的TSV數(shù)量，在確定的路由算法下，如何將輸入/輸出端口，以及TSV合理有效地分配給各個(gè)core，確定這些core的測(cè)試路徑，并且在功耗允許的條件下，無(wú)沖突地調(diào)度各個(gè)待測(cè)核的測(cè)試順序，使整體測(cè)試時(shí)間最小。

3.2 路由算法及路徑?jīng)_突

在測(cè)試過(guò)程中，采用XYZ路由算法，數(shù)據(jù)包由源節(jié)點(diǎn)沿X方向傳輸，到達(dá)與目標(biāo)節(jié)點(diǎn)x坐標(biāo)相同的路由節(jié)點(diǎn)后，轉(zhuǎn)向Y方向進(jìn)行傳輸，到達(dá)與目標(biāo)節(jié)點(diǎn)y坐標(biāo)相同的路由節(jié)點(diǎn)后轉(zhuǎn)向Z方向傳輸，直至目標(biāo)節(jié)點(diǎn)。

根據(jù)已制定的測(cè)試策略，一旦給某個(gè)core分配了輸入/輸出端口以及TSV等資源，那么按照XYZ路由算法，該core的測(cè)試路徑便是確定的。由于多個(gè)core同時(shí)進(jìn)行測(cè)試，如果芯核測(cè)試順序調(diào)度不合理，測(cè)試路徑便有可能產(chǎn)生沖突，即兩個(gè)core的測(cè)試數(shù)據(jù)在某個(gè)路由節(jié)點(diǎn)處向相同路由節(jié)點(diǎn)進(jìn)行傳輸。

3.3 測(cè)試時(shí)間以及功耗約束

(1)測(cè)試時(shí)間 多對(duì)端口并行測(cè)試規(guī)劃如圖2所示，總測(cè)試時(shí)間取決于測(cè)試時(shí)間最長(zhǎng)的那對(duì)I/O端口。

總測(cè)試時(shí)間為

圖2 多對(duì)端口并行測(cè)試規(guī)劃圖

其中，Ti代表core i分配到第j對(duì)I/O端口上的測(cè)試時(shí)間，NC代表core的數(shù)量，Tkx(j)為第j對(duì)I/O端口上測(cè)試資源沖突或功耗過(guò)大時(shí)的空閑時(shí)間，NIO為I/O端口對(duì)數(shù)，單個(gè)核的測(cè)試時(shí)間Ti包括測(cè)試數(shù)據(jù)的傳輸時(shí)間以及測(cè)試所消耗的時(shí)間，即Ti=Ttr+Tte，而在核進(jìn)行測(cè)試的同時(shí)，其余數(shù)據(jù)包已相繼傳入網(wǎng)絡(luò)，因此數(shù)據(jù)傳輸所耗的時(shí)間主要是第1個(gè)測(cè)試數(shù)據(jù)包從輸入端口至測(cè)試核以及最后1個(gè)測(cè)試響應(yīng)數(shù)據(jù)包從測(cè)試核至輸出端口所耗的時(shí)間。

式中Tp(first), Tp(last)分別為第1個(gè)測(cè)試數(shù)據(jù)包和最后1個(gè)測(cè)試響應(yīng)數(shù)據(jù)包在兩個(gè)路由節(jié)點(diǎn)之間的傳輸時(shí)間，hopi和hopo分別代表數(shù)據(jù)包輸入以及輸出測(cè)試核所經(jīng)過(guò)的路由跳數(shù)。

Th為路由器處理數(shù)據(jù)包頭所耗的時(shí)間，Tr為確定路由的時(shí)間，Td為數(shù)據(jù)傳輸至下一路由節(jié)點(diǎn)所耗的時(shí)間。

通常，核的測(cè)試時(shí)間遠(yuǎn)大于數(shù)據(jù)包的傳輸時(shí)間，因此本文不考慮傳輸時(shí)間的影響。

(2)功耗約束 考慮到異構(gòu)NoC每層的功耗不同，因此有必要將功耗約束到每一層。對(duì)于每個(gè)時(shí)隙(time slot)，第 l層的功耗必須滿(mǎn)足:

單個(gè)核的功耗包含傳輸功耗和測(cè)試功耗，即P=np ·Pp+Pc，其中np是該核的數(shù)據(jù)包數(shù)量，Pc是該核的測(cè)試功耗，Pp是一個(gè)數(shù)據(jù)包通過(guò)路徑的傳輸功耗。

其中Pr代表數(shù)據(jù)包在一個(gè)路由器上的傳輸功耗，Pxy代表數(shù)據(jù)包在一條水平通道上的傳輸功耗，Ptv代表數(shù)據(jù)包在一條TSV上的傳輸功耗，Nr, Nch, Ntv分別代表數(shù)據(jù)包經(jīng)過(guò)的路由器數(shù)量，通道數(shù)量以及TSV數(shù)量，其中通道數(shù)量包含了TSV數(shù)量。

其中CL, T和σw分別表示負(fù)載電容(技術(shù)有關(guān)常數(shù))、時(shí)鐘周期以及開(kāi)關(guān)因子。變量nbff, nbgt, σff和σgt分別表示活性元件的數(shù)量(觸發(fā)器或者邏輯門(mén))及其通過(guò)的路由器上相應(yīng)的開(kāi)關(guān)因子[10]。

Pr, Pxy以及Ptv均為常數(shù)。采用文獻(xiàn)[10]的功耗模型，Pr=10, Pxy=2。由于互連TSV很短，比水平互連通道小兩個(gè)數(shù)量級(jí)，所以功耗遠(yuǎn)遠(yuǎn)小于水平通道的功耗，考慮到TSV的工藝與分布結(jié)構(gòu)還沒(méi)有統(tǒng)一，本文設(shè)定Ptv=1。

4 基于云模型進(jìn)化算法的測(cè)試規(guī)劃方法

3D NoC測(cè)試規(guī)劃屬于NP難問(wèn)題[11]，而基于云模型的進(jìn)化算法[12-14]是一種高精度尋優(yōu)的算法，將該算法與3D NoC測(cè)試結(jié)合起來(lái)，可以迅速而且準(zhǔn)確地找到最優(yōu)的資源(I/O端口，TSV)分配方案，從而提高TSV利用率，優(yōu)化測(cè)試時(shí)間。

4.1 算法的相關(guān)設(shè)計(jì)

假定NoC有L層，將底層稱(chēng)為第 0層, 其上各層按順序依次稱(chēng)為第 1層，第 2層……。核數(shù)量為第 l層的核數(shù)量，各層核的編號(hào)依次0, 1,…,-1。TSV數(shù)量其中為第 l層的TSV數(shù)量，各層TSV編號(hào)依次為0, 1,…,-1。設(shè)I/O端口對(duì)數(shù)為NIO，則I/O端口對(duì)的編號(hào)依次為0, 1,…,NIO-1。

本文以3層NoC為例來(lái)進(jìn)行說(shuō)明。

4.1.1 染色體 對(duì)于本文所研究的問(wèn)題，一條染色體就是完成一個(gè)待測(cè)核測(cè)試的一種資源(I/O端口，TSV)分配方案。設(shè)定染色體Ali=(G0, G1, G2, G3, G4)，其中G0～G4為染色體中的基因。G0所含信息為I/O端口編號(hào)，G1～G2依次為測(cè)試數(shù)據(jù)從輸入端口傳輸至core li先后經(jīng)過(guò)的各層TSV編號(hào)，G3～G4依次為測(cè)試數(shù)據(jù)從core li傳輸至輸出端口先后經(jīng)過(guò)的各層TSV編號(hào)。各基因在3D NoC中的映射如圖3所示。染色體所包含的信息為測(cè)試core li時(shí)測(cè)試數(shù)據(jù)所經(jīng)過(guò)的關(guān)鍵通道。例如染色體A26= (0, 0, 0, 3, 3)所含信息為測(cè)試第2層第6號(hào)芯核時(shí)，測(cè)試數(shù)據(jù)先后經(jīng)過(guò)的關(guān)鍵通道依次為輸入0→底層TSV0→第1層TSV0→core li→第1層TSV3→底層TSV3→輸出 0。需要注意的是，當(dāng)測(cè)試底層芯核時(shí)，測(cè)試數(shù)據(jù)不需要經(jīng)過(guò)任何TSV，此時(shí)G1～G4為無(wú)效基因，用‘X’來(lái)表示，染色體標(biāo)志為(G0,X,X,X,X)；當(dāng)測(cè)試第1層芯核時(shí)，測(cè)試數(shù)據(jù)不需要經(jīng)過(guò)第2層以上的TSV，此時(shí)G2和G3為無(wú)效基因，染色體標(biāo)志為(G0,G1,X,X,G4)。

圖3 染色體結(jié)構(gòu)映射圖

4.1.2 個(gè)體 個(gè)體為完成對(duì)所有待測(cè)核進(jìn)行測(cè)試的一種資源分配方案。一個(gè)個(gè)體有Nc條染色體，Nc為待測(cè)核的數(shù)量。例如，A00=(2,X,X,X,X), A10= (1,1,X,X,2),20= (0,0,0,3,3)構(gòu)成一個(gè)個(gè)體，該個(gè)體有3條染色體，代表NoC有3個(gè)待測(cè)核，分別分布在第0, 1, 2層，每條染色體所含的信息代表著一個(gè)待測(cè)核的測(cè)試路徑。

4.1.3 個(gè)體適應(yīng)度值 文中以完成對(duì)所有core進(jìn)行測(cè)試所需的時(shí)間作為個(gè)體的適應(yīng)度值，測(cè)試時(shí)間越小，該個(gè)體越優(yōu)秀。測(cè)試時(shí)間依據(jù)式(1)計(jì)算。在測(cè)試過(guò)程中，需要對(duì)分配在各I/O端口對(duì)上進(jìn)行測(cè)試的芯核進(jìn)行調(diào)度，盡量縮短測(cè)試時(shí)間。本文采用非搶占式的測(cè)試調(diào)度策略，測(cè)試調(diào)度的偽代碼如表1所示。

表1 測(cè)試調(diào)度的偽代碼

4.1.4 云模型 本文選用1維正態(tài)云模型C(Ex, En, He)實(shí)現(xiàn)進(jìn)化過(guò)程。期望Ex代表父代的優(yōu)良特性；熵En表示云模型中云滴距離期望值Ex的離散范圍；超熵He是熵的不確定度，反映了云模型中數(shù)值的凝聚程度。正態(tài)云模型更新云滴過(guò)程：

(1)生成期望值為En，方差為He的正態(tài)隨機(jī)數(shù)，

(2)以Ex為期望值，()2為方差生成正態(tài)隨機(jī)數(shù)x, x稱(chēng)為云滴；

更新個(gè)體時(shí)，Ex取個(gè)體的基因值，En代表基因在進(jìn)化過(guò)程中變異的范圍，En=e/c1，其中e為各基因取值范圍。當(dāng)Ex=G0時(shí)，e值為I/O端口對(duì)數(shù)；當(dāng)Ex=G1或G4時(shí)，e值為底層TSV數(shù)量；當(dāng)Ex=G2或G3時(shí)，e值為上層TSV數(shù)量。He代表了進(jìn)化過(guò)程中搜索尋優(yōu)的范圍，He=En/c2。c1, c2均為可控參數(shù)。在進(jìn)化過(guò)程中，出現(xiàn)跨代精英即更優(yōu)秀個(gè)體時(shí)，應(yīng)調(diào)節(jié)c1, c2使En和He減小，縮小搜索范圍，進(jìn)行局部求精；當(dāng)平凡代數(shù)(連續(xù)不出現(xiàn)跨代精英的代數(shù))達(dá)到一定值時(shí)，應(yīng)調(diào)節(jié)c1, c2使En和He增大，從而擴(kuò)大搜索范圍，進(jìn)行局部求變操作。

4.1.5 交叉變異 包括雜交、自交以及變異。雜交過(guò)程采用輪盤(pán)賭的方式選取2個(gè)個(gè)體，越優(yōu)秀的個(gè)體被選中的概率越大，個(gè)體的基因交換方式采用多點(diǎn)交換，同樣以輪盤(pán)賭的方式選擇需要交換的染色體，含有有效基因較多的染色體被選擇的概率較大，基因交換如圖4所示。自交過(guò)程是將一個(gè)個(gè)體中不同染色體的相同位置的有效基因進(jìn)行交叉互換。變異則是利用隨機(jī)函數(shù)更新個(gè)體中的某些有效基因。交叉變異后的個(gè)體需要檢驗(yàn)是否合格：個(gè)體中所有G0基因的值是否涵蓋了所有I/O端口編號(hào)值，若不是，則個(gè)體不合格，需重新進(jìn)行交叉變異。

4.2 算法設(shè)計(jì)

普通的云模型進(jìn)化算法一般只針對(duì)一個(gè)群落，從該群落中選取優(yōu)秀的種子進(jìn)行個(gè)體更新，當(dāng)連續(xù)n代沒(méi)有發(fā)現(xiàn)精英個(gè)體才進(jìn)行交叉變異操作，而且各種子個(gè)體間有血緣關(guān)系，進(jìn)化代數(shù)達(dá)到一定時(shí)，各個(gè)體的基因有很大相似度，最終導(dǎo)致算法尋優(yōu)速度慢、容易陷入局部最優(yōu)等情況。為了克服這些缺點(diǎn)，算法中設(shè)計(jì)了普通群落、雜交群落以及精英群落3個(gè)群落，群落的系統(tǒng)結(jié)構(gòu)如圖5所示。普通群落為整個(gè)系統(tǒng)提供多樣基因，用以維持系統(tǒng)的多樣性，主要利用了生物學(xué)中物以類(lèi)聚的小生境原理，該群落中的各種群之間沒(méi)有血緣關(guān)系。根據(jù)優(yōu)勝劣汰的生存原則，利用隨機(jī)種群替換普通群落中的劣勢(shì)種群。實(shí)驗(yàn)證明，雜交群落中往往比較容易產(chǎn)生優(yōu)良品種，因此在算法中加入雜交種群以加快尋優(yōu)速度。精英群落挑選優(yōu)良品種進(jìn)行繁殖，該群落使用云模型進(jìn)化來(lái)更新個(gè)體以提高尋優(yōu)精度。

圖4 基因交換

圖5 群落的系統(tǒng)結(jié)構(gòu)框圖

3個(gè)群落之間的關(guān)系體現(xiàn)在種子篩選的環(huán)節(jié)。

種子篩選：從普通群落中篩選m個(gè)來(lái)自不同種群的最優(yōu)個(gè)體，作為更新普通群落的種子(普通種子)。從所有群落中選取m個(gè)不同的最優(yōu)個(gè)體，作為更新精英群落的種子(精英種子)。將普通種子與精英種子作為雜交群落的種子。由于普通群落中的各種群之間沒(méi)有血緣關(guān)系，因此普通種子之間有較大的基因差異，可以保持系統(tǒng)的多樣性，避免算法進(jìn)入局部最優(yōu)。精英種子主要利用優(yōu)良種子進(jìn)行繁殖，加快算法尋優(yōu)速度。

整個(gè)算法流程如圖6所示，主要步驟有：初始化群落、適應(yīng)度評(píng)估、個(gè)體選擇、個(gè)體更新等。

(1)初始化群落：利用隨機(jī)函數(shù)產(chǎn)生n個(gè)個(gè)體，n為群落規(guī)模，每個(gè)個(gè)體含有Nc個(gè)待測(cè)核的測(cè)試資源(I/O端口，TSV)分配信息，初始化3個(gè)群落。

圖6 算法流程圖

(2)適應(yīng)度評(píng)估：計(jì)算每個(gè)個(gè)體的測(cè)試時(shí)間。

(3)個(gè)體選擇：如前文的種子篩選。

(4)個(gè)體更新：該步驟是整個(gè)算法的核心部分，包括3個(gè)群落的個(gè)體更新，其中普通群落和精英群落利用云模型更新個(gè)體，過(guò)程相似。而雜交群落通過(guò)交叉變異來(lái)更新個(gè)體。

云模型操作：通過(guò)正向云發(fā)生器來(lái)更新每個(gè)個(gè)體中的基因，無(wú)效基因‘X’不需要更新。步驟如下：

(1)設(shè)置云模型中的3個(gè)特征參數(shù)Ex, En, He，設(shè)置過(guò)程已在4.1節(jié)作了分析；

(2)將3個(gè)特征參數(shù)輸入到正向云發(fā)生器中，產(chǎn)生一個(gè)云滴，即一個(gè)新的基因。

(3)重復(fù)步驟(1)至步驟(2)，直到產(chǎn)生群落所需的個(gè)體數(shù)為止。此過(guò)程中，越優(yōu)秀的種子產(chǎn)生的種群規(guī)模越大。在普通群落中，淘汰掉最劣勢(shì)的種群，用隨機(jī)函數(shù)補(bǔ)充種群，充分利用自然界優(yōu)勝劣汰的生存規(guī)則，以加快尋優(yōu)速度。

交叉變異操作：設(shè)定雜交概率為0.8，自交和變異的概率均為0.1。在篩選種子時(shí)，為了減小近親雜交的概率，應(yīng)限定所選種子中最多只有一個(gè)精英種子。

5 實(shí)驗(yàn)結(jié)果與分析

本文選擇ITC′ 02 SoC標(biāo)準(zhǔn)電路作為實(shí)驗(yàn)對(duì)象，采用Visual C++編寫(xiě)程序，其中正向云發(fā)生器用MATLAB 7.1的MCC方式與VC混編實(shí)現(xiàn)，在Intel(R) core i3 3.1 GHz CPU, 3 G內(nèi)存Windows XP操作系統(tǒng)下運(yùn)行。本文基于4×3×3 mesh結(jié)構(gòu)的3D NoC，選取SoC基準(zhǔn)電路d695×3(30個(gè)內(nèi)嵌核)和p93791(32個(gè)內(nèi)嵌核)作為研究對(duì)象。

實(shí)驗(yàn)設(shè)定不同的TSV數(shù)量，利用本文算法對(duì)每種TSV數(shù)量的各種分配方案進(jìn)行測(cè)試分析。實(shí)驗(yàn)過(guò)程中，分別設(shè)定I/O端口對(duì)數(shù)為2, 3, 4和5；測(cè)試功耗限制為系統(tǒng)功耗的50%。由于本實(shí)驗(yàn)測(cè)試的規(guī)模較大，為了保證能搜尋到最優(yōu)測(cè)試時(shí)間，經(jīng)過(guò)多次實(shí)驗(yàn)調(diào)整，設(shè)定每個(gè)群落的規(guī)模為1000。

圖7給出了各種TSV數(shù)量所對(duì)應(yīng)的兩種基準(zhǔn)電路IP核的最優(yōu)測(cè)試時(shí)間。由圖7可以看出，I/O端口對(duì)數(shù)一定時(shí)，測(cè)試時(shí)間隨著TSV數(shù)量的增加而下降，但當(dāng)TSV增加到一定數(shù)量時(shí)，測(cè)試時(shí)間基本上保持穩(wěn)定的變化趨勢(shì)。原因是TSV數(shù)量在一定范圍內(nèi)的增加使得測(cè)試數(shù)據(jù)可以在上下層之間暢通傳輸，但當(dāng)TSV過(guò)多而I/O端口對(duì)數(shù)有限時(shí)，只會(huì)造成一些TSV處于饑餓狀態(tài)，即造成TSV浪費(fèi)。另外，由圖7縱向?qū)Ρ瓤芍?，?dāng)TSV數(shù)量一定時(shí)，測(cè)試時(shí)間隨著I/O端口對(duì)數(shù)的增加而減少，但當(dāng)TSV數(shù)量較少時(shí)，上下層間測(cè)試數(shù)據(jù)的傳輸達(dá)到了飽和狀態(tài)，此時(shí)即使增加I/O端口對(duì)數(shù)，也不能減少測(cè)試時(shí)間。圖7數(shù)據(jù)表明，對(duì)于規(guī)模為4 ×3×3的3D mesh 結(jié)構(gòu)NoC, I/O端口對(duì)數(shù)與TSV數(shù)量有一定的匹配關(guān)系，當(dāng)I/O端口對(duì)數(shù)為2時(shí)，在TSV數(shù)量為4左右處開(kāi)始尋得最優(yōu)測(cè)試時(shí)間；當(dāng)I/O端口對(duì)數(shù)為3時(shí)，在TSV數(shù)量為6左右處開(kāi)始尋得最優(yōu)測(cè)試時(shí)間；當(dāng)I/O端口對(duì)數(shù)為4時(shí)，在TSV數(shù)量為8左右處開(kāi)始尋得最優(yōu)測(cè)試時(shí)間；當(dāng)I/O端口對(duì)數(shù)為5時(shí)，在TSV數(shù)量為10左右處開(kāi)始尋得最優(yōu)測(cè)試時(shí)間。此時(shí)TSV在各層的最優(yōu)分配方案如表2第3列所示，括號(hào)中第1個(gè)數(shù)據(jù)為上層TSV數(shù)量，第2個(gè)為底層TSV數(shù)量。由表2中數(shù)據(jù)可以看出，在測(cè)試模式下，當(dāng)TSV總數(shù)一定時(shí)，底層分配的TSV數(shù)量多于上層，可以提高TSV的利用率，優(yōu)化測(cè)試時(shí)間。

為了驗(yàn)證改進(jìn)算法(ICEA)的性能，在表2相同的條件下，即I/O端口對(duì)數(shù)、TSV總數(shù)以及TSV分配方案相同，NoC的結(jié)構(gòu)不變，將其與沒(méi)有采用精英群落、雜交群落以及小生境技術(shù)的算法(CEA)進(jìn)行NoC測(cè)試規(guī)劃研究比較，實(shí)驗(yàn)設(shè)置CEA的群落規(guī)模為3000，最大進(jìn)化代數(shù)設(shè)為2000，將研究結(jié)果與ICEA的研究結(jié)果進(jìn)行比較，結(jié)果如表2所示。由表2的測(cè)試時(shí)間和尋優(yōu)代數(shù)可以看出，無(wú)論在尋優(yōu)精度還是尋優(yōu)速度上，算法ICEA都比算法CEA有明顯的優(yōu)勢(shì)，特別是在I/O端口對(duì)數(shù)以及TSV總數(shù)比較大時(shí)，優(yōu)勢(shì)更為明顯。原因是本文算法將云進(jìn)化算法與小生境技術(shù)以及遺傳算法中的雜交技術(shù)有效地結(jié)合起來(lái)，提高了算法的尋優(yōu)精度和尋優(yōu)速度。

圖7 測(cè)試時(shí)間與TSV數(shù)量關(guān)系

表2 最優(yōu)TSV數(shù)量的分配方案以及算法比較

6 總結(jié)

本文采用改進(jìn)后的進(jìn)化算法對(duì)TSV數(shù)量受約束的3D NoC進(jìn)行測(cè)試規(guī)劃研究，并探討TSV數(shù)量?jī)?yōu)化問(wèn)題。選取ITC′ 02測(cè)試標(biāo)準(zhǔn)電路進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，當(dāng)I/O端口對(duì)數(shù)一定時(shí)，適度選取TSV數(shù)量可以降低測(cè)試成本；當(dāng)TSV數(shù)量一定時(shí)，底層分配的TSV數(shù)量多于上層，可以提高TSV的利用率。實(shí)驗(yàn)結(jié)果證明，加入小生境技術(shù)以及雜交技術(shù)的云模型進(jìn)化算法收斂速度快，利用其對(duì)3D NoC進(jìn)行測(cè)試規(guī)劃研究，可以快速而且精確地找到最優(yōu)測(cè)試方案。

本文提出的測(cè)試規(guī)劃方法針對(duì)3D NoC的測(cè)試資源分配進(jìn)行研究，算法將測(cè)試數(shù)據(jù)經(jīng)過(guò)的路徑定義為染色體，不依賴(lài)于NoC結(jié)構(gòu)，因此適用于不同拓?fù)浣Y(jié)構(gòu)的3D NoC。不同拓?fù)浣Y(jié)構(gòu)的3D NoC需要選取合適的路由算法，但不同的路由算法主要影響數(shù)據(jù)的傳輸時(shí)間，不會(huì)影響本方法的應(yīng)用。

[1] Hwang Yong-joong, Lee Jae-hun, and Han Tae-hee. 3D Network-on-Chip system communication using mini-mum number of TSVs[C]. ICTC 2011, Seoul, Korea, 2011: 517-522.

[2] 歐陽(yáng)一鳴, 劉蓓, 梁華國(guó). 一種三維SoCs綁定前的測(cè)試時(shí)間優(yōu)化方法[J]. 電子測(cè)量與儀器學(xué)報(bào), 2011, 25(2): 164-169. Ouyang Yi-ming, Liu Bei, and Liang Hua-guo. Optimizing method for pre-bond test time on three-dimensional SoCs[J]. Journal of Electronic and Instrument, 2011, 25(2): 164-169.

[3] Noia B, Chakrabarty K, and Xie Y. Test-wrapper optimization for embedded cores in TSV-based three-Dimensional SoCs[C]. IEEE International Conference on Computer Design, Lake Tahoe, CA, USA, 2009: 70-77.

[4] Roy S K, Giri C, Ghosh S, et al.. Optimizing test wrapper for embedded cores using TSV based 3D SoCs[C]. IEEE Computer Society Annual Symposium on VLSI, Chennai, India, 2011: 31-36.

[5] Cota érika and Liu Chun-sheng. Constraint-driven test scheduling for NoC-based systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(11): 2465-2478.

[6] Mali G, Das S, Rahaman H, et al.. Non-preemptive test scheduling for Network-on-Chip(NoC) based systems by reusing NoC as TAM[C]. IEEE Asia Pacific Conference Circuits and Systems, Kuala Lumpur, Malaysia, 2010: 268-271.

[7] Liu C, Zhang L, Han Y H, et al.. Vertical interconnects squeezing in symmetric 3D mesh Network-on-Chip[C]. Asia and South Pacific Design Automation Conference(ASPDAC), Yokohama, Japan, 2011: 357-362.

[8] Sbiai T and Namba K. NoC Dynamically reconfigurable as TAM[C]. 2012 IEEE 21st Asian Test Symposium(ATS), Niigata, Japan, 2012: 326-331.

[9] Amory A, et al.. Determining the test sources/sinks for NoC TAMs[C]. 2013 IEEE Computer Society Annual Symposium, Natal, Brazil, 2013: 8-13.

[10] Cota E, Zeferino C, Carro L, et al.. Reusing an on-chip network for the test of core-based systems[J]. ACM Transactions on Design Automation of Electronic Systems, 2004, 9(4): 471-499.

[11] Chakrabarty K. Test scheduling for core-based systems using mixed-integer linear programming[J]. IEEE Transactions on ComPuter-Aided Design of Integrated Cireuits and Systems, 2000, 19(10): 1163-1174.

[12] 張光衛(wèi), 何銳, 劉禹, 等. 基于云模型的進(jìn)化算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(7): 1082-1091. Zhang Guang-wei, He Rui, Liu Yu, et al.. An evolutionary algorithm based on cloud model[J]. Chinese Journal of Computers, 2008, 31(7): 1082-1091.

[13] 許川佩, 姚芬, 胡聰. 基于云進(jìn)化算法的NoC資源節(jié)點(diǎn)優(yōu)化測(cè)試研究[J]. 電子測(cè)量與儀器學(xué)報(bào), 2012, 26(3): 192-196. Xu Chuan-pei, Yao Fen, and Hu Cong. Optimal test of NoC resource nodes based on cloud evolution algori-thm[J]. Journal of Electronic Measurement and Instrument, 2012, 26(3): 192-196.

[14] 李國(guó)柱. 基于云模型的實(shí)數(shù)編碼量子進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用, 2013, 33(9): 2550-2552, 2569. Li Guo-zhu. Real-coded quantum evolutionary algorithm based on cloud model[J]. Journal of Computer Applications, 2013, 33(9): 2550-2552, 2569.

許川佩： 女，1968年生，教授，碩士生導(dǎo)師，主要研究方向?yàn)樽詣?dòng)測(cè)試總線(xiàn)與系統(tǒng)、集成電路測(cè)試技術(shù).

陳家棟： 男，1986年生，研究生，研究方向?yàn)榧呻娐窚y(cè)試.

Research on Test Scheduling of 3D NoC under Number Constraint of TSV (Through-Silicon-Vias) Using Evolution Algorithm Based on Cloud Model

Xu Chuan-pei Chen Jia-dong Wan Chun-ting
(School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin 541004, China)

As Through-Silicon-Vias (TSVs) in three-Dimensional Network-on-Chip (3D NoC) accompany some overhead such as the cost and the area, in order to optimize the number of TSVs of 3D NoC in test mode and reduce the test time, a new method using evolution algorithm based on cloud model is proposed to research on the test scheduling of 3D NoC and the impact of TSVs number and their allocation in each layer on 3D NoC test. This method combines the cloud evolution algorithm with niche technology and hybridization technique in genetic algorithm. It uses effectively the concepts of heredity, natural selection and community diversity to improve the quality of the algorithm on optimizing speed and precision. Experimental results demonstrate that the proposed method can not only effectively prevent from running into local optimization solution, but also improve the ability and speed of searching the best solution, and that TSVs number of 3D NoC can be optimized to improve the TSVs’ utilization.

Three-Dimensional Network-on-Chip (3D NoC); Through-Silicon-Via (TSV); Cloud model; Evolution algorithm

TN407

A

1009-5896(2015)02-0477-07

10.11999/JEIT140165

2014-01-24收到，2014-04-24改回

*通信作者：陳家棟 cljxdm@163.com