基于超立方體拓撲結構的NoC測試規(guī)劃研究

胡 聰 信文雪 周 甜 朱愛軍 許川佩

1(桂林電子科技大學電子工程與自動化學院 廣西 桂林 541004) 2(桂林航天工業(yè)學院電子信息與自動化學院 廣西 桂林 541004) 3(廣西自動檢測技術與儀器重點實驗室 廣西 桂林 541004)

0 引 言

片上網(wǎng)絡(Network on Chip,NoC)結構作為一種高度集成的片上多處理器系統(tǒng)[1]，雖然打破了傳統(tǒng)片上系統(tǒng)(System on Chip,SoC)結構的性能瓶頸，但是，單位面積上芯片IP核(Intellectual Property core)數(shù)目的增長以及芯片結構復雜度的攀升，將會對芯片的測試效率帶來新一輪的考驗。因此，以縮減測試成本為目標，考慮軟硬件等多種約束條件的限制，如何實施高效的并行傳輸與測試，成為一個NP難題，同時也具有較大研究價值。

為此大量學者在NoC測試方面做了諸多研究。文獻[2]提出一種基于模糊邏輯的任務映射方法，可根據(jù)芯片需求調整任務映射權重因子，有效降低通信延時、功耗以及芯片測試核的最高溫度。文獻[3]提出了一種新的元啟發(fā)式算法——差分灰狼算法。通過對元啟發(fā)式算法進行改進，有效降低了測試過程中的時間和經(jīng)濟成本。文獻[4]針對非全互連類型的3D NoC,提出一種能夠自適應調整路由路徑的混合多播算法，在同一平面內與不同平面之間分別通過使用Hamilton圖與樹結構的多播思想進行路徑選擇,保證了數(shù)據(jù)在高效傳輸過程中不會失真。文獻[5]為了減少測試時間，提出了xy方向連接子圖劃分方法來消除測試前的路徑?jīng)_突，同時確定了測試訪問點的位置。綜上所述，目前的研究雖然對測試過程中的功耗和時間進行了不同程度的優(yōu)化，但所選拓撲結構僅處于二維和三維階段。

針對上述文獻的不足，本文提出了一種基于超立方體拓撲結構的NoC測試規(guī)劃方法。從NoC測試規(guī)劃的拓撲結構方面進行考慮，提出采用在平均延時、網(wǎng)絡直徑以及功耗等方面都優(yōu)于3D Mesh結構的超立方體拓撲結構對NoC測試規(guī)劃進行研究；在測試規(guī)劃中針對該拓撲結構設計了具有部分自適應能力的E-cube路由算法，減少了測試過程中的路由傳輸時間；本文采用的優(yōu)化算法為改進的PSO，增強了PSO的全局尋優(yōu)能力與局部精細搜索能力，實現(xiàn)了NoC測試規(guī)劃問題的優(yōu)化求解。

1 NoC測試基本概念

1.1 超立方體拓撲結構

拓撲結構決定了NoC中IP核、路由器以及通信鏈路之間的連接方式，很大程度上決定了系統(tǒng)的性能和代價。3D Mesh結構因其對稱性好、可擴展性強、簡單易實現(xiàn)、布局規(guī)整等特點，目前在片上網(wǎng)絡研究中被廣泛采用，但是它仍具有平均延時長和網(wǎng)絡直徑大等缺點。超立方體拓撲結構不僅具有對稱性好、可擴展性強等特點，而且其網(wǎng)絡直徑短,因此本文選擇超立方體結構對片上網(wǎng)絡進行研究。

為降低測試硬件開銷、減少測試時間，本文復用NoC作為測試訪問機制(test access mechanism,TAM)，采用并行測試的方式對各個IP核進行測試。并行測試雖然加快了測試時間，但容易造成過熱測試和損壞芯片等問題。因此本文通過添加子立方體功耗和總功耗雙重約束來減少測試過程中由于功耗過高而產生的一系列故障問題。

本文研究的NoC測試規(guī)劃問題可簡要概述為：對于一個NoC，已知N個IP核的相關參數(shù)如：掃描鏈長度及數(shù)量和測試矢量個數(shù)等，以及帶寬數(shù)目、TAM條數(shù)、拓撲結構、調度方式和路由算法等。研究在測試資源無沖突、功耗滿足限制的條件下，如何通過群智能優(yōu)化算法求得最佳測試方案。

1.2 目標函數(shù)與測試約束函數(shù)條件

1.2.1目標函數(shù)

測試調度以系統(tǒng)測試時間為目標函數(shù)，系統(tǒng)測試時間取決于測試時間最長的一條TAM，計算公式如下：

(1)

式中：B代表TAM條數(shù)；k代表第b條TAM上的IP核個數(shù)；Ttesti代表IP核i的測試時間，包含對IP核自身進行測試所耗費的時長及測試數(shù)據(jù)包的路由時長。

1.2.2功耗約束

