基于改進遺傳算法的3D NoC測試優(yōu)化

凌景 唐靜

（巢湖學院，安徽 巢湖 238000）

1 引言

隨著半導體集成技術和制造工藝的不斷發(fā)展，片上網(wǎng)絡（Network-On-Chip，NoC）技術作為一種新型體系結(jié)構(gòu)解決了SoC總線通信的局限性[1]，而三維片上網(wǎng)絡（three dimensional network-on-chip，3DNoC）的出現(xiàn)解決了2D NoC全局連線過長、連線延遲和功耗開銷等問題，逐漸成為NoC發(fā)展的主流[2]。3D NoC的測試隨著IP核集成時不斷增加的種類和數(shù)量變得愈來愈重要，隨著芯片集成復雜度的提高同時也愈來愈困難，因此，3D NoC發(fā)展的瓶頸之一是怎樣實現(xiàn)高效的測試調(diào)度。

目前對3D NoC測試調(diào)度的研究主要集中在優(yōu)化算法和優(yōu)化策略上，文獻[3]利用遺傳算法將系統(tǒng)中的待測核分配到各個測試端口，實驗結(jié)果表明，該方法可減小測試時間，但在測試過程中未考慮到測試端口的位置。文獻[4]采用Kernighan-Lin算法實現(xiàn)對TSV位置的合理選擇，該方法有助于3D設計實現(xiàn)，但沒有權衡對系統(tǒng)性能的影響。文獻[5]采用粒子群算法對3D NoC TSV數(shù)量和位置進行協(xié)同優(yōu)化，實驗結(jié)果表明，該方法可提高TSV的利用率，完成TSV位置的尋優(yōu)。

本文結(jié)合3D NoC通過路由傳輸數(shù)據(jù)的特點，重用NoC作為TAM，并將TAM動態(tài)劃分的帶分復用和并行測試的策略。將遺傳算法和云模型相結(jié)合，以測試時間為目標函數(shù)，對分配到測試端口上的IP核進行調(diào)度，尋優(yōu)最佳調(diào)度方案。

2 3D NoC測試調(diào)度

2.1 測試策略

本文進行測試調(diào)度研究的NoC為規(guī)則的3D Mesh結(jié)構(gòu)，圖1所示為其體系結(jié)構(gòu)，資源結(jié)點、路由結(jié)點和通信鏈路是主要組成部分[6]，其中水平方向的互連線和垂直方向的硅通孔組成了通信鏈路。資源結(jié)點主要用來完成系統(tǒng)計算任務，又稱為資源內(nèi)核或IP核；NoC核與核之間的數(shù)據(jù)傳輸主要是通過路由節(jié)點進行數(shù)據(jù)的存儲和轉(zhuǎn)發(fā)，這是與SoC通過總線來實現(xiàn)數(shù)據(jù)傳輸本質(zhì)上的區(qū)別；IP核和路由節(jié)點之間的數(shù)據(jù)傳輸通過資源網(wǎng)絡接口實現(xiàn)[7]。3D NoC片上豐富的資源為并行測試提供了硬件支持，為減小并行測試時的硬件開銷，本文重用NoC作為TAM，即重復使用路由節(jié)點、互連線和TSV完成測試。

圖1 3D Mesh NoC結(jié)構(gòu)圖

2.2 測試調(diào)度模型

在測試過程中，采用xyz路由算法，即一旦給核分配了TAM帶寬和I/O端口，便確定了核的測試路徑，以圖1為例，核的測試過程如下：若核8的測試矢量從源節(jié)點核1開始出發(fā)，根據(jù)設定的路由算法，先沿X方向傳輸，到達與Core8 X坐標相同的Core2路由節(jié)點后，由于Core2和Core8兩路由節(jié)點Y坐標相同，測試矢量不需沿Y方向傳輸，直接沿Z方向傳輸?shù)竭_待測核，測試完成后，測試矢量按照同樣的傳輸算法到達目的節(jié)點Core6，此時對Core8的測試結(jié)束。Core8總的測試時間包括傳輸測試矢量的時間和測試Core8所用的時間。

本文采用帶分復用的方法對3D NoC測試規(guī)劃，使同一時刻IP核的多個測試數(shù)據(jù)共享同一TAM并行傳輸[8]，若core的測試順序調(diào)度不合理，則有可能產(chǎn)生路徑?jīng)_突，影響系統(tǒng)總調(diào)度時間和功耗。如圖2所示，圖2（a）是未使用帶分復用的規(guī)劃結(jié)果，最后的測試時間為Ta；圖2（b）是使用帶分復用的規(guī)劃結(jié)果，最后的測試時間為Tb，Ta要遠遠大于Tb，可見方案（b）要優(yōu)于方案（a）。相比以往一條TAM被單個IP核測試數(shù)據(jù)獨占進行傳輸，資源利用率和并行測試的效率因帶分復用提高了[9]。描述文中的測試調(diào)度問題為：如何無沖突地調(diào)度個待測核core，在帶寬允許的條件下，使系統(tǒng)整體測試時間最小。

