歐陽一鳴, 黃 河, 梁華國

(1.合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院,安徽 合肥 230009;2.合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院,安徽 合肥 230009)

傳統(tǒng)基于共享總線的片上系統(tǒng),其通訊能力已經(jīng)不能滿足未來SoC(System on Chip,簡稱SoC)設(shè)計的要求。為此,計算機(jī)網(wǎng)絡(luò)通訊技術(shù)被移植到芯片設(shè)計中來,以分組交換作為基本通訊技術(shù),采用全局異步-局部同步GALS(Globally Asynchronous Locally Synchronous,簡稱GALS)通訊機(jī)制,徹底解決了片上通訊的瓶頸問題。這就是片上網(wǎng)絡(luò)——NoC(Network on Chip簡稱NoC)。NoC不僅具有良好的空間可擴(kuò)展性,還支持并行的多重通訊及提供更高的帶寬。

1 NoC的相關(guān)知識

NoC的通訊架構(gòu)是由控制數(shù)據(jù)傳輸?shù)膔outer和互聯(lián)網(wǎng)絡(luò)中各 router之間的channel構(gòu)成,NoC的拓?fù)浣Y(jié)構(gòu)主要有：2D-Mesh、T orus和Fat-T ree等,本文提出的測試方法是針對2D-Mesh結(jié)構(gòu),3×3的 2D-Mesh結(jié)構(gòu)片上網(wǎng)絡(luò)如圖1所示。

圖1 3×3的2D-Mesh結(jié)構(gòu)模型

本文所涉及的有關(guān)基本概念如下：①節(jié)點。就是對片上網(wǎng)絡(luò)中路由器的簡稱。②數(shù)據(jù)包。網(wǎng)絡(luò)中傳輸?shù)南⑼ǔＳ深^部、傳輸數(shù)據(jù)和尾組成。由于通訊效率的需要,再將傳輸數(shù)據(jù)分割成更小的數(shù)據(jù)段,在測試模式下,測試向量加上包頭包尾封裝成一個數(shù)據(jù)包。③XY路由算法。基本思想是數(shù)據(jù)包在向目的節(jié)點發(fā)送的過程中,先在X方向上發(fā)送,等到達(dá)目的節(jié)點所在列后,再在Y方向上發(fā)送直至到達(dá)目的節(jié)點。④Y X路由算法?；舅枷胧菙?shù)據(jù)包在向目的節(jié)點發(fā)送的過程中,先在Y方向上傳送,然后再在X方向上傳送。⑤曼哈頓距離。假設(shè)片上網(wǎng)絡(luò)中節(jié)點P1坐標(biāo)為(x1,y1),節(jié)點P2坐標(biāo)為(x2,y2),那么該對節(jié)點間的曼哈頓距離為|x1-y1|+|x2-y2|。⑥曼哈頓路徑。指片上網(wǎng)絡(luò)中任意兩節(jié)點間,距離長度等于橫向距離與縱向距離之和,即距離值等于曼哈頓距離的一條路徑。⑦曼哈頓路徑數(shù)。指片上網(wǎng)絡(luò)中任意兩節(jié)點間的曼哈頓路徑總數(shù),可由(1)式算出,即

其中,m表示NoC的行數(shù);n表示NoC的列數(shù)。

2 NoC測試

(1)針對NoC通訊架構(gòu)的測試方法。文獻(xiàn)[1]提出了用于測試2D-Mesh結(jié)構(gòu)NoC的可擴(kuò)展BIST方式,該方法幾乎適用于各種故障檢測,并能定位出故障點,根據(jù)反饋的故障信息,重新對整個NoC進(jìn)行配置;而文獻(xiàn)[2]則提出了針對2D-Mesh結(jié)構(gòu)中路由器里多路選擇器的外建自測試方法,該方法主要用于檢測多路選擇器和FIFO中存在的固定故障,以及延時故障、相鄰鏈路中的斷路和短路故障;對于非規(guī)則結(jié)構(gòu)的片上網(wǎng)絡(luò),文獻(xiàn)[3]提出了增加測試外殼,采用并行的測試方式,對片上網(wǎng)絡(luò)的路由器進(jìn)行測試。