測試功耗與測試時間存在互為代價的關系，雖然并行測試的方式有效縮短了測試時間，但同時也導致測試功耗的上升。本文對拓撲結構中的兩個子立方體功耗與超立方體結構的總功耗進行雙層約束。

(1) 在任意的時間槽t，任一子立方體中在測核的功耗總和Pl需要滿足：

(2)

式中：Ptesti(l)表示某一時刻分布在子立方體結構中核i的總功耗；h表示子立方體結構中被測核數(shù)目；Pmax-subcube(l)為子立方體結構的最大允許功耗。

(2) 在任意時間槽t，要求拓撲結構中所有正在進行測試的IP核的功耗之和Ptotal必須低于總功耗的上限Pmax。

(3)

式中：Ptotal為某一時刻超立方體結構中的總功耗；L表示超立方體結構中子立方體的個數(shù)；Ptest(l)為子立方體中IP核的測試功耗；Pmax為允許最大總功耗。

2 NoC測試規(guī)劃中的超立方體拓撲結構

2.1 超立方體拓撲結構

超立方體網(wǎng)絡結構[7]具有網(wǎng)絡直徑小、連通性高、網(wǎng)絡尋徑路由簡單等優(yōu)點，很早便被提出并進行研究。圖1對四維超立方體網(wǎng)絡的定義與節(jié)點的編號方式均參考文獻[7]。

圖1 四維超立方體網(wǎng)絡及結點編號

本文對N維超立方體結構與網(wǎng)絡規(guī)模為M×N×L(N>M>K>1)的3D Mesh和3D Torus結構進行了相關參數(shù)比較。由表1可知超立方體結構不僅比其他兩種結構擁有更多的物理鏈路數(shù)而且其網(wǎng)絡直徑比3D Mesh結構更短，且對于超立方體結構維數(shù)越高，對比優(yōu)勢越明顯。

表1 超立方體結構與經(jīng)典結構性能指標對比

2.2 具有部分自適應能力的E-cube路由算法

E-cube路由算法是一種確定性路由算法，不能根據(jù)網(wǎng)絡狀態(tài)進行動態(tài)調整，缺乏自適應性。本文提出了能根據(jù)網(wǎng)絡當前狀態(tài)進行適度調整的具有部分自適應能力的E-cube路由算法。

區(qū)別于確定性路由算法，本文所提算法采用低維優(yōu)先原則，通過設定輸出端口的優(yōu)先級控制數(shù)據(jù)輸出。在數(shù)據(jù)傳輸過程中，首先判斷初始節(jié)點是否與目標節(jié)點相同，若相同則將測試數(shù)據(jù)傳至此節(jié)點所在IP核，否則判斷下一跳節(jié)點中的1維方向是否被占用，如果未被占用，則向此節(jié)點傳輸，反之，則判斷下一跳節(jié)點的2維方向。以此類推，逐次向高維傳輸。這樣可以避免確定性路由算法某一維由于受到阻塞而帶來的死鎖問題。具體過程如圖2所示。

圖2 E-cube部分自適應路由算法流程

根據(jù)圖2所示路由算法，本文以具有16個路由節(jié)點的四維超立方體結構與具有相同網(wǎng)絡規(guī)模2×2×4的3D Mesh結構為例進行對比分析。圖3和圖4中黑色圓球分別代表輸入端口和待測核,黑色箭頭所示部分代表路由算法所走路徑。由對比可知，圖3測試過程中經(jīng)過的路由器個數(shù)及鏈路條數(shù)明顯低于圖4，且對于超立方體結構，維數(shù)越高，優(yōu)化效果越明顯。

圖3 四維超立方體拓撲結構

圖4 2×2×4 3D Mesh結構

3 NoC測試規(guī)基于改進粒子群算法的片上網(wǎng)絡IP核測試優(yōu)化方法

3.1 粒子群算法原理

粒子群算法(PSO)是由Kennedy博士和Eberhart博士提出的一種群體智能進化算法。本文針對NoC測試規(guī)劃問題，首先利用PSO的隨機解對一群隨機粒子進行初始化，然后粒子在每次的迭代求解過程中，通過跟蹤個體極值pbesti和群體極值gbesti不斷地更新自己的速度和位置。對于每一代個體，在找到兩個最優(yōu)值時，粒子根據(jù)如下公式來更新自己的速度和位置：

(4)

(5)

3.2 算法設計

PSO具有記憶性且操作簡單、搜索能力強、沒有交叉和變異運算，但該算法容易陷入局部最優(yōu)，且缺乏速度的動態(tài)調整。針對PSO種群多樣性不足導致的早熟收斂和由于迭代后期吸引力過大導致的粒子收斂速度變慢等現(xiàn)象，本文對粒子群算法進行如下改進：

(1) 混沌優(yōu)化算法更新準則。基于混沌的隨機、遍歷特性，通過混沌序列而非隨機函數(shù)產生初始粒子種群，可以使初始種群中的個體具備混沌序列的隨機性與遍歷性。本文采用的混沌模型為立方映射[7]，如下：

