一種轉向均衡的3D NoC 感知容錯路由算法

李 嬌， 郭潤龍， 蔡 升， 崇云鋒， 徐海鵬， 冉 峰

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

利用硅通孔(through silicon vias， TSV)技術實現三維集成電路(three-dimensional integrated circuit， 3D IC)[1]已成為可能， 與之相適應的片上網絡 (network on chip， NoC)技術也從二維片上網絡(two-dimensional network on chip， 2D NoC)[2]發展到三維片上網絡(threedimensional network on chip， 3D NoC)[3]. 3D NoC 可以實現更短的全局互連， 并具有可擴展性， 可提高通信效率， 因此將成為復雜高性能片上系統(system on chip， SoC)中最有效的通信結構. 但芯片復雜度的增加也使得網絡鏈路在通信時出現故障的概率變大， 網絡可靠性也隨之降低. 因此， 為了保證3D NoC 的性能， 已有研究者提出了容錯路由算法[4].

在數據傳輸過程中， 由于數據包相互等待形成環形會引起網絡死鎖， 使得數據無法繼續傳輸， 從而降低傳輸效率及可靠性; 同時死鎖會造成數據擁塞導致流量不均衡， 從而引起網絡性能下降. 容錯路由算法可以解決網絡中死鎖及流量不均衡的問題， 從而保證網絡的性能，因此容錯路由算法是提升網絡性能的一個研究重點. 為了避免額外的面積開銷， 目前解決死鎖問題主要采用禁止轉向模型法. 在3D NoC 禁止轉向模型法中， Dahir等[5]對2D NoC 中的奇偶(odd even， OE)轉向模型[6]進行擴展后提出了一種B-OE 轉向模型應用于3D NoC 中，并證明了該模型可以避免水平和垂直方向的死鎖. Zhou等[7]基于B-OE 轉向模型提出了一種低開銷容錯(low-overhead fault-tolerant， LOFT)算法， 該算法在XY 平面的轉向模型中進行4 種行列上的變體， 再分別應用于不同的平面以提高XY 平面的流量均衡性， 但LOFT 中的B-OE 轉向模型在垂直方向有多個禁止轉向， 且B-OE 轉向模型依賴垂直方向的流量負載，不能達到流量均衡， 在很大程度上限制了網絡性能. 由此， Zhou等[8]提出了一種NeoOE 轉向模型， 該模型在奇偶XY 平面上增加了特定的上下禁止轉向， 使垂直方向的流量能達到相對均衡， 但在數據流越來越多的3D NoC中， 其禁止的轉向較少且固定， 這勢必會影響流量均衡性，造成傳輸延時的增加及吞吐量的降低， 因此需要設計均衡轉向模型以避免死鎖， 并提高流量均衡性.

為了解決上述問題， Lei等[9]提出了垂直網格動態感知(vertical-mesh-conscious-dynamic，VMCD)路由算法應用于3D NoC 中， 該算法提高了網絡的吞吐量， 降低了傳輸延遲， 但在不同平面上應用相同的轉向模型， 由于轉向不均衡從而使得流量均衡性改善不明顯. Su等[10]結合VMCD 算法提出了一種容錯路由算法， 該算法在VMCD 中增加了水平鏈路故障模型， 并對每種故障模型制定了相應的容錯繞行路徑， 同時在網絡中應用“一跳預先感知”策略以提高傳輸效率， 增強了網絡的容錯能力. 但該算法只考慮了水平邊界鏈路故障， 并沒有解決水平鏈路內部及垂直鏈路故障， 所以需要設計包含更多故障類型的模型及繞行規則以提高網絡的可靠性.