圖2 3D NoC測試調(diào)度結(jié)果

2.3 目標函數(shù)以及TAM約束函數(shù)

2.3.1 測試時間

在圖2中的每個測試節(jié)點更新待測核時，測試結(jié)束時間最大的核決定了系統(tǒng)總測試時間，即T ＝ max（Tend（corei）），i≤1≤N。其中，核的總數(shù)為 N，corei測試結(jié)束時間 Tend（corei）包括 corei開始測試的時間與測試corei的總時間。corei前一個核的結(jié)束測試時間決定了該核開始測試時間，核傳輸測試矢量的時間 Ttr和測試核的時間 Ttc為 corei測試總時間 Ttest（corei），即 Ttest（corei） =Ttr+Ttc。

文中對核進行測試的測試矢量是通過測試數(shù)據(jù)包在各個路由節(jié)點間傳輸，當?shù)谝粋€測試數(shù)據(jù)包傳輸?shù)奖粶y核時開始對核進行測試，余下的測試數(shù)據(jù)包相繼傳入網(wǎng)絡，此時對核進行測試的時間包括了測試數(shù)據(jù)包的傳輸時間。因此，第一個測試數(shù)據(jù)包從源節(jié)點傳輸?shù)奖粶y核的時間Tpacket（first）和最后一個測試數(shù)據(jù)包從被測核傳輸?shù)侥康墓?jié)點的時間Tpacket（last）為測試數(shù)據(jù)包傳輸總時間，即Ttr=nhopi·Tpacket（first）＋nhop0·Tpacket（last）。其中，nhopi是第一個測試數(shù)據(jù)包傳輸?shù)奖粶y核所經(jīng)過的路由跳數(shù)，nhop0是最后一個測試數(shù)據(jù)包從被測核傳輸?shù)侥康墓?jié)點所經(jīng)過的路由跳數(shù)。文中各路由節(jié)點用三維坐標表示，設待測核的坐標為（xc，yc，zc），源節(jié)點的坐標為（xi，yi，zi），目的節(jié)點的坐標為（xo，yo，zo）。則：

2.3.2 TAM約束函數(shù)

當TAMj上核i開始測試時，該核測試數(shù)據(jù)傳輸帶寬Wcoreij的分配必須滿足：其中，每條TAM總帶寬為WTAM，文中TAM的測試方法采用重用NoC，因此每條TAM總帶寬固定且相等。為TAMj上所有在測核占用的帶寬之和。

3 改進遺傳算法的3D NoC測試優(yōu)化研究

3.1 3D NoC測試調(diào)度編碼設計

文中將核分配到實施帶分復用的TAM上，不同的分配方案使得最后調(diào)度的結(jié)果不同，即核的測試數(shù)據(jù)包在TAM上傳輸順序決定了最終的測試時間。本文以規(guī)模為M×N×L、TAM的條數(shù)為B的3D NoC為例，為了體現(xiàn)每個核的特征，本文采用的編碼方法如下：

3.2 個體、基因

上文中的S即是完成所有核測試的一種調(diào)度方案被稱為個體，基因則是組成個體的各元素，基因的特征用S中的子矩陣Gbj中的元素表示。不同的基因在不同的測試節(jié)點表現(xiàn)出的特征不同，進而使得個體特征不同。本文中基因表示核的標號，利用云模型更新所選個體非0基因即有效基因。若新生成的子代中最優(yōu)個體的適應度比父代差，則當代的種子仍然取父代個體。

3.3 算法流程

遺傳算法借用了仿真生物遺傳學和自然選擇機理，通過遺傳、變異等機制尋找最優(yōu)個體，但僅僅通過交叉變異實現(xiàn)個體的更新，尋優(yōu)精度不高，容易陷入局部最優(yōu)。本文優(yōu)化測試調(diào)度采用結(jié)合了云模型的改進遺傳算法，利用云模型在進化初期更新個體，當調(diào)節(jié)云模型參數(shù)時無法尋優(yōu)到更優(yōu)秀的個體，實施遺傳算法的交叉變異、個體之間競爭等策略繼續(xù)尋優(yōu)，直至達到最大迭次數(shù)。云模型特征如圖3，其數(shù)字特征用期望Ex、熵En和超熵He三個參數(shù)表示。將優(yōu)秀個體作為云模型更新時的Ex，進化過程中物種變異的范圍可用En表示，進化過程中的穩(wěn)定性可用He表示[9-10]。

圖3 云模型特征圖

將云模型與進化算法相結(jié)合，算法主要流程如圖4，包括：種群初始化、適應度值計算、云模型更新個體、云進化算法自適應調(diào)整、遺傳算法更新策略、種群間個體競爭。

