基于加權輪詢仲裁的NoC 容錯路由設計*

張培雯 于宗光 陳振嬌 徐新宇

(1.江南大學物聯網工程學院,江蘇 無錫 214122；2.中國電子科技集團公司第五十八研究所,江蘇 無錫 214072)

片上網絡(Network-on-Chip,NoC)本質上是一種為解決片上多核系統設計中核間通信以及核與非核硬件單元之間數據傳輸問題的通信方案。相比于片上總線(On-Chip-Bus,OCB),NoC 因其集成度高、擴展性強、并行度高以及功耗低等優勢,已經逐漸取代OCB 成為新的片上通信標準[1]。

路由器作為NoC 中負責通信數據暫存和轉發的模塊,其設計對NoC 的傳輸效率具有重要影響。隨著NoC 中處理器核心數目的增多以及通信量的增大,出現網絡擁塞問題的概率也相應增加。路由器的設計中應考慮擁塞緩解,平衡網絡負載。目前,有很多文獻提到路由器設計中的擁塞緩解問題,例如通過專門的擁塞信息傳播網絡來獲取擁塞信息,或者在相鄰節點間設置旁路路徑來傳輸擁塞信息,也有通過下游路由節點的空閑緩存數量來判斷擁塞程度,最后根據擁塞情況選擇一條擁塞程度最小的傳輸路徑[2-4]。對于擁塞情況的處理,此類研究大多采用路由算法的優化,但是自適應算法可能存在數據包中切片無序到達目的節點問題,需要在目的端對包進行重新排序,如此網絡接口的設計復雜度增加,設計的面積開銷過大,并且很少考慮到網絡中鏈路故障的情況。為此,本文在現有研究的基礎上,提出基于加權仲裁的路由器設計方案,對路由仲裁模塊采用雙層仲裁機制,第一層仲裁采用權重策略,基于本地輸入負載情況以及報文剩余跳數的考慮給每個輸入請求賦予不同的權重Wi,Wi作為第二層輪詢仲裁的指針。本地負載較重且報文剩余跳數較少的請求被賦予更高的權重,對其優先進行傳輸,當傳輸完成后根據權重值的大小依次傳輸其他報文。與此同時,本文路由計算模塊采用具有容錯功能的自適應路由算法,避免因鏈路故障而面臨的阻塞情況,提高了網絡傳輸效率。

1 NoC 路由概述

1.1 2D_Mesh NoC 結構

一個典型的NoC 包括物理鏈路(Link,L)、路由器(Router,R)、網絡接口(Network Interfaces,NI)和處理單元(Processing Elements,PE)。如圖1 所示為一個典型二維網格(2D-Mesh)NoC 結構。

圖1 一個典型2D-Mesh NoC 結構

1.2 路由器架構

根據在網絡中所處位置不同,路由可分為內部路由節點,邊沿路由節點和對角路由節點,其路由器結構也因此有所差異。內部路由節點具有五個輸入輸出端,邊沿路由節點具有四個輸入輸出端,而對角路由節點只有三個輸入輸出端。以內部路由節點為例,輸入和輸出分別有東(E)、南(S)、西(W)、北(N)四個方向,通過雙向鏈路連接相鄰路由器,還有一個本地(L)端口連接資源節點(PE)。其內部由輸入單元、路由計算單元(Routing Computation,RC)、虛通道分配單元(Virtual-Channel Allocation,VA)和交叉開關分配單元(Switch Allocation,SA)、交叉開關以及輸出單元組成[5]。

輸入模塊由寄存器搭建的緩存單元和相應的控制邏輯,緩存單元被組織成隊列的形式,每一個隊列是一條虛通道(VC)。RC 基于頭切片中目的節點位置信息等計算出報文從當前節點到目的節點的傳輸路徑,即路由算法的實現。完成RC 后,頭切片發起輸出端VC 請求,VA 收集所有輸入請求后,對輸出VC 進行分配,保證每條輸出VC 最多被分配給一條輸入請求,每一輸入請求最多獲得一條輸出VC 授權。RC 和VA 都是以報文為粒度,只需要頭切片執行,體切片和尾切片則隨頭切片進行傳輸,即頭切片帶動整個報文的傳輸。當輸入獲得輸出VC 的授權后,路由器檢查輸出端VC 緩存情況,如果有空閑緩存,切片會向SA 單元發起交叉開關傳輸請求。交叉開關是由多個多路選擇器組成,當切片獲得授權,經過交叉開關傳輸至輸出端口,交叉開關則向上游路由器反饋一個credit 信號,表示釋放一個緩存單元。輸出單元由多個寄存器組成,記錄下游VC 狀態。本文路由器的結構如圖2 所示。

