蘇 新，程 軍，劉 俞

（1. 馬鞍山職業(yè)技術學院 電子信息系，安徽 馬鞍山 243011；2. 巢湖學院 信息工程學院，安徽 合肥 238000）

0 引言

在電子通訊、多媒體處理等許多領域，片上系統(tǒng)（system-on-chip，SoC）將運算、存儲、通信、輸入輸出等功能集成在一起，提供了一種有效的解決方案。伴隨著半導體工藝的進步，集成度和復雜度不斷提升，數(shù)以百計的處理器被集成到單個芯片上，而對于基于共享總線通信架構的SoC，地址資源限制了功能模塊的擴展、線上延遲增加了全局時鐘樹的設計難度、共享總線通信機制降低了通信效率，SoC 的發(fā)展遇到了瓶頸。于是業(yè)界提出了一種新的通信架構：片上網(wǎng)絡（network-on-chip，NoC）［1］，它借鑒了計算機網(wǎng)絡互聯(lián)的思想，引入了分布式處理和并發(fā)通信技術，可有效提高通信效率，近年來成為研究熱點。

NoC 拓撲結構主要有二維拓撲結構（2D NoC）和三維拓撲結構（3D NoC），3D NoC 將不同電路單元制作在多個平面晶片上，通過硅通孔層間垂直互連技術（through-silicon-via，TSV）實現(xiàn)層間垂直堆疊互連，可以有效降低功耗、提高帶寬、增加集成度，因此3D NoC 將成為未來的發(fā)展趨勢。目前主流的3D NoC 拓撲包括3D Mesh、堆疊3D Mesh 和纖毛3D Mesh［2］。

路由算法是NoC 研究的關鍵技術之一，其設計依賴于網(wǎng)絡的拓撲結構。NoC 路由器運行路由算法，做路由決策，通過多個路由器可將數(shù)據(jù)包從源節(jié)點傳送到目標節(jié)點。路由算法的設計，對優(yōu)化網(wǎng)絡性能、提高系統(tǒng)吞吐量、降低功耗開銷都是非常有效的。DOR 算法［3］是傳統(tǒng)確定性路由算法的代表，數(shù)據(jù)包依次沿X軸、Y軸、Z軸到達目標節(jié)點所在的維度。DOR 算法思想簡單，當網(wǎng)絡負載較低時，使用該算法非常有效，但在網(wǎng)絡負載較高時，網(wǎng)絡的吞吐率低，傳輸時延長。Wang 等［4］提出了一種3D 輪轉路由算法，數(shù)據(jù)包先沿著Z軸的TSV 鏈路路由到目標節(jié)點所在層，在層內(nèi)傳輸時，通過路由器內(nèi)設置的翻轉標志的修改，平均分配X軸和Y軸的流量，在一定程度上可實現(xiàn)網(wǎng)絡流量分流，提高網(wǎng)絡吞吐量。RPM 算法［5］在Mesh 網(wǎng)絡階數(shù)為偶數(shù)時實現(xiàn)了最優(yōu)的最壞情況網(wǎng)絡吞吐率，且具有良好的平均網(wǎng)絡吞吐率。USM 路由算法［6］在Mesh 網(wǎng)絡階數(shù)為奇數(shù)時實現(xiàn)了最優(yōu)的最壞情況下的網(wǎng)絡吞吐率，但傳輸延時較高。

本文提出了一種3D Mesh 結構上的輸出輸入自適應路由算法（output input adaptive routing algorichm，OIARA）。本算法在當前節(jié)點全局上，根據(jù)7 個輸入端口內(nèi)待處理數(shù)據(jù)包對輸出端口的需求程度作為優(yōu)先級參數(shù)，優(yōu)先選擇需求程度最少的輸出端口，再在競爭該輸出端口的數(shù)據(jù)包集合內(nèi)授權總跳數(shù)最小的數(shù)據(jù)包。

1 相關工作

1.1 3D Mesh 拓撲結構

3D Mesh 拓撲結構是三維片上網(wǎng)絡最基本、最簡單的拓撲結構，其在2D Mesh 結構基礎上將各層之間通過TSV 鏈路連接拓展而形成3D Mesh 結構，圖1 為一個3 × 4 × 4 的3D Mesh 結構。3D Mesh 結構由于其具有擴展性好、結構簡單以及易實現(xiàn)等優(yōu)點而被廣泛使用。

1.2 路由器體系結構