由此可見， 雖然對3D NoC 容錯路由算法已開展了很多研究， 但在死鎖、流量均衡與故障模型等方面還存在問題. 本工作對這些問題進行了研究， 提出了一種轉向均衡的感知容錯路由算法. 本算法將3D NoC 中的平面進行奇偶分類， 并提出應用于不同平面的均衡轉向模型， 以提高網絡的流量均衡性， 進而提升吞吐量并降低傳輸延遲; 此外， 針對網絡中可能存在的鏈路故障， 提出了水平及垂直方向上邊界和內部鏈路故障模型， 根據奇偶行列制定相應的容錯繞行， 從而保證數據傳輸效率; 最后， 提出“全平面一跳預先感知”策略， 該策略可以同時感知垂直及水平方向連續兩跳的故障信息， 使得數據可以提前進入故障繞行路徑， 提高了網絡容錯能力和網絡可靠性.

1 均衡轉向模型

為了解決3D NoC 中死鎖的問題， 在VMCD 算法中將奇偶轉向模型與XY 路由應用在 XY ， XZ 和 Y Z 平面， 模型如圖 1 所示， 其中 E， W， S， N， U， D， Even 和 Odd 分別代表東、西、南、北、上、下、偶和奇. 先在網絡中以資源節點建立三維坐標系， 將E， S 和D 向分別作為X， Y 和Z 坐標軸正向， 從原點出發在各方向每一跳坐標加1， 根據坐標值可將X， Y 和Z 方向分為奇偶行列， 具體奇偶分類已在圖中標出; 同時， 在XY 平面上以Z 坐標分為奇偶平面，再以X 坐標分為奇偶列， 在Y Z 平面上以Z 坐標分為奇偶行， 在XZ 平面上以Z 坐標分為奇偶行.

圖1 VMCD 算法中的轉向模型Fig.1 Turn model in VMCD algorithm

依據上述定義的三維坐標系， VMCD 算法的轉向模型在奇XY 平面上偶列禁止ES 和EN轉向，奇列禁止SW 和NW 轉向，在偶XY 平面上應用XY 路由;Y Z 平面上偶行禁止SD 和ND轉向， 奇行禁止 US 和 UN 轉向; XZ 平面上偶行禁止 UE 和 UW 轉向， 奇行禁止 ED 和 WD 轉向. 但該模型在每個平面上都是禁止同樣的轉向， 當3D NoC 規模不斷增大時， 數據永遠無法選擇被禁止轉向路徑傳輸， 造成可傳輸的路徑數目減少， 從而導致流量不均衡而降低網絡性能.

為了解決網絡中轉向固定引起的流量不均衡問題， 本工作提出一種均衡轉向模型， 如圖2 所示. 首先， 對網絡中的奇偶平面與行列進行了新的分類， 即根據X， Y 和Z 的坐標值將網絡中的平面分為奇偶XY， XZ 和Y Z 共6 種類型平面. 在奇XY 平面上， 根據Y 坐標分為奇偶行， 在偶XY 平面上， 根據X 坐標分為奇偶列; 在奇XZ 平面上， 根據Z 坐標分為奇偶行， 在偶XZ 平面上， 根據X 坐標分為奇偶列; 在奇Y Z 平面上， 根據Z 坐標分為奇偶行， 在偶Y Z 平面上， 依據Y 坐標分為奇偶列. 然后， 設定了相應的轉向模型， 具體轉向規則如下: ①在奇XY 平面上， 奇行上禁止EN 和WN 轉向， 偶行上禁止SE 和SW 轉向;②在偶XY 平面上， 奇列上禁止WS 和WN 轉向， 偶列上禁止SE 和NE 轉向; ③在奇XZ 平面上， 奇行上禁止 UE 和 UW 轉向， 偶行上禁止 ED 和 WD 轉向; ④ 在偶 XZ 平面上， 奇列上禁止 UW 和 DW 轉向， 偶列上禁止 ED 和 EU 轉向; ⑤ 在奇 Y Z 平面上， 奇行上禁止 DS 和 DN 轉向， 偶行上禁止SU 和NU 轉向; ⑥在偶Y Z 平面上， 奇列上禁止SU 和SD 轉向， 偶列上禁止 UN 和 DN 轉向.

圖2 均衡轉向模型Fig.2 Turn balanced model

