一種低延遲的無虛通道NoC容錯路由算法

李 嬌, 徐海鵬, 崇云鋒, 劉 鵬, 冉 峰

(1.上海大學微電子研究與開發中心,上海200444;2.上海大學新型顯示技術及應用集成教育部重點實驗室,上海200444)

隨著單個芯片上集成的處理器單元數目的增多,多處理器片上系統(multiple processor system-on-chip,MPSoC)的傳統總線結構效率變低,因此需要一種新型的通信結構.鑒于此,片上網絡(network on chip,NoC)應運而生.NoC技術具有可擴展性、可重用性、靈活性和平行度等優點,已成為多處理器片上系統互聯問題的最佳解決方案[1-2].由于電路特征尺寸的不斷減小,芯片受到串擾、耦合、制造工藝和電路老化等問題影響的可能性增大,更易產生瞬時故障或永久性故障,降低了NoC的可靠性[3].為了有效減小故障對NoC帶來的影響,具有容錯性能的NoC路由算法成為了研究的熱點.

Zhang等[4]提出了一種可重構無虛通道容錯路由算法(簡稱Zhang’s算法).該算法在無故障區域使用XY路由算法,同時為了避免繞過故障節點時發生死鎖,根據轉向模型禁止東北和北東兩個轉向.Zhang’s算法復雜度較低,但其每個節點需要獲取8個方向上相鄰節點的故障信息,且只能對一個故障節點容錯.之后,姚磊等[5]對Zhang’s算法進行了擴展,提出基于內建自測試(build in self test,BIST)的容錯路由算法.該算法利用BIST提供的故障信息,分別在x軸方向和y軸方向上優化繞行環(鏈)路上的數據包分布,縮短了數據包的路由距離.基于BIST的容錯路由算法能夠均衡故障區域周圍的鏈路負載,降低網絡的時延,提高網絡吞吐量,但其仍只是對單故障區域進行容錯.

Ebrahimi等[6]提出一種最短路徑容錯路由算法(簡稱Ebrahimi’s算法),該算法能夠保持NoC在發生故障時的性能,但當位于對角線上的兩個相鄰節點發生故障時,存在數據包不能到達目的節點的情況,且NoC的可靠性也會隨著故障節點的增多而降低.另外,為避免死鎖,Ebrahimi’s算法使用了虛通道,使得NoC路由節點的復雜度上升.

為提高NoC的容錯能力,提高網絡傳輸效率,本工作主要提出了一種低延遲的無虛通道NoC容錯路由算法.該算法利用旁路結構,縮短了多核間數據包傳輸時的路徑,降低延遲時間,同時也能提高NoC的容錯性能.通過NoC研究中常用的仿真器NIRGAM對算法進行仿真,驗證了本算法的有效性.

1 NoC路由節點旁路結構

傳統的路由節點內部包括輸入緩存、路由計算單元、虛通道分配器、仲裁分配單元和交叉開關等[7].由于虛通道的使用會增加NoC路由節點的復雜度,增加芯片成本和功耗,因此本工作對傳統的路由節點結構進行修改,去除了虛通道分配器,同時增加旁路結構.旁路結構能夠在該路由節點發生故障時啟用,保持了一定方向上的連接,避免因故障而增加路由算法的復雜度.路由節點旁路結構模型如圖1所示.從圖可知,旁路結構中4個輸入輸出通道處(東、西、南、北)共增加了4個多路復用器和多路選擇器(虛線部分)以及旁路連線,其控制信號中的故障信號由故障檢測模塊生成.通過多路復用器、多路選擇器和旁路連線,路由節點上的南、北輸入通道分別直接連接北、南輸出通道,東、西輸入通道分別直接連接西、東輸出通道.因此,當節點發生故障時,故障檢測模塊產生的故障信號選通旁路,使得數據包可以直接通過旁路傳輸到下一個路由節點.

將旁路結構運用于整個NoC時,對于NoC邊界上的路由節點,由于邊界處會缺失與某一方向相連的路由節點,因此對邊界故障進行容錯時,勢必會存在轉向限制性.為改變這一限制,修改邊界上路由節點的旁路結構,改變路由節點輸入、輸出通道的連接,從而保持節點與其相鄰節點的連接性.

