李洋，呂瑞

（長春理工大學(xué)　電子信息工程學(xué)院，長春　130022）

基于可重構(gòu)容錯(cuò)路由的片上網(wǎng)絡(luò)負(fù)載均衡

李洋，呂瑞

（長春理工大學(xué)電子信息工程學(xué)院，長春130022）

基于內(nèi)建自測(cè)技術(shù)，通過判斷故障節(jié)點(diǎn)信息，提出了一種片上網(wǎng)絡(luò)可重構(gòu)容錯(cuò)路由優(yōu)化算法。算法根據(jù)故障節(jié)點(diǎn)的位置在網(wǎng)絡(luò)中設(shè)立判斷點(diǎn)和有效轉(zhuǎn)向點(diǎn)，以減少在重構(gòu)環(huán)路上的負(fù)載，在完成路由容錯(cuò)優(yōu)化的同時(shí)實(shí)現(xiàn)了負(fù)載均衡。在OPNET仿真平臺(tái)上，采用均勻流量模式，對(duì)比了該算法與RRA算法在兩種2D-mesh網(wǎng)絡(luò)中的性能，實(shí)驗(yàn)結(jié)果表明，提出算法在平均時(shí)延和吞吐率方面具有顯著優(yōu)勢(shì)，并且與5×5網(wǎng)絡(luò)相比，7×7規(guī)模的NoC中隨著網(wǎng)絡(luò)注入率的增加延時(shí)優(yōu)化愈加明顯。

片上網(wǎng)絡(luò)；可重構(gòu)；容錯(cuò)路由；負(fù)載均衡

為了適應(yīng)通信復(fù)雜度的需求，片上網(wǎng)絡(luò)（Network-on-Chip，NoC）成為當(dāng)前片上多核的標(biāo)準(zhǔn)通信架構(gòu)。在數(shù)據(jù)傳輸?shù)倪^程中，一旦網(wǎng)絡(luò)芯片存在局部故障，與之相連的通信節(jié)點(diǎn)周圍鏈路就會(huì)失效，無法完成源節(jié)點(diǎn)與目的節(jié)點(diǎn)的有效通信［1-3］。為了確保數(shù)據(jù)傳輸?shù)腝oS，片上網(wǎng)絡(luò)容錯(cuò)路由算法已成為當(dāng)前片上網(wǎng)絡(luò)的研究熱點(diǎn)［4］。文獻(xiàn)［5］提出了一種基于內(nèi)建自測(cè)（Built In Self Test，BIST）機(jī)制的分布式可重構(gòu)容錯(cuò)路由算法（Reconfigurable Routing Algorithm，RRA），它的設(shè)計(jì)思想是在無障礙區(qū)域采用XY路由方式，在障礙區(qū)域通過重構(gòu)環(huán)路選用基于Turn Model模型的特定繞行路徑進(jìn)行分組傳輸。本文以容錯(cuò)路由算法為切入點(diǎn)，基于BIST機(jī)制，對(duì)2D Mesh片上網(wǎng)絡(luò)的容錯(cuò)路由算法進(jìn)行改進(jìn)和優(yōu)化。

1　故障節(jié)點(diǎn)模型

對(duì)于2D Mesh拓?fù)浣Y(jié)構(gòu)，單一的NoC故障節(jié)點(diǎn)通常被劃分為三種情況，如圖1所示的6×6網(wǎng)格中，故障節(jié)點(diǎn)分別處于Mesh結(jié)構(gòu)的內(nèi)部、邊緣以及頂端，用F表示。由于F與其它節(jié)點(diǎn)直接相連的鏈路失效，為確保數(shù)據(jù)有效傳輸，數(shù)據(jù)流應(yīng)繞過F點(diǎn)，并選擇與之臨近的節(jié)點(diǎn)形成重構(gòu)環(huán)路。這里用E、W、S、N表示F點(diǎn)直接相鄰的節(jié)點(diǎn)，分別代表東、西、南、北四個(gè)方位，NE表示重構(gòu)環(huán)路上東北角的通信節(jié)點(diǎn)，對(duì)其它節(jié)點(diǎn)的表示以此類推。現(xiàn)有算法對(duì)于位于網(wǎng)絡(luò)邊緣和頂端的故障節(jié)點(diǎn)的容錯(cuò)處理具有良好的網(wǎng)絡(luò)性能，但是很多文獻(xiàn)對(duì)于網(wǎng)絡(luò)內(nèi)部故障節(jié)點(diǎn)處理，為了避免死鎖，引起了負(fù)載不均衡，犧牲了網(wǎng)絡(luò)性能。當(dāng)F點(diǎn)在Mesh結(jié)構(gòu)的內(nèi)部時(shí)，重構(gòu)環(huán)路的路線形成閉合路徑，具體情況如圖2所示。