綜上可見， 當3D NoC 規模不斷增大時， 均衡轉向模型在每種平面上都有不同的禁止轉向，不僅可以避免環形路徑解決死鎖問題， 保證網絡的可靠性， 同時還可避免某些轉向永遠禁止傳輸數據的情況， 增加了傳輸路徑的選擇性， 提升了流量均衡性， 從而提高吞吐量并降低傳輸延時.

2 故障模型與路由算法

2.1 故障模型與繞行規則

故障模型與繞行規則均是為了提高NoC 路由算法的容錯性， 保障當NoC 中出現鏈路故障時通信可以正常進行. Su等[10]提出的故障模型及繞行規則是3D NoC 路由算法研究中的典型.該模型將XY 平面的邊界故障分為8 種類型， 再設置相應的繞行規則， 如圖3 所示. 以type 1為例， 其為北邊界東向鏈路故障(即源節點15 到目的節點14 的鏈路故障)， 此時根據繞行規則，數據由節點15 先向南路由至節點8， 再向東路由至節點9， 最后再向北路由至目的節點14 完成路由， 其余7 種故障類型及其繞行規則在圖3 中可見.

圖3 無垂直故障模型及繞行規則[10]Fig.3 No vertical fault model and bypass rules[10]

可以看出， 上述故障模型及繞行規則提高了網絡的容錯能力， 但只解決了XY 平面邊界的水平鏈路故障及其繞行， 而故障可以發生在任意鏈路， 因此本工作提出了新的故障模型， 本模型對3D NoC 中水平及垂直方向上的邊界和內部鏈路故障均有所考慮， 并對每種鏈路故障設計了相應的繞行規則. 在容錯路由算法中加入本故障模型， 可以保證當鏈路出現故障時數據能繞行傳輸， 避免數據擁塞導致死鎖， 從而提高數據傳輸效率， 提高網絡可靠性.

本模型根據鏈路故障的位置分為8 種類型: 在XY 平面根據Y 坐標在行向上分為奇偶東西向， 根據X 坐標在列向上分為奇偶南北向; 在XZ 平面根據X 坐標在列向上分為奇偶上下向; 在Y Z 平面根據Y 坐標在列向上分為奇偶上下向. 如圖4 所示， 根據不同的故障制定相應的繞行規則， 具體故障模型分類和繞行規則如下.

圖4 優化的故障模型及繞行規則Fig.4 Optimized fault model and bypass rule

type 1: 對XY 平面偶行上東與西向鏈路故障， 故障繞行先向南路由， 再分別向東與西路由， 最后再向北路由完成繞行;

type 2: 對XY 平面奇行上東與西向鏈路故障， 故障繞行先向北路由， 再分別向東與西路由， 最后再向南路由完成繞行;

type 3: 對XY 平面偶列上南與北向鏈路故障， 故障繞行先向東路由， 再分別向南與北路由， 最后再向西路由完成繞行;

type 4: 對XY 平面奇列上南與北向鏈路故障， 故障繞行先向西路由， 再分別向南與北路由， 最后再向東路由完成繞行;

type 5: 對XZ 平面偶列上上與下向鏈路故障， 故障繞行先向東路由， 再分別向上與下路由， 最后再向西路由完成繞行;

type 6: 對XZ 平面奇列上上與下向鏈路故障， 故障繞行先向西路由， 再分別向上與下路由， 最后再向東路由完成繞行;

type 7: 對Y Z 平面偶列上上與下向鏈路故障， 故障繞行先向南路由， 再分別向上與下路由， 最后再向北路由完成繞行;

type 8: 對Y Z 平面奇列上上與下向鏈路故障， 故障繞行先向北路由， 再分別向上與下路由， 最后再向南路由完成繞行.

上述設計的繞行路徑均是在出現某一故障時， 繞行鏈路在無故障情形下的最簡繞行路徑， 若繞行路徑出現故障， 數據將同向路由至下一節點再進行反向路由， 從而完成繞行， 因此可避免數據擁塞問題. 以type 1 為例， 當節點15 至節點14 的偶行東向故障時， 首先數據由節點15 向南路由至節點8， 如節點8 至節點9 存在東向故障， 數據將從節點8 向南路由至節點7，再向東路由至節點6， 最后通過向北路由經過節點9 再至節點14; 如節點9 至節點14 存在北向故障， 則數據將從節點9 向東路由至節點10， 再向北路由至節點13， 最后向西路由至節點14;當其他故障類型最簡繞行路徑存在故障時， 故障繞行與type 1 類似. 因此， 本工作提出的故障模型及其繞行策略可提升數據繞行靈活性， 使網絡可靠性大幅提升.