路由器是片上網(wǎng)絡非常重要的組成部分（見圖2），路由器內(nèi)部通常包括路由邏輯模塊Routing Compute（RC）、仲 裁模塊Arbiter、交叉開關CrossBar、輸 入 端口Input Ports、輸出 端 口Output Ports 和寄存器等。路由器配置7 個輸入端口和7 個輸出端口，每個輸入端口配置2 個虛擬通道VC，以避免死鎖，每個虛擬通道容量等于整數(shù)個微片尺寸；7 × 7 交叉開關在輸入端口和輸出端口之間建立通信鏈路；RC 模塊收集信息，執(zhí)行路由算法，做路由決策；仲裁模塊功能包括虛擬通道仲裁VA 和交叉開關仲裁CA，VA 階段負責授權一個輸入端口，傳輸該端口上VC 內(nèi)的數(shù)據(jù)包，被選中的VC 優(yōu)先傳輸數(shù)據(jù)，同時，多個輸入端口選出的虛擬通道也存在對同一輸出端口的競爭，輸出端口的選擇在仲裁器的CA 階段完成。

圖1 3×4×4 3D Mesh 拓撲結構Fig.1 3×4×4 3D Mesh topology

圖2 路由器體系結構Fig.2 The architecture of the router

1.3 坐標系統(tǒng)與方位

圖1 所示的3D Mesh 結構中，示意了本文算法所依據(jù)的坐標系統(tǒng)。同時路由器體系結構中，數(shù)據(jù)包可被路由方位包括東、南、西、北、上、下以及本地7 個方向，坐標系統(tǒng)與方位的映射關系如表1 所示。

表1 坐標系統(tǒng)與方位映射關系Tab.1 The mapping relationship between coordinate system and position

1.4 相關定義

結合本文所提路由算法，對算法中涉及的相關概念、引用作以下規(guī)定：

定義13D NoC 中每個節(jié)點地址用三元組（Z，X，Y）標記，其中Z表示節(jié)點所在的層，X、Y表示層內(nèi)二維坐標。

定義2輸入端口內(nèi)數(shù)據(jù)包的目標節(jié)點（Zd，Xd，Yd）相對于當前節(jié)點（Zc，Xc，Yc）的曼哈頓距離稱為總跳數(shù)top，記為

這里，規(guī)定如果某個輸入端口沒有接收到任何數(shù)據(jù)包，則將對應的目標地址用(∞,∞,∞)表示，那么7 個輸入端口待處理數(shù)據(jù)包的總跳數(shù)可以構成一個長度為7 的一維數(shù)組top［7］。

定義3用一個7 × 6 的矩陣表示7 個輸入端口內(nèi)待處理數(shù)據(jù)包，按照靠近目標節(jié)點的原則，所可能走的6 個方向稱之為方向矩陣Direct。

說明：對于Direct［i］［j］元素，i表示輸入端口，j表示可選方向。若元素值為1，表示數(shù)據(jù)包從第i個輸入端口，可以走j方向靠近目標；若元素值為0，表示數(shù)據(jù)包從第i個輸入端口，不可以走j方向靠近目標；若元素值為-1，表示第i個輸入端口沒有待處理數(shù)據(jù)。表2 所示為數(shù)組的行坐標與輸入端口映射關系，表3 所示為列坐標與方向的映射關系。

表2 行坐標與輸入端口映射關系Tab.2 The mapping relationship between row coordinates and input port

表3 列坐標與方向的映射關系Tab.3 Teh mapping relationship between column coordinates and output port

例如，圖3 所示的案例中，第4 行表示W(wǎng)est 輸入端口，其列坐標0，1，4 上元素值為1，表示該數(shù)據(jù)包可以被路由到Up、Down、North 3 個方向；第7 行元素值全為-1，表示Local 端口上沒有待處理的數(shù)據(jù)包。

圖3 Direct數(shù)組案例Fig.3 Directarray case

2 OIARA 算法設計

2.1 算法總體思路

路由器在做路由決策前，路由節(jié)點的仲裁模塊需要授權輸入端口，并選擇輸出端口，對于輸入端口的授權，DOR 算法以及大部分算法采用了時間片輪轉［7］的方法，輸出端口選擇有維序法［3］（如DOR 算法）、隨機法（如DPT 算法［7］）等。