圖1　D-Mesh單故障節(jié)點(diǎn)NoC模型

圖2　2D-Mesh NoC內(nèi)部節(jié)點(diǎn)故障繞行

圖2中虛線表示在NoC中無故障節(jié)點(diǎn)的路徑線路，實(shí)線表示出現(xiàn)故障節(jié)點(diǎn)的路徑線路，由于重構(gòu)環(huán)路的閉合性，該算法通過限制由北向西和由東向南兩個(gè)方向的轉(zhuǎn)彎，即Turn Model模型中的NW和ES這兩個(gè)轉(zhuǎn)向，來防止出現(xiàn)死鎖。故障節(jié)點(diǎn)出現(xiàn)在網(wǎng)絡(luò)內(nèi)部時(shí)，由于算法RRA在重構(gòu)環(huán)路上禁止了NW和ES的轉(zhuǎn)向，加重了重構(gòu)環(huán)路上左半環(huán)的負(fù)載，尤其在網(wǎng)絡(luò)數(shù)據(jù)流量較大時(shí)，容易引起環(huán)路阻塞，使NoC的性能受損。本文以此為研究基礎(chǔ)，構(gòu)建新的容錯(cuò)策略，優(yōu)化路由算法，提高網(wǎng)絡(luò)性能。

2　NoC可重構(gòu)容錯(cuò)路由算法優(yōu)化設(shè)計(jì)

當(dāng)網(wǎng)絡(luò)內(nèi)部出現(xiàn)故障節(jié)點(diǎn)，容錯(cuò)策略主要體現(xiàn)在X和Y維兩個(gè)方向上的傳輸繞行。這里以一個(gè)6×6的2D-Mesh網(wǎng)絡(luò)結(jié)構(gòu)為例，如圖3所示，s和d分別代表源節(jié)點(diǎn)和目的節(jié)點(diǎn)。針對(duì)X維方向，s和d分別位于F點(diǎn)東西兩個(gè)方位，且s和d與F的相對(duì)位置坐標(biāo)滿足xs＞xF，yF-1≤ys＜yF+1且xd≤xF，yd＞yF，從s1到d1的數(shù)據(jù)傳輸，基于算法RRA，由于限制了在重構(gòu)環(huán)路上的NW轉(zhuǎn)向，s1需要在X維上繞過重構(gòu)環(huán)路的左半環(huán)才能抵達(dá)接收端。

圖3　RRA算法的繞行實(shí)例

