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

李洋，呂瑞

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

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

李洋，呂瑞

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

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

片上網(wǎng)絡(luò)；可重構(gòu)；容錯路由；負(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é)點周圍鏈路就會失效，無法完成源節(jié)點與目的節(jié)點的有效通信［1-3］。為了確保數(shù)據(jù)傳輸?shù)腝oS，片上網(wǎng)絡(luò)容錯路由算法已成為當(dāng)前片上網(wǎng)絡(luò)的研究熱點［4］。文獻(xiàn)［5］提出了一種基于內(nèi)建自測（Built In Self Test，BIST）機(jī)制的分布式可重構(gòu)容錯路由算法（Reconfigurable Routing Algorithm，RRA），它的設(shè)計思想是在無障礙區(qū)域采用XY路由方式，在障礙區(qū)域通過重構(gòu)環(huán)路選用基于Turn Model模型的特定繞行路徑進(jìn)行分組傳輸。本文以容錯路由算法為切入點，基于BIST機(jī)制，對2D Mesh片上網(wǎng)絡(luò)的容錯路由算法進(jìn)行改進(jìn)和優(yōu)化。

1　故障節(jié)點模型

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

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

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

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

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

當(dāng)網(wǎng)絡(luò)內(nèi)部出現(xiàn)故障節(jié)點，容錯策略主要體現(xiàn)在X和Y維兩個方向上的傳輸繞行。這里以一個6×6的2D-Mesh網(wǎng)絡(luò)結(jié)構(gòu)為例，如圖3所示，s和d分別代表源節(jié)點和目的節(jié)點。針對X維方向，s和d分別位于F點東西兩個方位，且s和d與F的相對位置坐標(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算法的繞行實例

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

圖4　網(wǎng)絡(luò)內(nèi)部故障節(jié)點容錯優(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)傳送至判斷點H2后，由路由信息改變的繞行路徑避開了重構(gòu)環(huán)的熱點區(qū)域，緩解了重構(gòu)環(huán)上的負(fù)載。針對Y維繞行，如圖4（b）所示的網(wǎng)絡(luò)中，設(shè)置判斷點和有效轉(zhuǎ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)向點T為（xF+2，yF+1）。優(yōu)化的路由策略為：若H點滿足條件（1），且滿足xd=xF，yd＜yF，則分組沿Y維向S（南）通道轉(zhuǎn)發(fā)至NW，然后根據(jù)算法RRA傳送分組到目的節(jié)點；若H點滿足條件（2），且滿足xd=xF，yd＜yF，則分組沿Y維即向S（南）通道轉(zhuǎn)發(fā)至NE，然后在算法RRA下傳送至接收端；若H點滿足條件（3），且滿足xd＜xF，yd＞yF，則分組沿Y維向N（北）通道轉(zhuǎn)發(fā)至SW，然后在算法RRA下傳送至接收端；若H點滿足條件（4），且滿足xd＜xF，yd＞yF，則分組在XY算法下傳送至有效轉(zhuǎn)向點T為，然后繼續(xù)在XY算法下傳送至接收端；若H點滿足條件（5），且d點坐標(biāo)滿足xF-1≤xd≤xF+1，yd＞yF+1，則分組沿Y維即向N（北）通道轉(zhuǎn)發(fā)至有效轉(zhuǎn)向點T，然后繼續(xù)依據(jù)XY算法完成分組傳輸。當(dāng)數(shù)據(jù)分組達(dá)到判斷點時，如果不滿足上述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ò)路徑延時的同時減輕了傳輸鏈路重構(gòu)環(huán)上的負(fù)載。針對以上優(yōu)化策略，在NoC運行的時候，通過BIST機(jī)制判斷每一節(jié)點周邊節(jié)點是否是F點，由通信節(jié)點與F點的相對位置確定重構(gòu)環(huán)路、有效轉(zhuǎn)向點T以及駐點H的信息。

3　容錯算法無死鎖驗證

對單故障節(jié)點2D-Mesh的NoC構(gòu)造一個有向圖I=G（N，C），如圖5（a）所示，結(jié)構(gòu)中的集合N和C分別代表節(jié)點間的鏈路。故障點F定義在（c，d）處，通信節(jié)點間的鏈路C=｛｝X，Y，X和Y是鏈路上橫向和豎向的路線集，分別用+、-的符號代表路線的傳輸方向，其余通信節(jié)點由F點的方位確定各自坐標(biāo)，在橫向上由西向東遞增，在豎向上由南向北遞增。由此對于節(jié)點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)向，同時增添由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)路，本文對算法RRA優(yōu)化的容錯策略是沒有死鎖的。

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

4　實驗設(shè)置與性能分析

4.1仿真配置

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

5　結(jié)論

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

［1］郭志海.片上網(wǎng)絡(luò)容錯路由算法的研究與實現(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)路無虛通道容錯路由技術(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