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

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

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

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

1 NoC 路由概述

1.1 2D_Mesh NoC 結(jié)構(gòu)

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

圖1 一個典型2D-Mesh NoC 結(jié)構(gòu)

1.2 路由器架構(gòu)

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

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

圖2 NoC 路由器結(jié)構(gòu)框圖

1.3 虛通道技術(shù)

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

圖3 單端口數(shù)據(jù)緩存

2 路由算法

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

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

圖4 路由算法流程圖

3 加權(quán)輪詢仲裁設計

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

圖5 輪詢仲裁原理圖

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

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

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

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

圖6 優(yōu)先級可配置仲裁器

4 仿真與結(jié)果分析

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

圖7 仲裁波形圖

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

圖8 無競爭時數(shù)據(jù)傳輸

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

圖9 存在競爭時數(shù)據(jù)傳輸

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

表1 模擬器參數(shù)設置

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

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

5 結(jié)束語

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