圖2 NoC 路由器結構框圖

1.3 虛通道技術

本文考慮到在網絡擁塞時,出現頭切片被阻塞,從而導致整個包的切片都無法傳輸,其傳輸的整個鏈路被阻塞的情況,為每個端口設置了2 條VC 緩存區間,每條VC 的深度為16。圖3 所示為緩存模塊框圖,圖中每個緩存空間對應一條VC,數據的輸入和輸出通過數據選擇器(MUX)控制。模塊中計數器用以記錄每個緩存區間的剩余可用空間。常規VC 分配中,當持有VC 的尾切片離開路由器時,VC就可重新分配。本文采用原子VC 分配,在路由器接收到前一個包的尾切片的信元之前,VC 不能被重新分配。這確保了每個VC 在任何給定的時間只持有一個包,從而避免了網絡中連續包之間的依賴關系。雖然常規的VC 分配可以在有限數量的VC下提供更高的吞吐率,但是原子VC 分配由于可以避免頭阻塞,從而體現出更好的傳輸性能。

圖3 單端口數據緩存

2 路由算法

路由算法負責為報文計算源節點到目的節點之間的傳輸路徑。路由算法包括路由協議和路由策略,路由協議根據收集的網絡信息形成路由表,路由策略則規定了查詢路由表選擇下一跳路由節點的方式。在網絡無故障的情況下,本文采用的路由算法遵循最短路徑原則[6],首先,比較源節點與目的節點的坐標,得到其X維度和Y維度上距離差值ΔX和ΔY。當ΔX＜＝ΔY,使用XY路由算法,先進行X維度尋徑,當Xlocal＝Xdes時,進行Y維度尋徑直到Ylocal＝Ydes,報文傳輸至目的節點；當ΔX＞ΔY,使用YX路由算法,先進行Y維度尋徑,當Ylocal＝Ydes,再進行X維度尋徑直到Xlocal＝Xdes,報文傳輸至目的節點。

對網絡中可能出現的故障情況,本文采用的檢測方法是,在一定周期內每個路由節點向相鄰節點發送測試向量,當節點獲取到響應向量后,與發送的向量相比對,若兩者相同則鏈路無故障,否則斷定鏈路存在故障[7-9]。確定故障后,將故障鏈路標記在路由表中,通過繞開故障點完成數據傳輸[10-11]。首先,根據無故障情況下默認路由算法,計算從源節點到目的節點的傳輸路徑。若被標記的故障點不在其傳輸路徑上,則根據默認路由算法進行傳輸至目的節點；若被標記故障點在其傳輸路徑上,報文傳輸至故障點前一級路由后,往另一維度傳輸一跳路由,接著從當前節點到目的節點根據默認路由算法計算得到傳輸路徑進行傳輸。具體算法流程如圖4 所示。

圖4 路由算法流程圖

3 加權輪詢仲裁設計

在NoC 路由節點中,路由仲裁單元主要是為處理多個輸入端請求同一輸出端的情況。目前路由仲裁單元大多采用固定仲裁和輪詢仲裁策略,固定仲裁是對每個輸入端設置固定優先級,當優先級最高的輸入端一直存在對此輸出端口的請求時,則其一直被響應,其他輸入請求就會有“餓死”的風險,所以固定優先級仲裁不夠公平,資源分配不夠合理。輪詢仲裁首先對各輸入端設置默認優先級,第一輪仲裁批準最高優先級的輸入端請求傳輸,隨后其在下一輪仲裁優先級降至最低,其他輸入端優先級順次上升,如圖5 所示為輪詢算法原理圖。輪詢仲裁使得每個輸入通道請求得以批準的概率相同,保證了公平性,但是當NoC 中IP 發送的信息不是同一類型,以及各端口流量具有較大差異時,輪詢仲裁則并不適合[12-15]。

圖5 輪詢仲裁原理圖