另外，從s2到d2的數(shù)據(jù)傳輸同樣增加了在重構(gòu)環(huán)路的負(fù)載。針對(duì)Y維繞行，s和d分別位于F的南北兩個(gè)方位，與F的相對(duì)位置坐標(biāo)滿足ys＞yF+1，yd＜yF或 ys＜yF-1，yd＞yF且d與F在同一列上，從s3到d3的數(shù)據(jù)傳輸，依照RRA算法，s3需要先以XY算法路由至F點(diǎn)以北臨近的節(jié)點(diǎn)，然后沿重構(gòu)環(huán)路的左半環(huán)繞行傳送至目的節(jié)點(diǎn)。同樣，從s4到d4的數(shù)據(jù)傳輸先以XY維序路由算法抵達(dá)d4所在列，當(dāng)傳至S點(diǎn)時(shí)，遇到故障節(jié)點(diǎn)F，同樣需要沿重構(gòu)環(huán)路的左半環(huán)繞行傳送至目的節(jié)點(diǎn)。由此可以看出，為了避免重構(gòu)環(huán)路上的死鎖，在網(wǎng)絡(luò)內(nèi)部禁止了重構(gòu)環(huán)路上NW和ES的轉(zhuǎn)向，在一定程度上增加了在重構(gòu)環(huán)路的負(fù)載。為緩解網(wǎng)絡(luò)負(fù)載不均衡，根據(jù)數(shù)據(jù)流的不同狀態(tài)，在網(wǎng)絡(luò)中設(shè)置有效轉(zhuǎn)向點(diǎn)，打破算法RRA中絕對(duì)的左轉(zhuǎn)向繞行，同時(shí)通過在NoC中設(shè)置判斷點(diǎn)，當(dāng)分組到達(dá)判斷點(diǎn)時(shí)，通過增加優(yōu)化重構(gòu)環(huán)上的傳輸路徑使網(wǎng)絡(luò)性能得以優(yōu)化，具體措施如下：針對(duì)X維傳輸繞行進(jìn)行容錯(cuò)優(yōu)化，如圖4（a）所示的網(wǎng)絡(luò)中，判斷點(diǎn)設(shè)置在（xF+2，yF-1）和xF+2，yF兩個(gè)節(jié)點(diǎn)，分別用H1和H2表示。有效轉(zhuǎn)向點(diǎn)設(shè)為（xF+2，yF+1），用T表示。優(yōu)化的路由策略為：分組傳輸至判斷點(diǎn)時(shí)，由d的方位選擇路徑，如果目的節(jié)點(diǎn)X維坐標(biāo)符合xd≤xF，yd＞yF，則分組沿Y維傳送至T點(diǎn)，抵達(dá)后的分組避開了重構(gòu)環(huán)路的熱點(diǎn)區(qū)域，減小了左半環(huán)路的負(fù)載，然后再由XY路由傳送至目的節(jié)點(diǎn)。在其它的情況下，路由策略與RRA相同。值得一提的是，當(dāng)在T點(diǎn)（xF+2，yF+1）允許分組轉(zhuǎn)向后，在分組傳送時(shí)，容易在以T、NW、SW、H2這些頂點(diǎn)構(gòu)建的四邊區(qū)域產(chǎn)生逆時(shí)針的閉合環(huán)，繼而引發(fā)死鎖。這里沿用文獻(xiàn)［6］的方法，基于Turn Model模型，在此閉合環(huán)中禁止H2點(diǎn)EN的轉(zhuǎn)向來防止死鎖現(xiàn)象。對(duì)于需要在H2點(diǎn)進(jìn)行EN轉(zhuǎn)向的數(shù)據(jù)流，重新分配路徑。修改如下：（1）若xs＜xF，分組在重構(gòu)環(huán)上順向傳送至NE點(diǎn)，然后由XY路由至相應(yīng)節(jié)點(diǎn)。（2）若xs=xF或xs=xF+1，分組在重構(gòu)環(huán)上逆向傳送至NE點(diǎn)，然后由XY路由至相應(yīng)節(jié)點(diǎn)。

圖4　網(wǎng)絡(luò)內(nèi)部故障節(jié)點(diǎn)容錯(cuò)優(yōu)化

在圖4（a）中可以看到從s1到d1和s2到d2的數(shù)據(jù)傳輸路徑得到優(yōu)化，從s1到d1的路由跳數(shù)由原來的8跳減到6跳，并且緩解了重構(gòu)環(huán)上的負(fù)載，同樣，圖（a）中的另一條線路s2到d2，當(dāng)傳送至判斷點(diǎn)H2后，由路由信息改變的繞行路徑避開了重構(gòu)環(huán)的熱點(diǎn)區(qū)域，緩解了重構(gòu)環(huán)上的負(fù)載。針對(duì)Y維繞行，如圖4（b）所示的網(wǎng)絡(luò)中，設(shè)置判斷點(diǎn)和有效轉(zhuǎn)向點(diǎn)，在這里判斷點(diǎn)H的位置設(shè)為四種類型，分別是：（1） xH=xF-1，yH＞yF+1；（2）xH=xF+1，yH＞yF +1（3）xH=xF-1，yH＜yF-1；（4）xH=xF+1，yH＜yF-1；（5）xH=xF+2，yH＜yF-1，有效轉(zhuǎn)向點(diǎn)T為（xF+2，yF+1）。優(yōu)化的路由策略為：若H點(diǎn)滿足條件（1），且滿足xd=xF，yd＜yF，則分組沿Y維向S（南）通道轉(zhuǎn)發(fā)至NW，然后根據(jù)算法RRA傳送分組到目的節(jié)點(diǎn)；若H點(diǎn)滿足條件（2），且滿足xd=xF，yd＜yF，則分組沿Y維即向S（南）通道轉(zhuǎn)發(fā)至NE，然后在算法RRA下傳送至接收端；若H點(diǎn)滿足條件（3），且滿足xd＜xF，yd＞yF，則分組沿Y維向N（北）通道轉(zhuǎn)發(fā)至SW，然后在算法RRA下傳送至接收端；若H點(diǎn)滿足條件（4），且滿足xd＜xF，yd＞yF，則分組在XY算法下傳送至有效轉(zhuǎn)向點(diǎn)T為，然后繼續(xù)在XY算法下傳送至接收端；若H點(diǎn)滿足條件（5），且d點(diǎn)坐標(biāo)滿足xF-1≤xd≤xF+1，yd＞yF+1，則分組沿Y維即向N（北）通道轉(zhuǎn)發(fā)至有效轉(zhuǎn)向點(diǎn)T，然后繼續(xù)依據(jù)XY算法完成分組傳輸。當(dāng)數(shù)據(jù)分組達(dá)到判斷點(diǎn)時(shí)，如果不滿足上述5種情況，則繼續(xù)沿XY算法傳輸在圖4（b）可以看到從s3到d3和s4到d4的數(shù)據(jù)傳輸路徑得到優(yōu)化，從s3到d3的路由跳數(shù)由原來的8跳減到6跳，從s4到d4的路由跳數(shù)由原來的9跳減到7跳，在減小網(wǎng)絡(luò)路徑延時(shí)的同時(shí)減輕了傳輸鏈路重構(gòu)環(huán)上的負(fù)載。針對(duì)以上優(yōu)化策略，在NoC運(yùn)行的時(shí)候，通過BIST機(jī)制判斷每一節(jié)點(diǎn)周邊節(jié)點(diǎn)是否是F點(diǎn)，由通信節(jié)點(diǎn)與F點(diǎn)的相對(duì)位置確定重構(gòu)環(huán)路、有效轉(zhuǎn)向點(diǎn)T以及駐點(diǎn)H的信息。