2.2 “全平面一跳預先感知”策略

在3D NoC 中同一數據的傳輸路徑具有多樣性， 路徑的選擇是隨機的， 在規模和復雜度增大致使鏈路故障概率增大的情形下， 如果數據在傳輸過程中遇到故障鏈路， 則必須重新選擇路徑， 這勢必影響網絡傳輸效率， 因此在本工作提出的故障模型可以同時解決水平及垂直鏈路故障的情形下， 提出了“全平面一跳預先感知”策略. 當容錯路由算法未加入本策略時， 網絡中的路由器僅能感知其周邊一跳的鏈路故障信息并決定下一跳的傳輸路徑， 若根據路由算法決定的第二跳鏈路存在故障， 且第一跳路徑為第二跳故障鏈路的繞行路徑， 此時數據繞行需要回傳至第一跳路徑的源節點， 從而引起死鎖導致數據無法傳輸; 運用本策略后， 網絡中的路由器可以感知其周邊連續兩跳的鏈路故障信息， 如果出現第二跳路徑存在故障且第一跳路徑為繞行路徑時， 數據不會完成第一跳路由， 而是直接進入繞行路徑完成路由.

本策略可以同時感知水平及垂直方向上連續兩跳的鏈路故障信息， 從而決定所在路由平面連續兩跳的方向， 使得數據在傳輸時可以感知故障信息， 提前繞行故障鏈路， 不僅可以降低傳輸延時， 還可以避免死鎖， 從而提高網絡的可靠性. 以圖4(a)中的type 1 具體介紹本策略，在隨機選擇模式下， 數據由節點8 路由至節點14. 首先數據路由至節點9 或節點15 的概率各為50%， 如果路由器選擇下一節點為節點15， 且存在節點15 至節點14 的東向鏈路故障， 根據繞行規則數據需從節點15 路由至節點8， 此時由于數據回傳將導致死鎖， 引起網絡性能的降低. 應用本策略后， 當數據在節點8 路由之前， 路由器會感知連續兩跳的路徑是否存在故障， 此時如果感知到節點15 至節點14 的鏈路故障， 則路由器不再考慮節點15， 而是進入繞行路徑，直接由節點8 路由至節點9， 最后再路由至節點14， 可見本策略可避免數據繞行回傳造成的死鎖問題. 本策略的具體運用如圖3 和4 所示， 即圖中的回傳路徑不會出現， 可以有效避免死鎖而增加網絡傳輸延時的問題， 進而提高了網絡的可靠性.

2.3 路由算法

根據本工作設計的均衡轉向模型， 在垂直方向上的路由可在XZ 與Y Z 平面完成， 由于在垂直方向上有更多的轉向選擇， 可以避免死鎖以提升流量的均衡性， 所以本工作提出的算法將數據優先路由至XZ 和Y Z 垂直平面再進行路由. 設網絡中源節點坐標為S(x，y，z)， 當前節點坐標為C(x，y，z)， 目的節點坐標為D(x，y，z)， e0 = Dx-Sx， e1 = Dy-Sy， e2 = Dz-Sz.基于上述提出的均衡轉向模型， 本工作提出的路由算法規則如圖5 所示.

圖5 算法流程Fig.5 Algorithm process

具體路由算法規則如下:

(1) 當 e0， e1 和 e2 均為 0 時， 數據無需路由.

(2) 當 e0， e1 和 e2 中有 2 個為 0 時， 根據不為 0 數據的正負向 E， W， S， N， U 或 D 直接路由至目的節點.

(3) 當e0 為0 時， 數據直接根據Y Z 平面的轉向模型路由; 當e1 為0 時， 數據直接根據XZ 平面的轉向模型路由; 當e2 為0 時， 數據直接根據XY 平面的轉向模型路由.