(1)4個頂點.西北頂點路由節點為其東方向和南方向上輸入輸出通道的雙向連接,東北頂點路由節點為其西方向和南方向上輸入輸出通道的雙向連接,東南頂點路由節點為其西方向和北方向上輸入輸出通道的雙向連接,西南頂點路由節點為其東方向和北方向上輸入輸出通道的雙向連接.

圖1 路由節點旁路結構模型Fig.1 Bypass structure model of router

(2)其他邊界節點.對于西邊界上的路由節點,因其沒有西輸入輸出通道,則其南、北、東輸入通道分別通過旁路連接到其北、東、南輸出通道;對于北邊界上的路由節點,因其沒有北輸入輸出通道,則其西、東、南輸入通道分別通過旁路連接到東、南、西輸出通道;對于東邊界上的路由節點,因其沒有東輸入輸出通道,則其北、南、西輸入通道分別通過旁路連接到南、西、北輸出通道;對于南邊界上的路由節點,因其沒有南輸入輸出通道,則其東、西、北輸入通道分別通過旁路連接到西、北、東輸出通道.以3×3 Mesh NoC為例,修改后的NoC旁路結構如圖2所示.由圖可以看出,單向的通道連接會在邊界節點上形成環路,為避免死鎖,需要對部分轉向進行限制.

圖2 3×3 Mesh NoC的旁路連接Fig.2 Bypass connection of 3×3 Mesh NoC

2 無虛通道容錯路由算法

2.1 轉向模型

在NoC容錯路由算法中,死鎖是一個必須解決的問題.死鎖是指數據包之間相互等待形成環形,使得數據包無法繼續傳輸.在無虛通道的容錯路由算法中,轉向模型[8]是一種有效解決死鎖的方案,在不需要添加虛通道的情況下,通過禁止部分轉向避免死鎖.文獻[8]中給出了3種自適應的路由算法:西優先、北最后、逆向優先,這些算法的禁用轉向如圖3(a),(b)和(c)所示.本工作采用的轉向模型根據后續的無虛通道容錯路由算法,在數據包路由時,首先自適應地向西、北、南路由,然后才是東方向.即東方向是最后一個被傳輸的方向,該算法在數據包路由時禁止由東到南和由東到北的轉向,從而避免產生環路形成死鎖(見圖3(d)).

圖3 容錯路由算法的禁用轉向示意圖Fig.3 Schematic diagram of forbidden turnings for fault-toleront routing algorithm

2.2 容錯路由算法

為了計算數據包的合理輸出端口,本算法中每個節點會有一個4 bit的寄存器fault表示4個相鄰節點的故障信息.fault 0,fault 1,fault 2,fault-3分別表示東(E)、南(K)、西(W)、北(N)4個相鄰節點的故障信息,數值為0時表示無故障,1則表示有故障.考慮到轉向模型下數據包可存在多條傳輸路徑,為了均衡傳輸的負載,增加1 bit的標識位 fl ag來決定數據的輸出端口.在n×n Mesh NoC下,當前節點坐標為(XC,YC),目的節點坐標為(XD,YD),本算法描述如下.

(1)目的節點為當前節點(XC=XD,YC=YD)時,數據包轉發到當前節點的知識產權(intellectual property,IP)核,即輸出端口Out=L(本地).

(2)目的節點與當前節點位于同一軸(XC=XD或YC=YD)時,數據包轉發到該軸靠近目的節點的下一節點.

(3)目的節點位于當前節點東南(XCYD)時,如果當前節點不在西邊界(XC6=0),南相鄰節點故障且其不位于南邊界(fault 1=1,YC6=1)時,數據包的輸出端口Out=W;其他情況下,Out=S.

