基于FPGA的2D-Torus片上網絡無死鎖路由算法

李貞妮， 李晶皎， 王 驕， 楊 丹

(東北大學 信息科學與工程學院， 遼寧 沈陽 110819)

隨著面向智能信息處理的嵌入式系統的發展和半導體工藝技術的進步，片上系統(system on chip, SoC)能夠集成的處理器和IP核越來越多，使基于總線結構的設計復雜度呈指數增長，片上多核間的復雜通信也使得基于總線的通信結構成為限制芯片速度、功耗、面積和數據吞吐量的瓶頸[1-3].ITRS預測，到2020年，單芯片上可集成的晶體管數目將達到千億級的規模[4].片上網絡(network-on-chip，NoC)的出現解決了基于總線的系統不可伸縮等問題，通過借鑒計算機網絡技術，在芯片內部各個模塊之間采用路由和數據包分組交換的方式進行通信，為SoC中處理器和IP核之間的通信提供靈活、高效、可靠的解決方案[5].

目前，大多數片上網絡采用最典型的二維網格(2D-Mesh)[6-7]結構.2D-Mesh拓撲結構是一種網格結構，每個路由節點連接一個計算節點IP核，并與其上、下、左、右4個方向的相鄰路由節點連接(邊界節點除外)；然而在Mesh拓撲結構中，邊界路由節點之間不存在直接的路由連接，因此當數據包在邊界節點之間傳輸時，可能需要沿橫向或縱向穿過整個片上網絡，導致數據包在片上網絡中的傳輸延遲增加[8-9].與之相比，2D-Torus 拓撲結構在Mesh拓撲結構的基礎上，增加了行和列首尾路由節點的長連線，以達到縮短網絡平均直徑和提升片上網絡通信性能的目的[10-12]，每個路由節點具有相同的結構，因此可擴展性強，易于在硬件上實現，且其路由路徑的多樣性有效降低了阻塞的發生，提高了網絡的傳輸效率[1,13].因此，本文主要針對2D-Torus拓撲結構，對片上網絡的路由算法進行研究.

片上網絡的路由算法決定了消息從源節點到目的節點要經過的通道序列[14-16].隨著片上系統集成的處理器核數的不斷增加，由生產缺陷、工藝偏差和芯片老化等引發的故障導致NoC出現故障的概率不斷提高.路由算法主要解決路由路徑的選擇問題，一個好的路由算法必須考慮其是否能夠充分利用片上網絡的空閑資源來改善片上網絡的延遲和吞吐率；是否能夠盡可能減小片上網絡的功耗.Torus拓撲結構中的環路增加了路由路徑的多樣性，但同時也帶來了許多問題，例如死鎖問題，這就進一步要求面向Torus結構的路由算法能夠解決環路帶來的死鎖等問題.因此，本文針對2D-Torus拓撲結構，提出了一種基于列分轉彎[5]的Torus無死鎖(Torus deadlock-free, TDF)路由算法，通過改變數據包在片上網絡路由過程中受限制轉彎的位置，保證片上網絡的自適應路由條件，從而降低片上網絡的延遲.并通過理論分析、仿真實驗和實物測試來證明該算法是無死鎖的.

1 TDF路由算法描述

為解釋TDF路由算法，假設目的節點坐標為D(xd,yd)，源節點坐標為S(xs,ys)，當前節點坐標為C(x,y)；路由開始時，源節點坐標等于當前節點坐標.每個路由節點中，數據包可能的傳輸方向有9個，分別為O(本地)，E(東)，W(西)，S(南)，N(北)，SE(東南)，SW(西南)，NE(東北)，NW (西北)，具體如圖1所示.

2D-Torus片上網絡由于增加了首尾節點的連線，因此每一行及每一列都存在環路.路由方向也不再是簡單的東、西、南、北4個方向，傳統的禁止轉向技術不再適用.對于一個4×4的2D-Torus片上網絡，假定(0,0)節點在片上網絡的左下角，(3,3)節點在片上網絡的右上角.其拓撲結構如圖2所示.

圖1 路由節點的可能傳輸方向

設片上網絡系統中0維上的坐標為x，k代表每個維度上節點的數目，例如一個4×4的2D-Torus片上網絡，k=4，則x坐標的取值范圍是0≤x

圖2 4×4的2D-Torus片上網絡拓撲結構