y(n+1)=4y(n)3-3y(n)

(6)

式中：y(n)∈[-1,1]，且y(n)≠0，n=0,1,…。

(2) 學習因子自適應調整。學習因子c1、c2具有自我總結和向優(yōu)秀個體學習的能力。c1、c2較小時，使粒子在遠離目標區(qū)域內徘徊，反之，可使粒子迅速向目標區(qū)域移動，甚至超過目標區(qū)域。為了平衡粒子之間的信息交互能力，得到較好的收斂效果，需要對c1、c2進行動態(tài)更新，更新公式如下：

c1=1.0-iter/itermax

(7)

c2=1-c1

(8) (3) 添加壓縮因子。由式(4)可以看出，粒子飛行速度與w相關。w越大，粒子飛行速度越大。雖然較大的w有利于跳出局部最小值，便于全局搜索，但易出現(xiàn)“早熟收斂”現(xiàn)象；w越小，則越利于局部搜索。本文提出添加壓縮因子φ的方法，對w進行改進。

(9)

(10)

令C>4,C=c1+c2。φ較w而言，不僅可以更加有效地控制和約束微粒的飛行速度，而且也增強了算法的局部搜索能力。

本文根據(jù)NoC測試，通過改進粒子群算法可以高效準確地尋找出測試過程中測試時間最短與測試功耗最低的最優(yōu)解。首先采用映射規(guī)則，將每一子立方體拓撲結構中分配的IP核自身的測試時間、測試功耗之和大致相等。其次通過混沌優(yōu)化算法增加各個IP核分配至多條TAM上的種群多樣性。最后在最優(yōu)解的查詢過程中添加學習因子與壓縮因子增強算法的搜索能力，減少搜索時間。

改進PSO流程如圖5所示，主要包括：對種群進行初始化、適應度值的計算、pbest與gbest的更新、自適應參數(shù)的調整等。具體算法流程如下：

1) 初始化粒子種群。利用混沌優(yōu)化算法對IP核的測試數(shù)據(jù)分配TAM，產生初始種群。

2) 適應度值計算。各粒子的測試時間由式(1)得出，通過比較找到當前最優(yōu)值。

3) 更新粒子歷史最優(yōu)pbest與全局最優(yōu)gbest。

4) 自適應參數(shù)調整。

(1) 利用式(7)和式(8)完成學習因子的自適應調整。

(2) 利用式(9)和式(10)完成壓縮因子的自適應調整。

5) 檢查是否達到終止條件，若達到則結束算法，得出結果，否則轉步驟2)。

圖5 算法流程

4 實驗與結果分析

為驗證本論文所提方法的有效性，選取ITC’02國際標準電路中的d695和g1023進行仿真實驗。分別將兩個電路中的IP核映射至2×2×2×2的四維超立方體結構中。遵循的映射規(guī)則為：使每一子立方體拓撲結構中安排的IP核自身的測試時間、測試功耗之和大約相等，如表2所示。在Visual Studio 2019中編譯代碼。

表2 基準電路中核的分布

本文以d695電路為例，畫出其測試過程中的Gantt圖。圖6所示為d695電路在帶寬32，功耗約束滿足50%條件下的最優(yōu)測試規(guī)劃結果圖。橫軸表示IP核測試的時間歷程，可以非常直觀地看出每個IP核測試的起止時間，縱軸代表不同的TAM。由圖可知，測試開始時，核6、5、4分別在3條TAM上并行測試，在6238時間節(jié)點處，TAM2上的5號IP核測試完畢，但此時由于路徑?jīng)_突或者不滿足功耗約束條件，3號IP核的測試數(shù)據(jù)包無法進行傳輸，需等待直至測試資源空閑或滿足功耗約束條件時才能繼續(xù)進行測試。

圖6 d695電路的測試調度結果

同等條件下，為了進一步驗證測試結果，表3對本文所提方法與前人文獻中的測試結果進行了對比，結果表明：兩條TAM時，本文最高優(yōu)化率可達16.44%；三條TAM時，本文最高優(yōu)化率可達17.38%，整體優(yōu)化率維持在5.42%～17.38%之間。

表3 不同TAM條數(shù)的優(yōu)化方法性能對比

5 結 語

本文對NoC測試規(guī)劃問題進行了研究，提出了一種基于超立方體拓撲結構的NoC測試規(guī)劃方法。該方法首先通過映射算法將多個IP核分配到超立方體拓撲結構中，采用具有部分自適應能力的E-cube路由算法對IP核進行調度測試。為了對各種測試結果進行高效尋優(yōu)，本文對PSO進行了三處改進，即引入混度序列增加初始種群的隨機性與遍歷性、添加自適應調整的學習因子及引入壓縮因子對粒子群算法進行改進，增加種群的多樣性。用兩個標準電路d695與g1023對該方法做了測試，并將實驗結果與其他測試方法的實驗結果進行比較,結果顯示本文測試方法在測試時間與程序運行時間方面都展現(xiàn)出較明顯的優(yōu)勢。