基于FPGA的2D-Torus片上網(wǎng)絡(luò)無死鎖路由算法

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

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

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

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

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

1 TDF路由算法描述

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

2D-Torus片上網(wǎng)絡(luò)由于增加了首尾節(jié)點的連線，因此每一行及每一列都存在環(huán)路.路由方向也不再是簡單的東、西、南、北4個方向，傳統(tǒng)的禁止轉(zhuǎn)向技術(shù)不再適用.對于一個4×4的2D-Torus片上網(wǎng)絡(luò)，假定(0,0)節(jié)點在片上網(wǎng)絡(luò)的左下角，(3,3)節(jié)點在片上網(wǎng)絡(luò)的右上角.其拓?fù)浣Y(jié)構(gòu)如圖2所示.

圖1 路由節(jié)點的可能傳輸方向

設(shè)片上網(wǎng)絡(luò)系統(tǒng)中0維上的坐標(biāo)為x，k代表每個維度上節(jié)點的數(shù)目，例如一個4×4的2D-Torus片上網(wǎng)絡(luò)，k=4，則x坐標(biāo)的取值范圍是0≤x

圖2 4×4的2D-Torus片上網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

以4×4的2D-Torus片上網(wǎng)絡(luò)為例，TDF路由算法的具體執(zhí)行過程如下：

1) 若xd=x，yd=y，說明數(shù)據(jù)已經(jīng)傳輸?shù)侥康墓?jié)點，當(dāng)前路由節(jié)點會將數(shù)據(jù)發(fā)送到其本地端口.

2) 若xd=x，yd

3) 若xd=x，yd>y，當(dāng)y=0，yd=3，則數(shù)據(jù)應(yīng)向南方向(S)路由，其余情況數(shù)據(jù)應(yīng)該向北方向(N)路由，當(dāng)前節(jié)點也會隨即將數(shù)據(jù)傳輸?shù)奖毕蜉敵龆丝?

4) 若xd>x，y=yd，當(dāng)x=0，xd=3，則數(shù)據(jù)應(yīng)向西方向(W)路由，其余情況數(shù)據(jù)應(yīng)該向東方向(E)路由，當(dāng)前節(jié)點也會隨即將數(shù)據(jù)傳輸?shù)綎|向輸出端口.

5) 若xd

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

7) 若xd>x，yd

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

9) 若xd

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

11)若xd

2 TDF路由算法無死鎖證明

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

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

圖3 路由路徑編碼

編碼完成后的2D-Torus片上網(wǎng)絡(luò)路由路徑編碼如圖4所示.

圖4 2D-Torus片上網(wǎng)絡(luò)路由路徑編碼

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

3 系統(tǒng)測試及結(jié)果分析

在Xilinx ISE 14.4開發(fā)環(huán)境下，基于System Verilog語言，設(shè)計并實現(xiàn)了4×4的基于2D-Torus拓?fù)浣Y(jié)構(gòu)，采用TDF路由算法的片上網(wǎng)絡(luò)，并對該片上網(wǎng)絡(luò)進(jìn)行仿真測試與功能驗證.在FPGA的Xilinx Virtex-5硬件平臺上對系統(tǒng)性能進(jìn)行測試.

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

3.1 單個節(jié)點傳輸測試分析

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

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

圖5 單個節(jié)點傳輸波形圖

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

3.2 多節(jié)點并行傳輸測試分析

測試中，分別從(3,3)，(2,1)，(0,3)節(jié)點向(0,1)，(0,3)，(3,1)節(jié)點傳輸數(shù)據(jù)，那么輸入數(shù)據(jù)的標(biāo)志位應(yīng)該分別為111110001,110010011和100111101.仿真結(jié)果如圖6所示.通過仿真結(jié)果可知，多組數(shù)據(jù)在4×4的2D-Torus片上網(wǎng)絡(luò)中能夠進(jìn)行有效的傳輸，沒有產(chǎn)生死鎖現(xiàn)象.且目的節(jié)點的輸出數(shù)據(jù)與源節(jié)點的輸入數(shù)據(jù)相同，驗證了片上網(wǎng)絡(luò)在該路由算法作用下并行傳輸?shù)臏?zhǔn)確率.

3.3 基于FPGA的片上網(wǎng)絡(luò)性能測試

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

圖6 多節(jié)點并行傳輸測試仿真圖

圖7 無死鎖片上網(wǎng)絡(luò)FPGA硬件實物

4 結(jié) 論

本文針對2D-Torus拓?fù)浣Y(jié)構(gòu)，提出了一種基于列分轉(zhuǎn)彎模型的TDF路由算法，保證了數(shù)據(jù)包在片上網(wǎng)絡(luò)中的自適應(yīng)路由條件.并對TDF路由算法的無死鎖性進(jìn)行了理論證明.設(shè)計并實現(xiàn)了基于TDF路由算法的2D-Torus片上網(wǎng)絡(luò)系統(tǒng)，并在FPGA硬件平臺上對其進(jìn)行了測試.實驗結(jié)果表明，基于TDF路由算法的片上網(wǎng)絡(luò)，路由算法無死鎖，且能夠?qū)崿F(xiàn)多方向以及多節(jié)點的并行通信.片上網(wǎng)絡(luò)是未來片上多核系統(tǒng)的主流通信架構(gòu)，因此基于2D-Torus拓?fù)浣Y(jié)構(gòu)及TDF路由算法的片上網(wǎng)絡(luò)具有較好的應(yīng)用前景.