基于可重構容錯路由的片上網絡負載均衡

李洋，呂瑞

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

基于可重構容錯路由的片上網絡負載均衡

李洋，呂瑞

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

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

片上網絡；可重構；容錯路由；負載均衡

為了適應通信復雜度的需求，片上網絡（Network-on-Chip，NoC）成為當前片上多核的標準通信架構。在數據傳輸的過程中，一旦網絡芯片存在局部故障，與之相連的通信節點周圍鏈路就會失效，無法完成源節點與目的節點的有效通信［1-3］。為了確保數據傳輸的QoS，片上網絡容錯路由算法已成為當前片上網絡的研究熱點［4］。文獻［5］提出了一種基于內建自測（Built In Self Test，BIST）機制的分布式可重構容錯路由算法（Reconfigurable Routing Algorithm，RRA），它的設計思想是在無障礙區域采用XY路由方式，在障礙區域通過重構環路選用基于Turn Model模型的特定繞行路徑進行分組傳輸。本文以容錯路由算法為切入點，基于BIST機制，對2D Mesh片上網絡的容錯路由算法進行改進和優化。

1　故障節點模型

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

圖1　D-Mesh單故障節點NoC模型

圖2　2D-Mesh NoC內部節點故障繞行

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

2　NoC可重構容錯路由算法優化設計

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

圖3　RRA算法的繞行實例

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

圖4　網絡內部故障節點容錯優化

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

3　容錯算法無死鎖驗證

對單故障節點2D-Mesh的NoC構造一個有向圖I=G（N，C），如圖5（a）所示，結構中的集合N和C分別代表節點間的鏈路。故障點F定義在（c，d）處，通信節點間的鏈路C=｛｝X，Y，X和Y是鏈路上橫向和豎向的路線集，分別用+、-的符號代表路線的傳輸方向，其余通信節點由F點的方位確定各自坐標，在橫向上由西向東遞增，在豎向上由南向北遞增。由此對于節點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）是優化算法映射的CDG。依據死鎖定理可知若在映射的CDG中不存在環路，則路由算法R即為無死鎖的。在圖5（b）所示的CDG中，限制了由x+（c，d+1）至y-（c+1，d）和x+（c+1，d-1）至y+（c+2，d-1）的轉向，同時增添由y+（c+1，d）至 x+（c-1，d-1）和 y+（c+2，d）至 x-（c+1，d+1）的轉向。由圖中所示的CDG可以看出，沿任一通道開始都沒有構成環路，本文對算法RRA優化的容錯策略是沒有死鎖的。

圖5　2D-Mesh拓撲的NoC連接圖和優化算法下的CDG

4　實驗設置與性能分析

4.1仿真配置

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

4.2仿真結果分析

圖6　5×5和7×7兩種拓撲結構下NoC內部故障節點平均時延和吞吐率對比

5　結論

本文在BIST機制的基礎上，針對位于網絡內部的故障節點，通過判斷節點故障信息，根據故障的位置在網絡中設立判斷點和有效轉向點，在減少在重構環路上通信節點的負載同時完成路由算法優化設計。在OPNET仿真平臺上完成網絡元素配置，在均勻流量模式下，在5×5和7×7 2D Mesh兩種網絡規模上實現了算法仿真，獲得了平均時延和吞吐率兩項性能指標，與RRA算法相比本文算法在一定程度上提升了網絡性能。

［1］郭志海.片上網絡容錯路由算法的研究與實現［D］.哈爾濱：哈爾濱工業大學，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中規則網格及非規則網格結構的路由方法研究［D］.合肥：合肥工業大學，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］姚磊.片上網路無虛通道容錯路由技術研究［D］.西安：西安電子科技大學，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