3　容錯(cuò)算法無死鎖驗(yàn)證

對(duì)單故障節(jié)點(diǎn)2D-Mesh的NoC構(gòu)造一個(gè)有向圖I=G（N，C），如圖5（a）所示，結(jié)構(gòu)中的集合N和C分別代表節(jié)點(diǎn)間的鏈路。故障點(diǎn)F定義在（c，d）處，通信節(jié)點(diǎn)間的鏈路C=｛｝X，Y，X和Y是鏈路上橫向和豎向的路線集，分別用+、-的符號(hào)代表路線的傳輸方向，其余通信節(jié)點(diǎn)由F點(diǎn)的方位確定各自坐標(biāo)，在橫向上由西向東遞增，在豎向上由南向北遞增。由此對(duì)于節(jié)點(diǎn)n（c-1，d-1）來說，它的四條通道分別表示為 x+（c-1，d-1），x-（c-1，d-1），y+（c-1，d-1）和y-（c-1，d-1）。圖5（b）是優(yōu)化算法映射的CDG。依據(jù)死鎖定理可知若在映射的CDG中不存在環(huán)路，則路由算法R即為無死鎖的。在圖5（b）所示的CDG中，限制了由x+（c，d+1）至y-（c+1，d）和x+（c+1，d-1）至y+（c+2，d-1）的轉(zhuǎn)向，同時(shí)增添由y+（c+1，d）至 x+（c-1，d-1）和 y+（c+2，d）至 x-（c+1，d+1）的轉(zhuǎn)向。由圖中所示的CDG可以看出，沿任一通道開始都沒有構(gòu)成環(huán)路，本文對(duì)算法RRA優(yōu)化的容錯(cuò)策略是沒有死鎖的。

圖5　2D-Mesh拓?fù)涞腘oC連接圖和優(yōu)化算法下的CDG

4　實(shí)驗(yàn)設(shè)置與性能分析

4.1仿真配置