(2)針對IP核的測試調(diào)度方法。文獻(xiàn)[4]提出了一種NoC測試端口位置和數(shù)量的優(yōu)化選取方法,既能高效地完成對核的測試,又能有效地避免因測試帶來的器件損壞;而文獻(xiàn)[5]提出的方法是基于IP核的優(yōu)先權(quán)調(diào)度,即一旦某個IP核獲得調(diào)度,就必須等到屬于該核的所有向量都施加完畢,才釋放所占用資源。

3 針對2D-Mesh通訊架構(gòu)的測試方法

3.1 基于洪泛的窮舉測試方法

文獻(xiàn)[6]提出了基于洪泛的窮舉測試方法,其思想是：借鑒普通通信網(wǎng)絡(luò)中的洪泛思想,即在片上網(wǎng)絡(luò)中,由測試訪問源節(jié)點發(fā)送一個數(shù)據(jù)包給其所有鄰接節(jié)點。而網(wǎng)絡(luò)中每個節(jié)點在接收到數(shù)據(jù)包后,將向除接收端口以外的所有端口,復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)包。為防止數(shù)據(jù)包在網(wǎng)絡(luò)中無限制地復(fù)制轉(zhuǎn)發(fā),數(shù)據(jù)包包頭被設(shè)置了跳數(shù)計數(shù)域,跳數(shù)值設(shè)為兩測試訪問節(jié)點間曼哈頓距離,即最短路徑所需的跳數(shù)。每經(jīng)過一個節(jié)點,跳數(shù)減1,然后復(fù)制轉(zhuǎn)發(fā)。當(dāng)跳數(shù)為零時,沒有到達(dá)目的節(jié)點則丟棄該數(shù)據(jù)包。

3.2 基于洪泛的偽窮舉測試方法

在基于洪泛的窮舉測試方法的基礎(chǔ)上,文獻(xiàn)[7]提出了基于洪泛的偽窮舉測試方法,其思想是：類似洪泛思想,只是每個通訊節(jié)點將它所接收到的數(shù)據(jù)包,同時以YX路由算法和XY路由算法向目的節(jié)點轉(zhuǎn)發(fā),所以每個節(jié)點只需要將所接收的數(shù)據(jù)包復(fù)制2份向其鄰接節(jié)點轉(zhuǎn)發(fā),這樣相對窮舉方法,可以降低功耗,縮短測試時間,但是網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包數(shù)量仍然較大。

3.3 功耗優(yōu)先的偽窮舉測試方法

由于NoC的電路規(guī)模十分巨大,其測試功耗比正常工作模式下的功耗高很多,因此如何降低或限制測試片上系統(tǒng)時的通訊功耗,就成為設(shè)計者設(shè)計測試方法時越來越關(guān)心的問題。文獻(xiàn)[8]指出：一個路由器的功耗主要分成3部分,即緩沖區(qū)功耗、控制邏輯功耗和交換開關(guān)功耗。其功耗計算公式為：

其中,m表示一個路由器中緩沖區(qū)的數(shù)量;n表示對整個片上網(wǎng)絡(luò)中對路由器的采樣數(shù);Pcrossbar為交換開關(guān)的功耗;Pcontrol為邏輯控制的功耗。

而2D-Mesh結(jié)構(gòu)中各路由器的結(jié)構(gòu)基本一致,在一個測試過程中只注入一個數(shù)據(jù)包,這樣各路由器轉(zhuǎn)發(fā)數(shù)據(jù)包內(nèi)容完全相同,其產(chǎn)生的功耗也一樣,因此可以得出測試過程中的總功耗跟網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包數(shù)量成正比。

從上述2種測試方法可以得出,測試方法決定整個網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)量,在整個測試過程中中間節(jié)點所產(chǎn)生的冗余數(shù)據(jù)包最多,因此本文提出了功耗優(yōu)先的偽窮舉測試方法。

要實現(xiàn)本方法,需要根據(jù)網(wǎng)絡(luò)中各節(jié)點的不同位置,將它們重新定義：

(1)邊緣節(jié)點。指2D-Mesh結(jié)構(gòu)中,鄰接節(jié)點數(shù)少于4的節(jié)點。在坐標(biāo)系中表現(xiàn)為X坐標(biāo)值等于0或n,或者Y坐標(biāo)值等于0或m。如圖2中坐標(biāo)值為(0,0)、(2,0)就是邊緣節(jié)點。