(4) 當 e0， e1 和 e2 均不為 0 時， 若 e0 的絕對值小于 e1 的絕對值， 則數據根據 e0 的正負向東或向西路由至與目的節點在同一個Y Z 平面， 在Y Z 平面根據轉向模型路由至目的節點;若e0 的絕對值大于e1 的絕對值， 則數據根據e1 的正負向南或向北路由至與目的節點在同一個XZ 平面， 在XZ 平面根據轉向模型路由至目的節點.

本工作提出的算法路由規則中加入了均衡轉向模型， 提高了流量的均衡性; 結合故障模型與繞行規則可以避免出現鏈路故障造成的擁塞死鎖問題， 提高了網絡的可靠性; 同時將“全平面一跳預先感知”策略加入路由算法中， 可以提前感知故障鏈路并進行繞行， 從而提升傳輸效率. 本工作提出的容錯路由算法提升了流量均衡性， 從而降低了傳輸延時， 同時可以避免死鎖，提高了網絡可靠性.

3 實驗結果與分析

為了驗證本工作所提出的算法， 采用由二維仿真器Noxim 擴展而來的三維仿真器Access Noxim 對算法進行仿真驗證. Access Noxim 是一種基于 System C 的 3D NoC 專用仿真器， 具有代碼開源、擴展性好等特點， 仿真器的配置參數如表1 所示. 將加入本工作提出的故障模型及繞行規則的VMCD1 算法和本工作提出的算法分別通過Access Noxim 進行仿真驗證， 同時在網絡中分別隨機選取0%， 4%， 7%的水平和垂直鏈路故障， 對比仿真結果驗證隨故障率增加時的算法性能.

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

圖6 為VMCD1 變形算法和本工作提出的算法在不同鏈路故障率情形下吞吐量與注入率變化的對比. 從圖6(a)可以看出， 當兩種算法不存在鏈路故障時， 本算法相對VMCD1 變形算法吞吐量有16.2%的提升; 在圖6(b)中， 當網絡中鏈路故障率增加時， 本算法在吞吐量方面也明顯優于VMCD1 變形算法. 這是因為本算法使用均衡的轉向模型， 使得鏈路中的流量均衡，降低了擁塞度. 圖7 為VMCD1 變形算法和本工作提出的算法在不同鏈路故障率情形下平均延時與注入率變化的對比.

圖6 算法吞吐量比較Fig.6 Algorithm throughput comparison

圖7 算法平均延時比較Fig.7 Algorithm average delay comparison

在無鏈路故障下， 當注入率達到0.15 時平均延時基本穩定， 本算法相比VMCD1 變形算法平均延時有3.6%的降低. 在網絡中出現鏈路故障下， 當注入率達到0.3 時平均延時基本穩定，且當故障率增加時， 本算法在平均延時上有明顯的優勢， 相比VMCD1 變形算法平均延時降低了11.8%. 從圖中可看出， 當故障率增加時， 本算法傳輸延時比無故障時有所降低， 這是因為出現故障時數據選擇繞行路徑傳輸， 此時不受禁止轉向的限制， 路徑跳數有減少的可能性， 所以傳輸延時有所降低， 但吞吐量是隨著故障率增加而下降的.

4 結束語

本工作提出一種轉向均衡的感知容錯路由算法， 在復雜的網絡中通過對不同平面禁止不同的行列轉向， 在避免網絡死鎖的同時有了更均衡的轉向， 進而流量均衡降低了數據傳輸延時并提高了網絡的吞吐量; 本工作提出的故障模型及繞行規則解決了網絡中水平和垂直方向上的邊界及內部鏈路故障， 提高了網絡的可靠性; 同時， 運用“全平面一跳預先感知”策略提高了傳輸效率. 實驗結果表明， 本工作提出的算法具有轉向均衡的特性， 能有效降低傳輸延時并提高網絡吞吐量， 在有鏈路故障時， 本算法的性能仍然優于加入本工作提出的故障模型的VMCD1 算法.