本文采用優先級可配置的仲裁策略,采用雙層仲裁。第一層為權重仲裁,對輸入端的負載量Li和請求報文的傳輸剩余跳數綜合考慮,賦予不同請求不同的權重。負載量較大的輸入端存在擁塞的可能性較大。同時,報文的傳輸剩余跳數(Remaining Hop Count,RHC)是報文在當前路由到目的路由之間的傳輸距離。傳輸方向上RHC 小的報文需要較少的時間在網絡中傳輸,對其優先傳輸,能夠使其占用的網絡的緩存資源盡快釋放給其他報文使用,能夠避免網絡擁塞。所以報文權重正比于輸入端負載量,與報文剩余跳數成反比。對輸出端為東、南、西、北這四個方向時,權重的計算公式為:

式中:Li為輸入端負載量,RHC 為當前報文的傳輸剩余跳數值。將不同輸入請求根據權重值進行排序,權重值越高優先級越高。當輸出端為本地方向時,權重直接由輸入端負載量決定。

公平性仍然是仲裁不可以忽略的原則,為防止高優先級輸入端一直占用資源,導致低優先級請求“餓死”,第二層仲裁采用輪詢算法。

圖6 為本文仲裁器的結構框圖,由權重仲裁、和輪詢仲裁兩級組成。參與資源競爭的各報文的權重由第一層權重仲裁產生。生成的權重作為第二層輪詢仲裁的指針,權重值越高其優先級越高,則此報文贏得仲裁,當此報文傳輸完成,則根據優先級高低順次響應其他請求。

圖6 優先級可配置仲裁器

4 仿真與結果分析

本文通過Verilog 實現路由器各個模塊的設計,并使用Modelsim 進行仿真驗證。圖7 是優先級可配置仲裁的仿真波形,當東西南北四個方向的輸入端均存在對本地輸出的請求時,根據第一層基于輸入端負載情況而確定各請求的權重,權重值越高則優先級越高,由圖可知東輸入端權重值最高,則其方向報文優先經交叉開關傳輸至本地,根據輪詢仲裁算法,當最高優先級請求傳輸完成后,選擇優先級次高的端口。

圖7 仲裁波形圖

當前某節點的西和南輸入端口都存在數據包傳輸請求,但兩輸入請求不同輸出端,即兩組數據傳輸不存在沖突,則兩請求各自傳輸,如圖8 所示。

圖8 無競爭時數據傳輸

當前某節點的西和南輸入端均存在對節點的東輸出端的請求,此時需要對兩請求進行仲裁,經過仲裁后輸出端口首先分配給西輸入請求,待西端口數據包傳輸完成,接著南輸入端口的請求被響應,如圖9所示。

圖9 存在競爭時數據傳輸

本文使用NoC 模擬仿真器Booksim,比較了本文仲裁和一般輪詢仲裁的路由器在uniform 和Transpose 流量模式下的數據包傳輸平均延時。表1為仿真參數配置。

表1 模擬器參數設置

兩種流量模式的延遲曲線如圖10 所示。在uniform 流量模式下,網絡中各節點的流量情況較平均,Transpose 是一種非均勻的流量模式,所以相較于uniform 流量下,在更小的數據包注入率下網絡接近飽和。在此兩種流量模式下,數據包注入率較低時,兩種路由器的數據包平均延時相差不大,當注入率不斷提高,優先級可配置仲裁路由平均包延時性能明顯優于普通輪詢仲裁路由。

圖10 兩種流量模式下平均包延時

5 結束語

本文設計了一種仲裁優先級可配置且具有容錯功能的NoC 路由器,實現了對路由器的各個模塊RTL 設計。首先,提出了權重輪詢仲裁方案,實現仲裁優先級可配置,將報文RHC 值以及輸入端負載作為權重計算變量,優先響應負載量較大且報文RHC值較小的請求,有利于避免網絡擁塞。其次,本文采用了一種容錯功能的自適應路由算法,通過向相鄰節點發送測試向量確定故障點并進行標記,繞開故障點完成數據傳輸。最后,給出了本文實驗仿真結果,以及將本文路由方案與采用普通輪詢仲裁的路由方案相比較,結果表明本文路由功能正常,擁塞緩解和容錯功能具有明顯優勢,是應對大通信量數據傳輸的有益方案。