在OPNET平臺(tái)上，分別搭建5×5和7×7的2D-Mesh拓?fù)浣Y(jié)構(gòu)的NoC，修改網(wǎng)絡(luò)參數(shù)和路由算法，并在網(wǎng)絡(luò)內(nèi)部設(shè)立故障節(jié)點(diǎn)，同時(shí)修改其對(duì)應(yīng)的雙向鏈路參數(shù)，使故障節(jié)點(diǎn)完全失效。假設(shè)NoC兼具 BIST機(jī)制，通信節(jié)點(diǎn)能夠判斷出相鄰?fù)ㄐ殴?jié)點(diǎn)的狀態(tài)信息。交換機(jī)制采用蟲孔交換機(jī)制，仿真環(huán)境中數(shù)據(jù)是以flit為基本的流控單元形式進(jìn)行傳輸，每個(gè)數(shù)據(jù)包由8個(gè)flit組成，且每個(gè)flit是32bits。采用均勻流量模式，網(wǎng)絡(luò)注入率的單位為flit/cycle/ node，表示每一通信節(jié)點(diǎn)在每一cycle內(nèi)向NoC中注入的flit數(shù)值。對(duì)本文中優(yōu)化的容錯(cuò)算法與在文獻(xiàn)［5］中的提出的算法RRA在延時(shí)和吞吐率方面進(jìn)行比較。圖6分別給出了5×5和7×7兩種不同規(guī)模的時(shí)延和吞吐率性能比較，這里隨機(jī)設(shè)置一個(gè)網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)為故障節(jié)點(diǎn)。由于在相對(duì)較大規(guī)模的NoC中，被優(yōu)化的通信節(jié)點(diǎn)增多，相比5×5，在7×7規(guī)模的NoC中優(yōu)化的算法在時(shí)延和方面的優(yōu)勢(shì)更加明顯，隨著網(wǎng)絡(luò)注入率的增加延時(shí)優(yōu)化愈加明顯，當(dāng)注入率達(dá)到0.6flit/cycle/node時(shí)，5×5網(wǎng)絡(luò)中，時(shí)延減少10.2%，而在7×7網(wǎng)絡(luò)中時(shí)延減少19.3%。但在網(wǎng)絡(luò)吞吐率方面5×5網(wǎng)絡(luò)優(yōu)化效果更明顯，在5×5和7×7網(wǎng)絡(luò)中當(dāng)注入率達(dá)到0.40.6flit/cycle/node的峰值吞吐率分別增加11.3%和7.1%。

4.2仿真結(jié)果分析

圖6　5×5和7×7兩種拓?fù)浣Y(jié)構(gòu)下NoC內(nèi)部故障節(jié)點(diǎn)平均時(shí)延和吞吐率對(duì)比

5　結(jié)論

本文在BIST機(jī)制的基礎(chǔ)上，針對(duì)位于網(wǎng)絡(luò)內(nèi)部的故障節(jié)點(diǎn)，通過判斷節(jié)點(diǎn)故障信息，根據(jù)故障的位置在網(wǎng)絡(luò)中設(shè)立判斷點(diǎn)和有效轉(zhuǎn)向點(diǎn)，在減少在重構(gòu)環(huán)路上通信節(jié)點(diǎn)的負(fù)載同時(shí)完成路由算法優(yōu)化設(shè)計(jì)。在OPNET仿真平臺(tái)上完成網(wǎng)絡(luò)元素配置，在均勻流量模式下，在5×5和7×7 2D Mesh兩種網(wǎng)絡(luò)規(guī)模上實(shí)現(xiàn)了算法仿真，獲得了平均時(shí)延和吞吐率兩項(xiàng)性能指標(biāo)，與RRA算法相比本文算法在一定程度上提升了網(wǎng)絡(luò)性能。

［1］郭志海.片上網(wǎng)絡(luò)容錯(cuò)路由算法的研究與實(shí)現(xiàn)［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2014.

［2］Pasricha S，Zou Y.NS-FTR：a fault tolerant routing scheme for networks on chip with permanent and runtime intermittent faults［C］.Design Automation Conference（ASP-DAC），2011 16th Asia and South Pacific.IEEE，2011：443-448.

［3］丁同柱.NoC中規(guī)則網(wǎng)格及非規(guī)則網(wǎng)格結(jié)構(gòu)的路由方法研究［D］.合肥：合肥工業(yè)大學(xué)，2012.

［4］Ville Rantala.Network on chip routing algorithms ［R］.TUCS Technical Report，2006：10-12.

［5］Zhang Z，Greiner A，Taktak S.A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip［C］.IEEE Design Automation Conference，2008：441-446.

［6］姚磊.片上網(wǎng)路無虛通道容錯(cuò)路由技術(shù)研究［D］.西安：西安電子科技大學(xué)，2014.

Payload Balance for NoC Based on a Reconfigurable Fault Routing Algorithm

LI Yang，LV Rui
（School of Electronic and Information Technology，Changchun University of Science and Technology，Changchun 130022）

An optimized fault routing algorithm is supposed for Network on Chip Based on Built In Self Test by judging information about the fault node.A judgment node and a turning node are set up for decreasing the payload in the reconfigurable loop routing according to the position of the fault node，we made payload balanced while completed fault optimization.We got the delay and throughput data for 2 kinds of 2D-mesh NoC by means of OPNET simulation platform，the Experiment’s results show the advantage of the supposed algorithm，and more optimized network performance can be achieved in the 7×7 than 5×5 network.

network on chip（NoC）；reconfigurable；fault routing；payload balance

TP393

A

1672-9870（2016）03-0032-04

2016-01-20

李洋（1978-），女，博士，副教授，E-mail：lyang@cust.edu.cn