圖4 算法流程圖

3.3.1 云模型更新個體 從初始種群中選取適應度值最優(yōu)的個體，將該個體的基因作為云模型的期望值，初始的熵取值為 e／c1，超熵取值為 En／c2，c1、c2為控制系數(shù)，C1初始值取 1，C2初始值取 10，e 為待測核編號范圍。生成云滴的過程如下。

輸入：Ex、En和 He，n% 數(shù)字特征和云滴數(shù)

若云模型更新過程中連續(xù)多代都出現(xiàn)了適應性最強的個體，此時的進化過程有可能逼近了原極值領域或者找到了新極值領域，此時需減小搜索半徑和增大搜索穩(wěn)定度[11]，可通過減小En和He來實現(xiàn)，達到局部求精的目的。若經(jīng)過多代更新都沒有更優(yōu)的個體出現(xiàn)時，進化過程此時有可能陷入局部最優(yōu)，可通過提高En和He擴大搜索半徑和減小搜索穩(wěn)定度以達到局部求變和尋找全局最優(yōu)的目的[12-13]。

3.3.2 遺傳算法更新策略 當經(jīng)過若干代都沒有更優(yōu)秀的個體出現(xiàn)時，此時對種群引入遺傳算法進行更新。文中采用輪盤賭產(chǎn)生0～1的隨機概率p，根據(jù)實際情況設定p1、p2的值。當0≤p≤p1時進行自交，當p1≤p≤p2時進行雜交，當p2≤p＜1時進行變異。

3.3.3 種群間個體競爭 為加強種群間的個體交流進而有效避免算法陷入局部最優(yōu)，本文設計如下的競爭機制，主要過程為：兩兩比較從每個種群中挑選出的d個優(yōu)秀個體，以適應度值為評判標準，適應度值高者在比較中獲得勝利，種群i中的優(yōu)秀個體j的勝負次數(shù)分別用uij、vij（1≤i≤2，1≤j≤d）表示。經(jīng) d2次比較后，計算每個個體的勝、負次數(shù)差值△ij=uij-vij，1≤i≤2，1≤j≤d，若△ij＜ 0，則淘汰種群i中的個體j，淘汰的個體j用隨機生成新個體代替。圖5中以每個種群選出3個個體為例進行說明u11=2，v11=1，△11=1，u12=0，v12=3，△12=-3，u13=3，v13=0，△13=3，u21=1，v21=2，△21=-1，u22=1，v22=2，△22=-1，u23=2，v23=1，△23=1 則種群 1 中的個體 3，種群 2 中的個體 1、2 被淘汰。經(jīng)過多次比較、淘汰、替換操作后，剔除了適應度差的個體，其位置被加入的新個體代替，增加了多樣性，實現(xiàn)了種群間個體交流。

圖5 個體競爭示意圖

4 實驗結(jié)果分析

本文在不同的TAM條數(shù)下采用ITC′02基準電路d695和2*d695實驗，在的3D NoC Mesh結(jié)構(gòu)中映射d695電路，在3×3×3的3D NoC Mesh結(jié)構(gòu)中映射2*d695電路。核的分布如表1所示，依據(jù)的原則為每層IP核的測試時間、測試功耗總和大致相同。其中第1個d695電路中的第5個核用1-5表示；第2個d695電路中的第5個核用2—5表示。

實驗中設定不同的TAM條數(shù)，對每條TAM上IP核分配方案利用本文的方法進行分析，為驗證本文結(jié)合云模型的遺傳算法（CGA）的性能，將沒有結(jié)合云模型遺傳算法（GA）與本文的實驗結(jié)果進行對比，比較結(jié)果如下圖所示。以2條TAM為例，采用CGA的測試時間為14386個時鐘周期，而采用GA的測試時間為28467個時鐘周期，采用GA的測試時間明顯多于采用CGA的測試時間，因此本文所采用的方法總是優(yōu)于僅使用遺傳算法的優(yōu)化結(jié)果，且在TAM條數(shù)較少時，優(yōu)化的效果更明顯。

圖6 d695電路的測試結(jié)果

圖7 2*d695電路的測試結(jié)果

5 結(jié)論

本文采用帶分復用的測試策略，重用NoC作為TAM，在TAM帶寬約束下對3D NoC測試調(diào)度進行研究，將遺傳算法與云模型相結(jié)合，進化初期使用云模型更新個體，并根據(jù)實驗結(jié)果實時調(diào)節(jié)云模型參數(shù)。當云模型已無法更新更優(yōu)秀的個體時，加入遺傳算法的交叉變異以及個體間競爭機制繼續(xù)更新，直至得出最佳測試時間，完成3D NoC資源內(nèi)核測試規(guī)劃。實驗結(jié)果表明，本文的方法可明顯減少測試時間，提高測試效率。