本文算法從當前路由節(jié)點全局考慮，在仲裁模塊授權輸入端口和選擇輸出端口時，都采用優(yōu)先級確定。根據(jù)當前節(jié)點所有端口內(nèi)數(shù)據(jù)包對輸出端口的需求程度情況，需求越高表示該端口競爭越大，在選擇輸出端口時，優(yōu)先選擇需求程度低的端口輸出；然后在競爭選中的輸出端口數(shù)據(jù)包集合內(nèi)，授權總跳數(shù)最小的數(shù)據(jù)包來傳輸，如此可以在交叉開關內(nèi)為授權的輸入端口和選擇的輸出端口建立鏈路，傳輸數(shù)據(jù)，總跳數(shù)用定義2 中的曼哈頓距離來表示。算法在對輸入端口授權以及輸出端口選擇時，采用貪心算法思想，每次選出的都是需求程度最不迫切的輸出端口和總跳數(shù)最小的數(shù)據(jù)包，可以盡快處理網(wǎng)絡內(nèi)積壓的數(shù)據(jù)包，提高網(wǎng)絡整體吞吐量。

2.2 算法實現(xiàn)

本算法分為兩個階段，第一個階段是對數(shù)據(jù)結構初始化，主要包括總跳數(shù)數(shù)組top和方向矩陣Direct；第二個階段負責在7 個輸入端口中授權其中一個端口并匹配一個輸出端口。如此可以在路由器交叉開關內(nèi)建立傳輸鏈路，將授權的輸入端口內(nèi)數(shù)據(jù)包傳送到輸出端口。算法的主要偽代碼如下：

2.3 舉例

假設在一個4 × 4 × 4 的3D Mesh 結構中，當前路由節(jié)點的坐標是（2，1，2），路由器的上、下、東、西、北、南以及本地7 個輸入端口中的數(shù)據(jù)包目標地址分別是（0，1，3），（∞，∞，∞），（3，2，1），（1，2，3），（2，1，2），（2，2，3），（0，2，0），即下方輸入端口沒有數(shù)據(jù)包，北方輸入端口和本地端口地址相同，表示當前節(jié)點就是目標節(jié)點，不考慮算法執(zhí)行過程中有新數(shù)據(jù)包到達，那么根據(jù)本算法思路，在對top數(shù)組和Direct數(shù)組初始化后，其中top［4］= 0，即北輸入端口輸入的數(shù)據(jù)包目標節(jié)點是本地，優(yōu)先路由到本地節(jié)點處理，此時output = 6，input = 4；第二個數(shù)據(jù)包處理時，根據(jù)Direct數(shù)組統(tǒng)計得到的count數(shù)組中，count［0］= 1 最?。ú缓扔?），因此output = 0，選擇Up 輸出端口，而競爭Up 輸出端口的數(shù)據(jù)包只有一個，即East 輸入端口，因此input = 2，依次類推，可得當前路由節(jié)點處理數(shù)據(jù)包的順序見表4。

表4 案例處理結果Tab.4 The result of case processing

2.4 死鎖避免

自適應路由算法容易造成死鎖，當多個數(shù)據(jù)包在網(wǎng)絡中傳輸時，可能因為包的傳輸路徑形成環(huán)，彼此等待對方釋放資源卻又各自占有資源從而導致死鎖［8］。文獻［9］使用了在雙虛擬通道中添加不同的傳輸方向限制避免死鎖，本文算法基于雙虛擬通道路由器，引入雙虛擬通道技術解決死鎖。如圖4 所示，在一個平面上，數(shù)據(jù)包A 的兩個微片A1、A2 分別占用了路由器R1 的南輸入端口和東輸出端口的其中一個虛擬通道緩存，數(shù)據(jù)包B 的兩個微片B1、B2 分別占用了路由器R2的西輸入端口和南輸出端口的其中一個虛擬通道緩存，數(shù)據(jù)包C 和數(shù)據(jù)包D 也是類似的情況，但此時由于引入了虛擬通道技術，一條物理通道被劃分成兩條邏輯通道，數(shù)據(jù)包分時復用物理通道，在每一個端口還有一個虛擬通道緩存可以使用，從而使4 個數(shù)據(jù)包都可以繼續(xù)傳送。

圖4 雙虛擬通道技術解決死鎖Fig.4 Double virtual channel for solving the deadlock

3 仿真結果與分析

3.1 仿真環(huán)境

本文算法模擬實驗采用了基于System C 語言開發(fā)的仿真器Nirgam［10］。從芯片面積和死鎖兩方面綜合考慮，實驗中路由器使用雙虛擬通道路由器，每個虛擬通道的深度是8，寬度為32 bits，即1 個微片的尺寸，每個數(shù)據(jù)包劃分成8 個微片，實驗模型為4 × 4 × 4 3D Mesh 結構，分別在兩種不同的流量模式下：熱點注入模式和均勻注入模式，調(diào)節(jié)數(shù)據(jù)包的注入率。通過OIARA 算法與DOR算法、文獻［4］的3D 輪轉算法相比對，以平均時延和吞吐率兩個片上網(wǎng)絡的重要指標作分析。

