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

許川佩 陳家棟萬春霆

(桂林電子科技大學電子工程與自動化學院 桂林 541004)

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

許川佩 陳家棟*萬春霆

(桂林電子科技大學電子工程與自動化學院 桂林 541004)

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

3維片上網絡；硅通孔；云模型；進化算法

1 引言

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

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

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

2 3D NoC結構

3D NoC結構主要有3D mesh 結構，蝶形胖樹結構，XnoTs結構等。目前學者主要研究的是3D mesh 結構。典型的3D mesh結構NoC如圖1(a)所示，相鄰兩層對應的上、下兩個路由節(jié)點均由TSV連接起來。

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

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

圖1 3D mesh 結構NoC及其基本單元

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

3.1 NoC測試規(guī)劃

為減少硬件開銷，NoC測試采用重用片上網絡的測試訪問機制[6,8,9]，即復用片上網絡的路由節(jié)點和通道(channel)等資源，實施并行測試以提高測試效率。在測試core時，測試矢量由輸入端口送入網絡，按一定的路由算法到達core，生成的測試響應以同樣的路由算法到達輸出端，由外部的測試響應接收并分析，完成一個核的測試。

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

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

3.2 路由算法及路徑沖突

在測試過程中，采用XYZ路由算法，數據包由源節(jié)點沿X方向傳輸，到達與目標節(jié)點x坐標相同的路由節(jié)點后，轉向Y方向進行傳輸，到達與目標節(jié)點y坐標相同的路由節(jié)點后轉向Z方向傳輸，直至目標節(jié)點。

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

3.3 測試時間以及功耗約束

(1)測試時間 多對端口并行測試規(guī)劃如圖2所示，總測試時間取決于測試時間最長的那對I/O端口。

總測試時間為

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

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

式中Tp(first), Tp(last)分別為第1個測試數據包和最后1個測試響應數據包在兩個路由節(jié)點之間的傳輸時間，hopi和hopo分別代表數據包輸入以及輸出測試核所經過的路由跳數。

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

通常，核的測試時間遠大于數據包的傳輸時間，因此本文不考慮傳輸時間的影響。

(2)功耗約束 考慮到異構NoC每層的功耗不同，因此有必要將功耗約束到每一層。對于每個時隙(time slot)，第 l層的功耗必須滿足:

單個核的功耗包含傳輸功耗和測試功耗，即P=np ·Pp+Pc，其中np是該核的數據包數量，Pc是該核的測試功耗，Pp是一個數據包通過路徑的傳輸功耗。

其中Pr代表數據包在一個路由器上的傳輸功耗，Pxy代表數據包在一條水平通道上的傳輸功耗，Ptv代表數據包在一條TSV上的傳輸功耗，Nr, Nch, Ntv分別代表數據包經過的路由器數量，通道數量以及TSV數量，其中通道數量包含了TSV數量。

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

Pr, Pxy以及Ptv均為常數。采用文獻[10]的功耗模型，Pr=10, Pxy=2。由于互連TSV很短，比水平互連通道小兩個數量級，所以功耗遠遠小于水平通道的功耗，考慮到TSV的工藝與分布結構還沒有統一，本文設定Ptv=1。

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

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

4.1 算法的相關設計

假定NoC有L層，將底層稱為第 0層, 其上各層按順序依次稱為第 1層，第 2層……。核數量為第 l層的核數量，各層核的編號依次0, 1,…,-1。TSV數量其中為第 l層的TSV數量，各層TSV編號依次為0, 1,…,-1。設I/O端口對數為NIO，則I/O端口對的編號依次為0, 1,…,NIO-1。

本文以3層NoC為例來進行說明。

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

圖3 染色體結構映射圖

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

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

表1 測試調度的偽代碼

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

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

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

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

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

4.2 算法設計

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

圖4 基因交換

圖5 群落的系統結構框圖

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

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

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

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

圖6 算法流程圖

(2)適應度評估：計算每個個體的測試時間。

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

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

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

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

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

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

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

5 實驗結果與分析

本文選擇ITC′ 02 SoC標準電路作為實驗對象，采用Visual C++編寫程序，其中正向云發(fā)生器用MATLAB 7.1的MCC方式與VC混編實現，在Intel(R) core i3 3.1 GHz CPU, 3 G內存Windows XP操作系統下運行。本文基于4×3×3 mesh結構的3D NoC，選取SoC基準電路d695×3(30個內嵌核)和p93791(32個內嵌核)作為研究對象。

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

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

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

圖7 測試時間與TSV數量關系

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

6 總結

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

本文提出的測試規(guī)劃方法針對3D NoC的測試資源分配進行研究，算法將測試數據經過的路徑定義為染色體，不依賴于NoC結構，因此適用于不同拓撲結構的3D NoC。不同拓撲結構的3D NoC需要選取合適的路由算法，但不同的路由算法主要影響數據的傳輸時間，不會影響本方法的應用。

[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] 歐陽一鳴, 劉蓓, 梁華國. 一種三維SoCs綁定前的測試時間優(yōu)化方法[J]. 電子測量與儀器學報, 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]. 計算機學報, 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] 許川佩, 姚芬, 胡聰. 基于云進化算法的NoC資源節(jié)點優(yōu)化測試研究[J]. 電子測量與儀器學報, 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] 李國柱. 基于云模型的實數編碼量子進化算法[J].計算機應用, 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年生，教授，碩士生導師，主要研究方向為自動測試總線與系統、集成電路測試技術.

陳家棟： 男，1986年生，研究生，研究方向為集成電路測試.

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