定義TDF算法的規則如下：當節點的x<[k/2]時，數據禁止NW轉向和SW轉向；當節點的x≥[k/2]時，數據禁止NE轉向和SE轉向.數據在0列、k-1列、0行、k-1行這4條邊緣信道時，若數據由0列向k-1列路由，下一跳應向西(W)轉彎；若數據由0行向k-1行路由，當前節點為(0,0)，目的節點為(k-1,k-1)時，下一跳應向西(W)轉彎，其余情況下一跳應向南(S)轉彎；若數據由k-1列向0列路由，當前節點為(k-1,0)，目的節點為(0,k-1)，下一跳應向南(S)轉彎，當前節點為(k-1,k-1)，目的節點為(0,0)，下一跳應向北(N)轉彎，其余情況下一跳向東(E)轉彎；若數據由k-1行向0行路由，當前節點為(0,k-1)，目的節點為(k-1,0)時，下一跳應向西(W)轉彎，其余情況下一跳向北(N)轉彎.

以4×4的2D-Torus片上網絡為例，TDF路由算法的具體執行過程如下：

1) 若xd=x，yd=y，說明數據已經傳輸到目的節點，當前路由節點會將數據發送到其本地端口.

2) 若xd=x，yd

3) 若xd=x，yd>y，當y=0，yd=3，則數據應向南方向(S)路由，其余情況數據應該向北方向(N)路由，當前節點也會隨即將數據傳輸到北向輸出端口.

4) 若xd>x，y=yd，當x=0，xd=3，則數據應向西方向(W)路由，其余情況數據應該向東方向(E)路由，當前節點也會隨即將數據傳輸到東向輸出端口.

5) 若xd

6) 若xd>x，yd>y，當x≥[k/2]-1時，若y=0，yd=3,則數據應該向南方向(S)路由，若y≠0或yd≠3，則數據應該向北方向(N)路由；當x<[k/2]-1時,若y=0，yd=3，如果xd=3，則數據應該向西方向(W)路由，其余情況數據應該向南方向(S)路由，若y≠0或yd≠3，如果xd=3，數據應向西(W)路由，如果xd≠3，則數據應該向東方向(E)路由.

7) 若xd>x，yd

8) 若xdy，當y=0，yd=3時，數據應向南(S)路由，當y≠0或yd≠3時，如果x=3，xd=0,則數據應向東(E)路由，其余情況數據應向北(N)路由.

9) 若xd

10) 若xdy，如果y=0，yd=3，數據應向南(S)路由，如果y≠0或yd≠3，則數據應該向西(W)路由.

11)若xd

2 TDF路由算法無死鎖證明

由于面向片上網絡的Torus拓撲結構在網絡中存在多個環路，因此當數據包在路由節點間傳輸時容易產生死鎖.當相鄰的路由節點彼此請求對方進行數據轉發時，若數據包進入循環等待狀態，就會發生死鎖.例如，當某一路由節點接收到數據包，并將其存儲在緩存區中，數據包將根據路由算法請求下一跳的路由節點并申請緩存.若下一跳路由節點的接收通道被占據了，而占據該通道的數據包也正在等待被傳輸，并形成一個環路循環狀態.那么，這些數據包都會因為無法請求到下一跳路由節點而無法釋放當前路由節點的緩存，從而造成死鎖現象.分析可知，產生死鎖的根本原因在于數據包在路由傳輸過程中存在具有依賴性的環路.通常采用3種方法來避免死鎖：①通過設計路由算法來控制數據包的傳輸，限制路由方向，破除依賴性環路，從而避免死鎖現象.②通過使用虛通道來避免死鎖的發生.③通過檢測死鎖現象，強制破壞依賴性環路，從而限制死鎖的發生.本文提出的TDF算法就是通過設計路由算法來避免死鎖.

本文結合Dally[17]提出的通道依賴圖和Duato等[18]提出的無死鎖充分必要條件來證明本文提出的Torus片上網絡TDF路由算法的無死鎖特性.基于上述方法，對4×4的2D-Torus拓撲結構中各個路由節點的出入通路進行編碼標記，標記方案如圖3所示.該方案中將每條路由通道分成兩個方向，即路由節點的輸出通道與輸入通道.每一行的每一個方向上通道的x坐標都相同，每一列的每一個方向上通道的y坐標都相同.

圖3 路由路徑編碼

編碼完成后的2D-Torus片上網絡路由路徑編碼如圖4所示.

圖4 2D-Torus片上網絡路由路徑編碼