圖2 4×4的2D-Mesh結(jié)構(gòu)模型

(2)中間節(jié)點。指2D-Mesh結(jié)構(gòu)中,鄰接節(jié)點數(shù)為4的節(jié)點。在坐標(biāo)系中表現(xiàn)為X坐標(biāo)值大于0,且小于n,同時滿足Y坐標(biāo)值大于0,且小于m。如在圖2中節(jié)點坐標(biāo)值為(1,1)、(2,1)、(1,2)和(2,2)等節(jié)點均為中間節(jié)點。

(3)測試訪問節(jié)點。指與測試處理單元相連的節(jié)點,如在圖2中節(jié)點(0,0)、(3,3)被選為測試訪問節(jié)點 TAS(Test Access Switch,簡稱TAS)。

(4)基本思想。當(dāng)片上網(wǎng)絡(luò)處于測試狀態(tài)時,選取2個對角的邊緣節(jié)點為測試訪問節(jié)點TAS,同時以對方為目的節(jié)點發(fā)送數(shù)據(jù)包,每個節(jié)點接收到測試數(shù)據(jù)包后,判斷自己所處位置。如果是邊緣節(jié)點,則同時以XY和Y X 2種方式轉(zhuǎn)發(fā)數(shù)據(jù)包。如果是中間節(jié)點,則再判斷數(shù)據(jù)包來自哪個方向上端口。如果是來自X方向上,則采用XY路由算法轉(zhuǎn)發(fā);如果是來自Y方向上,則采用YX路由轉(zhuǎn)發(fā)。在到達(dá)目的節(jié)點后,所接收到的數(shù)據(jù)包數(shù)應(yīng)當(dāng)?shù)扔诒緶y試狀態(tài)下的對角邊緣節(jié)點間的曼哈頓路徑數(shù)。測試狀態(tài)下的對角邊緣節(jié)點曼哈頓路徑數(shù)計算公式為：

K(m,n)=m+n-2 (3)其中,m、n分別表示要測試2D-Mesh結(jié)構(gòu)NoC的行數(shù)和列數(shù)。如果電路中存在鏈路故障,則數(shù)據(jù)包數(shù)量將小于測試狀態(tài)下的曼哈頓路徑數(shù)。

3.4 節(jié)點所執(zhí)行的路由算法描述

對所要測試的片上網(wǎng)絡(luò),先任意選擇一個對角節(jié)點為坐標(biāo)原點。那么判斷一個節(jié)點S(Xs,Ys)位置的條件就是：當(dāng)|Xs|=0或n,或|Ys|=0或m時,S為邊緣節(jié)點;當(dāng)0＜|Xs|＜n,且0＜|Ys|＜m時,S為中間節(jié)點。其中,m為行數(shù);n為列數(shù);E、W 、S和N 分別表示東、西 、南、北4個方向的通道。

算法：測試狀態(tài)下,每個節(jié)點所執(zhí)行的路由算法。輸入：當(dāng)前節(jié)點坐標(biāo)(Xcurrent,Ycurrent)和目的節(jié)點坐標(biāo)(Xdest,Ydest)。輸出：選擇輸出的通道Channel。過程如下：

該算法的偽碼圖描述,如圖3所示。

圖3 算法偽碼圖

3.5 測試數(shù)據(jù)包總數(shù)的計算

本方法主要是基于節(jié)點在網(wǎng)絡(luò)中不同位置,而采取不同路由算法的。計算數(shù)據(jù)包總數(shù)分成如下2個部分。

(1)計算邊緣節(jié)點產(chǎn)生的數(shù)據(jù)包總數(shù)?，F(xiàn)在以圖2所示的2個對角邊緣節(jié)點為例,該節(jié)點接收到數(shù)據(jù)包后,X、Y坐標(biāo)值為0的邊緣節(jié)點,向目的節(jié)點以XY和YX路由算法同時復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)包,可推導(dǎo)出(4)式。但是X坐標(biāo)值為n和Y坐標(biāo)值為m的邊緣節(jié)點,與目的節(jié)點同行或同列,則只執(zhí)行XY或YX算法。這樣可推導(dǎo)出(5)式,即