(4)目的節點位于當前節點東北(XC

(5)目的節點位于當前節點西南(XC>XD,YC>YD)時,當南相鄰節點故障且西相鄰節點無故障(fault 1=1,fault 2=0),數據包的輸出端口Out=W;當西相鄰節點故障且南相鄰節點無故障(fault 2=1,fault 1=0),數據包的輸出端口Out=S;其他情況下,當標識位 flag=0時,輸出端口Out=W,將標識位取反;當標識位 fl ag=1時,輸出端口Out=S,將標識位取反.

(6)目的節點位于當前節點西北(XC>XD,YC

基于上述算法的描述可以看出:當目的節點位于當前節點東南或東北時,由于轉向模型的限制,只存在一條固定的數據包傳輸路徑;而當目的節點位于西南或西北時,算法可以采用多條路徑,同時在節點中增加1 bit的標識位,避免數據包固定傳輸同一路徑造成阻塞.這使得算法具有一定的自適應性,能夠緩解熱點的產生.

2.2.1 單故障節點

當NoC存在單個故障節點且故障節點不處于邊界時,Zhang’s算法和本算法的原輸路徑如圖4所示.由圖可知,在單個故障存在情況下,按照Zhang’s算法,數據包分別從源節點4,6,2傳輸到目的節點6,1,6.由于故障節點的存在,故障節點以及相連的鏈路都無法使用,數據包需要在故障節點周圍進行繞行才能到達目的節點;而基于本算法,在相同源節點和目的節點的情況下,由于故障節點的旁路被選通,數據包利用旁路結構能夠通過故障節點,有效降低數據包的傳輸距離.本算法最大能優化數據包繞行減少3跳,即源節點和目的節點位于同一列或同一行的情況.當故障節點位于邊界時,根據本算法的旁路規則,會產生邊界故障,如圖5所示.由圖可以看出,當前節點與目的節點分別位于節點1與節點5時,由于轉向模型的限制,數據包無法通過虛線所示路徑傳輸到目的節點.

圖4 兩種不同容錯路由算法的傳輸路徑Fig.4 Transmission path of two different fault-toleront routing algorithms

圖5 邊界故障Fig.5 Boundary fault

為了解決圖5所示的邊界故障問題,提高NoC的容錯性和可靠度,本算法允許故障邊界節點相連的節點部分180?轉向,以便有效解決邊界節點發生故障時數據包的傳輸限制.禁用的180?轉向如圖6所示,其中邊界故障的旁路連接可以類似表示為單向傳輸環路(單向實線箭頭構成部分).對于西邊界故障形成的單向傳輸環,允許其北相連節點(節點1)進行由南到南的轉向,東相連節點(節點2)進行由西到西的轉向,禁止其南相連節點(節點3)進行由北到北的轉向;對于北邊界故障而言,允許其西相連節點(節點4)進行由東到東的轉向,南相連節點(節點5)進行由北到北的轉向,禁止其東相連節點(節點6)進行由西到西的轉向;對于東邊界故障而言,允許其西相連節點(節點7)進行由東到東的轉向,北相連節點(節點8)進行由南到南的轉向,禁止其南相連節點(節點9)進行由北到北的轉向;對于南邊界故障而言,允許其西相連節點(節點10)進行由東到東的轉向,北相連節點(節點11)進行由南到南的轉向,禁止其東相連節點(節點12)進行由西到西的轉向.

圖 6 禁用的180?轉向(虛線)Fig.6 Forbidden 180?turnings(dotted line)

因此,對于圖5所示的邊界故障,數據包可以先傳輸到節點7,進行180?轉向,然后通過故障節點4的旁路到達目的節點5.通過允許180?轉向,邊界上的數據包可以不受轉向模型的限制,正常地傳輸到相應的目的節點,且面對多故障節點情況時數據包也能夠利用這些轉向更有效的傳輸.

2.2.2 多故障節點

對于多故障情況,Zhang’s等[4]提出了將多個故障節點與一些無故障節點擴展成一個故障區域的設想,但因故障區域中的無故障節點被視為故障節點,無法進行數據的傳輸接收,降低了NoC的可靠性.圖7所示為一對斜對角故障節點的情況.如果當前節點C與目的節點D位于圖中位置時,此時目的節點位于當前節點的西南方.故障節點與節點C,D形成了一個故障區域(虛線框).按照Zhang’s算法,故障區域內的節點C和D被視為故障節點,無法進行傳輸與接收數據.而對于本算法,數據包可以通過故障節點的旁路傳輸到目的節點,且由于算法的自適應性,數據包可以通過兩條路徑(實線)進行傳輸.

圖7 多故障節點下容錯路由算法的傳輸路徑Fig.7 Transmission path for fault-toleront routing algorithm with multiple faults

3 算法無死鎖證明

本算法采用的轉向模型是無死鎖的,由于在邊界故障節點上允許部分180?轉向,因此需證明在邊界上允許180?轉向,算法仍無死鎖.利用Dally等[9]提出的通道依賴圖(channel dependency graph,CDG)的方法,即當網絡對應的CDG無環路時,算法在該網絡中無死鎖.

根據Dally的方法,西邊界故障時的網絡連接如圖8所示.由于本算法采用的轉向模型禁止東南轉向和東北轉向,即不存在X56到X64的轉向和X12到X24的轉向.由于Z54到Y42以及Z54到Y46中也存在東南轉向和東北轉向,因此也不存在這兩種轉向.同時,為解決邊界故障的問題,增加Y15到Y54的轉向和Z54到Z41的轉向,禁止Z41到Y15的轉向.由采用本算法后網絡對應的CDG可以看出,CDG中沒有形成環路,即本算法是無死鎖的.對于其他邊界故障的情形,也可以類似證明.

圖8 西邊界故障的網絡連接Fig.8 Network links in west boundary fault

4 仿真分析

采用NIRGAM仿真器[10]對本算法的性能進行仿真驗證,并與Zhang’s算法和Ebrahimi’s算法進行比較.NIRGAM是一種基于System C的NoC專用仿真器,具有代碼開源、擴展性好等特點.仿真器的主要參數配置如表1所示.

表1 仿真器的參數配置Table 1 Configuration of simulator parameters

為了體現本算法的性能,分別在單故障與多故障情況下進行仿真,比較Zhang’s算法、Ebrahimi’s算法和本算法的平均延遲.在單個故障的情況下,Zhang’s算法、Ebrahimi’s算法和本算法的數據包平均延遲曲線如圖9所示.可以看出,在通信負載較低時,3種算法的平均延遲基本一致,但隨著通信負載的不斷增加,Zhang’s算法和Ebrahimi’s算法的平均延遲分別在通信負載20%和30%時迅速提升,而本算法的平均延遲則緩慢升高,在通信負載為40%后才大幅度升高.在通信負載為30%時,本算法的平均延遲相比于Zhang’s算法改善20.2%,相比于Ebrahimi’s算法改善4.35%.這是由于Zhang’s算法存在較長的繞行路徑,在通信負載較高時延遲較大的問題顯現出來;而Ebrahimi’s算法雖為最短路徑,一定程度上降低了延遲,但由于采用了虛通道,當通信負載較高時會出現負載不平衡的情況,產生阻礙數據包傳輸的的熱點,進而增加了延遲.本算法雖也存在繞行,但相比于Zhang’s算法,繞行距離要短.此外,本算法具有部分自適應性,能夠有效避免熱點的產生.

圖9 單故障下3種不同容錯路由算法的平均延遲Fig.9 Average latency of three different fault-toleront routing algorithms with single fault

在多故障的情況下,由于Zhang’s算法的性能并不高,因此僅比較Ebrahimi’s算法和本算法.圖10為多個故障情況下兩種算法的平均延遲曲線.可以看出,與單故障類似,本算法仍具有較低的平均延遲,且隨著故障節點數目的增多,平均延遲均會有所增加.

圖10 多故障下兩種不同容錯路由算法的平均延遲Fig.10 Average latency of two different fault-toleront routing algorithms with multiple faults

5 結束語

本工作提出了一種低延遲的無虛通道容錯路由算法,通過旁路結構,保持了故障節點在部分方向上與相鄰節點的連接,進而減少了數據包的傳輸延遲,同時對邊界旁路結構加以改進,解決了算法在使用轉向模型時邊界節點故障時的路由限制.仿真分析的結果表明,本工作提出的算法能夠有效降低數據包的平均延遲,且在多故障下仍能保持良好的性能.