功耗優(yōu)先的NoC通訊架構(gòu)測試方法

歐陽一鳴, 黃 河, 梁華國

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

傳統(tǒng)基于共享總線的片上系統(tǒng),其通訊能力已經(jīng)不能滿足未來SoC(System on Chip,簡稱SoC)設(shè)計(jì)的要求。為此,計(jì)算機(jī)網(wǎng)絡(luò)通訊技術(shù)被移植到芯片設(shè)計(jì)中來,以分組交換作為基本通訊技術(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é)點(diǎn)。就是對片上網(wǎng)絡(luò)中路由器的簡稱。②數(shù)據(jù)包。網(wǎng)絡(luò)中傳輸?shù)南⑼ǔＳ深^部、傳輸數(shù)據(jù)和尾組成。由于通訊效率的需要,再將傳輸數(shù)據(jù)分割成更小的數(shù)據(jù)段,在測試模式下,測試向量加上包頭包尾封裝成一個(gè)數(shù)據(jù)包。③XY路由算法?；舅枷胧菙?shù)據(jù)包在向目的節(jié)點(diǎn)發(fā)送的過程中,先在X方向上發(fā)送,等到達(dá)目的節(jié)點(diǎn)所在列后,再在Y方向上發(fā)送直至到達(dá)目的節(jié)點(diǎn)。④Y X路由算法?；舅枷胧菙?shù)據(jù)包在向目的節(jié)點(diǎn)發(fā)送的過程中,先在Y方向上傳送,然后再在X方向上傳送。⑤曼哈頓距離。假設(shè)片上網(wǎng)絡(luò)中節(jié)點(diǎn)P1坐標(biāo)為(x1,y1),節(jié)點(diǎn)P2坐標(biāo)為(x2,y2),那么該對節(jié)點(diǎn)間的曼哈頓距離為|x1-y1|+|x2-y2|。⑥曼哈頓路徑。指片上網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間,距離長度等于橫向距離與縱向距離之和,即距離值等于曼哈頓距離的一條路徑。⑦曼哈頓路徑數(shù)。指片上網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)間的曼哈頓路徑總數(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方式,該方法幾乎適用于各種故障檢測,并能定位出故障點(diǎn),根據(jù)反饋的故障信息,重新對整個(gè)NoC進(jìn)行配置;而文獻(xiàn)[2]則提出了針對2D-Mesh結(jié)構(gòu)中路由器里多路選擇器的外建自測試方法,該方法主要用于檢測多路選擇器和FIFO中存在的固定故障,以及延時(shí)故障、相鄰鏈路中的斷路和短路故障;對于非規(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)度,即一旦某個(gè)IP核獲得調(diào)度,就必須等到屬于該核的所有向量都施加完畢,才釋放所占用資源。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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é)點(diǎn)所執(zhí)行的路由算法描述

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

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

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

圖3 算法偽碼圖

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果比較

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

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

采用基于洪泛的偽窮舉測試方法和功耗優(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個(gè)節(jié)點(diǎn)之間發(fā)送每一位數(shù)據(jù)所需的平均功耗是由其曼哈頓距離決定的。這樣,可以用交換數(shù)據(jù)包數(shù)量和通過的路徑長度估算出功耗大小,其計(jì)算公式為：

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

采用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ī)模的增大,降低得越多。這是因?yàn)樵诰W(wǎng)絡(luò)中產(chǎn)生的復(fù)制轉(zhuǎn)發(fā)數(shù)據(jù)包得到了有效減少,從而降低整個(gè)網(wǎng)絡(luò)中的測試功耗。

4.3 測試時(shí)間

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

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

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

圖5 測試時(shí)間的比較

4.4 對比分析

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

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

5 結(jié) 論

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