(2)計算中間節(jié)點產(chǎn)生的數(shù)據(jù)包。邊緣節(jié)點在XY方向轉(zhuǎn)發(fā)的數(shù)據(jù)包和在Y X方向的數(shù)據(jù)包都要經(jīng)過中間節(jié)點,而且這些數(shù)據(jù)包均只復(fù)制一份轉(zhuǎn)發(fā)。這樣,根據(jù)中間節(jié)點區(qū)域的規(guī)模大小可計算得出數(shù)據(jù)包總數(shù)為：

測試處理單元向測試訪問節(jié)點發(fā)送一份數(shù)據(jù)包,同時由于2個測試訪問節(jié)點是互為目的節(jié)點對發(fā)數(shù)據(jù)包,最終得到一個測試過程中所產(chǎn)生的數(shù)據(jù)包總數(shù)的計算公式為：

4 實驗結(jié)果比較

本文方法是在OPNET仿真平臺上進(jìn)行模擬并得出實驗結(jié)果的,文獻(xiàn)[9]介紹了怎樣使用OPENET作為NoC的仿真平臺,現(xiàn)從以下幾個方面評價本文方法。

4.1 測試數(shù)據(jù)包數(shù)量的統(tǒng)計

采用基于洪泛的偽窮舉測試方法和功耗優(yōu)先的偽窮舉測試方法比較,如圖4所示。

圖4 采用2種方法所產(chǎn)生的測試數(shù)據(jù)包總數(shù)比較

從圖4可以看出,隨著NoC的規(guī)模增大,本方法所產(chǎn)生的數(shù)據(jù)包總數(shù)增長得較為緩慢,而基于洪泛的偽窮舉測試方法,則隨著片上網(wǎng)絡(luò)規(guī)模增大,所產(chǎn)生的數(shù)據(jù)包數(shù)量增長較快。這說明本方法在測試過程中產(chǎn)生數(shù)據(jù)包數(shù)量較少,有效地減少了冗余的測試數(shù)據(jù)包。

4.2 測試功耗

文獻(xiàn)[10]指出,對于2D-Mesh結(jié)構(gòu)的NoC,其總通訊功耗是最小的,而在2個節(jié)點之間發(fā)送每一位數(shù)據(jù)所需的平均功耗是由其曼哈頓距離決定的。這樣,可以用交換數(shù)據(jù)包數(shù)量和通過的路徑長度估算出功耗大小,其計算公式為：

其中,e表示從一個通訊節(jié)點向它的鄰節(jié)點發(fā)送一個數(shù)據(jù)包所需要的平均功耗,可以由(2)式計算得出。

采用2種測試方法在不同規(guī)模NoC中所產(chǎn)生功耗的比較,見表1所列。

表1 2種測試方法在不同規(guī)模NoC中所產(chǎn)生功耗的比較

本文所提出的方法正是以降低測試功耗為優(yōu)先考慮的目標(biāo),通過減少產(chǎn)生多余的測試數(shù)據(jù)包數(shù)量,達(dá)到降低總測試功耗的目的。從圖4可以看出,在網(wǎng)絡(luò)中分別采用了偽窮舉測試方法和功耗優(yōu)先的偽窮舉測試方法,所產(chǎn)生總測試數(shù)據(jù)包數(shù)有較大差別,而表1所列則反映了2種方法在測試功耗上的差別。本文提出的測試方法在測試功耗方面有了很大的降低,隨著NoC規(guī)模的增大,降低得越多。這是因為在網(wǎng)絡(luò)中產(chǎn)生的復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)包得到了有效減少,從而降低整個網(wǎng)絡(luò)中的測試功耗。

4.3 測試時間

根據(jù)基于洪泛的偽窮舉測試方法中的定義,測試時間的計算是從一個測試訪問節(jié)點發(fā)送一個數(shù)據(jù)包開始,到最后一個測試數(shù)據(jù)包被目的節(jié)點接收。文獻(xiàn)[7]給出測試時間的計算公式為：

從(9)式可以看出,整個片上網(wǎng)絡(luò)的測試通訊功耗與產(chǎn)生的復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)包成正比,數(shù)據(jù)包總數(shù)越少,總測試功耗就越低。