例如，(1,1)節點上方輸出通道編碼為(5,1)，輸入通道編碼為(7,2).假設有兩組路由數據A和B，數據A從路由節點(1,1)傳輸至路由節點(3,3)，數據B從路由節點(3,3)傳輸至路由節點(1,1).根據本文設計的路由算法規則，數據A的路由路徑為〈(1,1)(1,2)(1,3)(2,3)(3,3)〉，數據B的路由路徑為〈(3,3)(3,2)(3,1)(2,1)(1,1)〉，根據編碼規則可知數據A所經過的通道依次為〈(5,1)(5,2)(1,9)(2,9)〉，數據B所經過的通道依次為〈(9,3)(9,2)(3,5)(2,5)〉.由路由路徑可見，數據A所經過的路由通道在不同維度均嚴格遞增，數據B所經過的路由通道在不同維度均嚴格遞減，又根據編碼規則可知，該路由算法下數據在任意節點間傳輸所經路徑均為單調增或單調減，且不存在路徑交叉的情況，所以TDF路由算法是無死鎖的.

3 系統測試及結果分析

在Xilinx ISE 14.4開發環境下，基于System Verilog語言，設計并實現了4×4的基于2D-Torus拓撲結構，采用TDF路由算法的片上網絡，并對該片上網絡進行仿真測試與功能驗證.在FPGA的Xilinx Virtex-5硬件平臺上對系統性能進行測試.

在測試中，對路由節點進行編號，net_gen[i]表示坐標為(i%4,i/4)的路由節點，這里i為整數，則仿真中的net_gen[i]/…./output_port_(x)代表坐標為(i%4,i/4)的節點將數據從x端口輸出，net_gen[i]/…./input_port_(x)代表坐標為(i%4,i/4)的節點將數據從x端口輸入，x可以為O，W，S，E和N，其中O代表本地端口，W為西端口，S為南端口，E為東端口，N為北端口.例如b00net_gen[0]/…./output_port_(E)代表(0,0)節點將數據從東端口輸出，b32net_gen[11]/…./input_port_(S)代表(3, 2)節點將數據從南端口輸入.

3.1 單個節點傳輸測試分析

這里以數據從(0,1)節點向(3,3)節點的傳輸為例進行分析.單個節點傳輸波形如圖5所示.根據仿真波形圖中的信息，可以列出該過程的路由信息表如表1所示.

數據從(0,1)節點的本地端口輸入，接著從(0,1)節點即net_gen[4]的西端口輸出，從(3,1)節點即net_gen[7]的東端口輸入，然后從net_gen[7]的北端口輸出，從節點(3,2)即net_gen[11]的南端口輸入，接著從net_gen[11]的北端口輸出，從節點(3,3)即net_gen[15]的南端口輸入，最后從net_gen[15]的本地端口輸出.在路由的過程中，基于TDF路由算法的2D-Torus片上網絡共消耗了大約48個時鐘周期，而同樣結構的奇偶轉彎(odd-even)[9]片上網絡共消耗了大約55個時鐘周期.可知，TDF路由算法可以有效減少路由延遲時間.

圖5 單個節點傳輸波形圖

表1 〈(0,1),(3,3)〉路由信息表

3.2 多節點并行傳輸測試分析

測試中，分別從(3,3)，(2,1)，(0,3)節點向(0,1)，(0,3)，(3,1)節點傳輸數據，那么輸入數據的標志位應該分別為111110001,110010011和100111101.仿真結果如圖6所示.通過仿真結果可知，多組數據在4×4的2D-Torus片上網絡中能夠進行有效的傳輸，沒有產生死鎖現象.且目的節點的輸出數據與源節點的輸入數據相同，驗證了片上網絡在該路由算法作用下并行傳輸的準確率.

3.3 基于FPGA的片上網絡性能測試

以Genesys Vertex-5 系列的FPGA作為硬件平臺，設計并實現了本文提出的4×4的無死鎖2D-Torus片上網絡.無死鎖Torus片上網絡的硬件實物如圖7所示，源節點為(0,0)，目的節點為(3,3).測試結果表明，系統實物測試與仿真結果一致.

圖6 多節點并行傳輸測試仿真圖

圖7 無死鎖片上網絡FPGA硬件實物

4 結 論

本文針對2D-Torus拓撲結構，提出了一種基于列分轉彎模型的TDF路由算法，保證了數據包在片上網絡中的自適應路由條件.并對TDF路由算法的無死鎖性進行了理論證明.設計并實現了基于TDF路由算法的2D-Torus片上網絡系統，并在FPGA硬件平臺上對其進行了測試.實驗結果表明，基于TDF路由算法的片上網絡，路由算法無死鎖，且能夠實現多方向以及多節點的并行通信.片上網絡是未來片上多核系統的主流通信架構，因此基于2D-Torus拓撲結構及TDF路由算法的片上網絡具有較好的應用前景.