3.2 數(shù)據(jù)包結構

實驗使用蟲孔交換機制，每個數(shù)據(jù)包分成8 個微片，每個微片尺寸為32 bits，微片包括頭微片Head、體微片Body 和尾微片Tail，頭尾片中由微片類型、數(shù)據(jù)包id、微片id，到目標節(jié)點的距離Top，目標節(jié)點的坐標等字段組成，如圖5 所示，路由算法只根據(jù)頭微片的信息計算路由，體微片和尾微片沿著相同的路徑傳輸。

圖5 數(shù)據(jù)包格式Fig.5 Format of the data packet

3.3 平均時延

一個數(shù)據(jù)包的時延是指數(shù)據(jù)包從注入到源節(jié)點開始到被目標節(jié)點接收所經(jīng)歷的時間T，主要由數(shù)據(jù)包在鏈路上的傳輸時間Ttransport、數(shù)據(jù)包在節(jié)點內(nèi)排隊時間Twait和數(shù)據(jù)包的發(fā)送時間Tsend組成，即T=Ttransport+Twait+Tsend，其中Tsend忽略不計。仿真時間內(nèi)所有數(shù)據(jù)包時延的平均值為整個網(wǎng)絡的平均時延［11］，平均時延越小，表明網(wǎng)絡性能越好，平均時延大，表示數(shù)據(jù)包等待時間長，網(wǎng)絡可能產(chǎn)生擁堵。

圖6 所示在均勻流量注入模式下，在注入率較低時，本算法和DOR 算法及3D 輪轉算法平均時延相差不大，當注入率達到0.012，網(wǎng)絡內(nèi)微片數(shù)量增多，DOR 算法先沿某個方向走完再轉向，處理數(shù)據(jù)微片開始顯得乏力，在注入率超過0.016 后，由于本算法和3D 輪轉算法基于了分流的思想，平均時延明顯低于DOR 算法。圖7 顯示了在熱點模式下的仿真結果，在網(wǎng)絡中隨機選擇8個節(jié)點作為熱點注入數(shù)據(jù)包，由于網(wǎng)絡內(nèi)在局部迅速產(chǎn)生大量微片，DOR 算法難以快速解決，本算法能夠從多個方向分流，也略優(yōu)于3D 輪轉算法，最好情況下可以從7 個不同的方向輸出，減少了排隊等待的時間，平均時延更低，但是因為網(wǎng)絡局部范圍內(nèi)迅速出現(xiàn)大量數(shù)據(jù)，造成擁堵的觸發(fā)點提前了。

圖6 均勻流量模式下平均時延對比Fig.6 Comparison of average delay in uniform traffic mode

圖7 熱點流量模式下平均時延對比Fig.7 Comparison of average delay in hot traffic mode

3.4 網(wǎng)絡吞吐率

網(wǎng)絡吞吐率體現(xiàn)了網(wǎng)絡承載數(shù)據(jù)的能力［11］，用每個節(jié)點在每個時鐘周期內(nèi)傳輸微片的數(shù)量來度量［9］，公式為其中Li表示第i個數(shù)據(jù)包的長度，N為網(wǎng)絡的總節(jié)點數(shù)，T是仿真時間，單位是時鐘周期。網(wǎng)絡吞吐率的單位是flit/cycle/node。

圖8和圖9分別是均勻模式和熱點模式下吞吐率的對比，可以看到，本算法可以從7 個方向分流，3D 輪轉算法則是在層內(nèi)傳輸時輪轉，因此本算法吞吐率略高，當注入率達到一定值后，本文方法的吞吐率明顯高于DOR 算法

圖8 均勻模式下吞吐率對比Fig.8 Comparison of throughput in uniform traffic mode

圖9 熱點模式下吞吐率對比Fig.9 Comparison of throughput in hot traffic mode

4 結語

本文針對3D Mesh 結構，不考慮節(jié)點故障和鏈路故障，提出了一種自適應的路由算法OIARA，算法在處理數(shù)據(jù)包時可以從多個方向分流，同時每一步路由決策基于貪心算法思想保持當前節(jié)點狀態(tài)下最優(yōu)。仿真結果可以看到，OIARA 算法在網(wǎng)絡平均時延和網(wǎng)絡吞吐率兩個重要的NoC 評價指標方面，都優(yōu)于傳統(tǒng)的維序算法。