采用基于洪泛的偽窮舉測試方法和本文所提出的功耗優(yōu)先的偽窮舉測試方法,對不同規(guī)模NoC測試所需時間的比較,如圖5所示。從圖5可以看出,本文所提出的方法比基于洪泛的偽窮舉方法所需要的時間有較大的減少,并且隨著NoC的規(guī)模增大,減少就更多。

圖5 測試時間的比較

4.4 對比分析

基于洪泛的偽窮舉測試方法,是讓每個節(jié)點都采取同一種方式轉(zhuǎn)發(fā),即同時以XY和YX路由算法轉(zhuǎn)發(fā)數(shù)據(jù)包,這樣中間節(jié)點就會產(chǎn)生很多的冗余數(shù)據(jù)包,其包總數(shù)計算公式為：

而本文所提出的方法,把整個網(wǎng)絡(luò)劃分成邊緣節(jié)點區(qū)和中間節(jié)點區(qū)。邊緣節(jié)點在接收到數(shù)據(jù)包后,同時以XY和Y X路由算法向目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包,而中間節(jié)點經(jīng)過端口判斷后,再執(zhí)行相應(yīng)的路由算法發(fā)送。這樣由邊緣節(jié)點控制數(shù)據(jù)包走向,中間節(jié)點判斷后,再轉(zhuǎn)發(fā)1份數(shù)據(jù)包。其中間節(jié)點產(chǎn)生數(shù)據(jù)包數(shù)就大大減少,整個網(wǎng)絡(luò)中數(shù)據(jù)包總數(shù)也得到減少,這可由(7)式計算得出。所以,本方法在降低測試功耗方面有顯著改善。

5 結(jié) 論

NoC這種新體系結(jié)構(gòu)的提出,解決了總線結(jié)構(gòu)中存在的問題,對其測試也與總線結(jié)構(gòu)SoC所采用的方法有所不同。而其中2D-Mesh結(jié)構(gòu)特點是,整個網(wǎng)絡(luò)的總功耗跟網(wǎng)絡(luò)中所產(chǎn)生數(shù)據(jù)包的數(shù)量成正比,因此本文的基本思想是采用合理的測試方法,在保證測試效果的同時,使整個網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)包總數(shù)降低,從而降低了總功耗。

[1]Petersen K,Oberg J.T oward a scalable test methodology for 2D-mesh network-on-chips[C]//Design Automation and Test in Europe (DAT E).Nice, France,2007：367-372.

[2]Raik J,Govind V,Ubar R.An external test approach for network-on-a-chip switches[C]//15th Asian Test Symposium(AT S).Fukuoka,Japan,2006：437-442.

[3]Hosseinabady M,Banaiyan A,Bojnordi M N,et al.A concurrent testing method for NoC switches[C]//Design Automation and Test in Europe(DATE).Munich,Germany,2006：1171-1176.

[4]歐陽一鳴,馮 偉,梁華國.功耗限制下的NoC測試端口的優(yōu)化選擇方法[J].計算機(jī)應(yīng)用,2008,28(4)：204-206,209.

[5]Cota E,Liu C.Constraint-driven test scheduling for NoC-based systems[J].IEEE T ransactions on Computer-Aided Desig n of Integrated Circuits and Systems,2006,25(11)：2465-2478.

[6]Sedghi M,Koopahi E,Alaghi A,et al.An ex haustive test strategy based on flooding routing fo r NoC switch testing[C]//IEEE East-WestDesign and TestSymposium(EWDTS).Yerevan,A rmenia,2007：262-267.

[7]Sedg hi M,Koopahi E,Alaghi A,et al.An NoC test strategy based on flooding with power,test time and coverage considerations[C]//V LSID 2008,21st International Conference.Hyderabad,India,2008：409-414.

[8]Guindani G,Reinbrecht C,Raupp T,et al.NoC power estimation at the RT L abstraction level[C]//IEEE Computer Society Annual Symposium on VLSI.Montpellier,France,2008：475-478.

[9]Wu Ning,Ge Fen,Wang Qi.Simulation and performance analysis of network on chip architectures using OPNET[C]//7th International Conference on ASIC.Guilin,China,2007：1285-1288.

[10]Hu J,Marculescu R.Energy-and performance-aware mapping for regular NoC architectures[J].IEEE T ransactions on Computer-Aided Desig n of ICs and Systems,2005,24(4)：551-562.