一種二維片上網絡路由器的設計實現

(上海大學 微電子研究與開發中心，上海 200444)

0 引言

隨著半導體工藝的發展與集成度的提高，單芯片上的晶體管數量越來越多[1-2]，芯片的規模與日俱增。為了滿足多媒體、網絡通信與大數據計算的需求，目前多核片上系統(MPSoC)普遍采用總線互連的方式集成數個處理器核與功能IP核，并向著眾核片上系統發展。片上網絡技術采用包交換與分層的方式代替傳統的總線，實現了IP核與互連層之間的分離，相對總線互連具有拓展性高、可靠性高與功耗低的特點，已經成為眾核互連的主流解決方案[3-6]。片上網絡互連層主要由通信鏈路，路由器節點與網絡接口3個部分組成。拓撲結構與路由器效能直接決定網絡的整體性能。因此，針對片上網絡互連層的研究，特別是基于特定拓撲結構的路由器硬件設計，是一種提升NoC性能的有效途徑[7-8]。

1 NoC體系結構

NoC的互連層與分布式計算機系統的互連網絡有相似之處，如支持包交換、擁有路由協議與高可拓展性等。由于NoC內部的IP核通過數字電路工藝互連，與分布式計算機采用的物理線路互連差別較大，這讓NoC發展出了獨有的拓撲結構，路由算法、數據格式與流控策略。

1.1 NoC拓撲結構

拓撲結構是片上網絡互連層研究的一個重要領域，拓撲結構的類型會直接對網絡整體性能與硬件實現造成顯著的影響。例如，網絡拓撲決定片上網絡路由器節點與通信鏈路的空間分布和互連布局，會影響到數據微片的路由路徑距離和每跳路由的線路長度。拓撲結構也決定源節點與目的節點之間的路由路徑跳數與鏈路資源數量，會對數據流量的分布與路由器的負載分布造成直接影響，與網絡吞吐率等性能指標關系緊密。

NoC拓撲結構主要分為規則拓撲結構與不規則拓撲結構。常見的拓撲結構有2D Mesh結構、2D Tours結構與Octagon結構等。由于2D Mesh拓撲結構擁有良好的拓展性、結構規整、容易實現高效的路由計算與仲裁，因此本文基于2D Mesh拓撲進行路由器的設計研究。基于2D Mesh的NoC如圖1所示，其路由器節點擁有5組輸入輸出端口，4組端口用于與相鄰由器的連接，本地端口則通過網絡接口與IP核相連。

圖1 Mesh拓撲結構圖

1.2 NoC路由算法

路由算法確定數據包下一跳路由所需要的輸出端口，能夠將數據從源節點準確的傳輸到目的節點，是影響片上網絡性能的重要因素。NoC路由算法的電路實現不能太復雜，因為復雜的電路會增加關鍵路徑的延時，占用更多的硬件面積，并增加功耗。路由算法按照是否具有適應性可分為自適應路由算法與確定性路由算法。

自適應路由算法是研究的熱點，其規劃的路徑不僅與源節點和目的節點的相對位置有關，還受到網絡的狀態，如溫度[9-10]、功耗[11]、緩存空間與路由器負載的影響。在已知源節點與目的節點位置的情況下，自適應路由算法會實時感知網絡狀態，規劃最優路徑傳輸數據。此類算法的優點是能夠較好的避免數據擁塞，獲得更高的片內通信吞吐率。其缺點是路由邏輯復雜，需要特殊的硬件結構，硬件實現的難度巨大，而且存在死鎖與感知滯后問題。

確定性路由算法實現簡單，在網絡低負載條件下能夠獲得較小的延時，且不會產生死鎖，能夠滿足大部分數據傳輸任務的需求，所以本文采用XY確定性路由算法。該算法首先在X維度上路由，當數據包與達目的節點處于同一列時，再進行Y維度上的路由，從而達到目的節點。

1.3 NoC數據格式

數據包的最小組成單位是微片，其分為頭微片、體微片與尾微片。對于本文設計的路由器，規定微片位寬為32bit，具體格式如表1所示。位于[33:32]的數值用于區分微片種類(00為頭微片，01為體微片，11為尾微片)。頭微片攜帶著源節點地址(SY，SX)、目的節點地址(DY，DX)和有效數據長度等附加信息。地址每個維度位寬為4，最多支持256個節點。體微片和尾微片不攜帶路由信息，它們沿著頭微片建立的路徑傳輸到目的節點。

1.4 NoC流控機制

片上網絡主要的流控機制有電路交換技術，儲存轉發交換技術，虛直通交換技術與蟲孔交換技術。電路交換技術、儲存轉發交換技術與虛直通交換技術均存在資源利用率不高、串行化延遲較大與硬件資源消耗較多等問題[12]。因此，綜合慮資源與功耗等方面的因素，本文選用蟲孔交換技術作為路由器的流控機制。

蟲孔交換技術以微片作為數據傳輸的最小粒度，并將數據包劃分成多個微片(flits)。頭微片(head flit)存儲路由信息，包括數據包的源節點、目的節點等控制信息。頭微片后面的微片按照流水的順序跟隨頭微片在傳輸路徑中行進。某個鏈路上的微片傳輸完成后，該鏈路就會被解除占用。每一個路由器節點的僅需若干個微片大小的緩存空間，當下一級路由器緩存尚有空間是就立刻發送微片。如果傳輸過程中網絡發生了擁塞，數據包的后續微片會暫存在后面的各個路由器節點。當網絡出現擁塞時，會有較多的路由器節點與鏈路被占用，采用蟲孔交換方式在網絡產生比較嚴重的擁塞時候還會產生死鎖。后續路由節點的緩存單元只有一個微片的空間時，蟲孔交換仍然能傳送數據包。如圖2所示，當路由器節點0與路由器節點1在網絡不存在擁塞時，應用蟲孔交換與虛直通的表現相同。但是，當網絡出現擁塞時，兩種流控機制會有不同的表現。如圖2所示，盡管在時鐘周期2路由器節點2的緩存空閑空間(2個微片的空間)無法容納整個數據包，路由器節點2仍然可以傳輸頭微片與第一個數據微片。當路由器節點1和路由器節點2之間的鏈路在第4與第5個時鐘周期內均處于空閑狀態時，這條鏈路也無法被其它傳輸任務使用，直到第7個時鐘周期時尾微片完成傳輸。因此，在蟲孔交換機制下，數據包會以微片的組成形式保存在一系列的路由器節點中，但其傳輸路徑中的鏈路通道會一直被該數據包傳輸任務使用。組成數據包的微片均不會丟失或受到其他數據包傳輸任務的干擾，數據包能夠保持自身完整性。

圖2 蟲孔交換流控機制

2 路由器設計

確定片上網絡互連層的主要技術特征，包括拓撲結構、路由算法后，就要對路由器硬件進行研究設計。路由器是片上網絡互連層的主要部件，也是片上網絡的關鍵部件，主要負責數據的暫存與轉發。其主要模塊有輸入緩存模塊、輸出端口、路由計算模塊、交叉開關模塊與路由仲裁模塊等，具體如圖3所示。路由器輸入輸出端口用于連接相鄰路由器與本地IP核，對于本文的2D Mesh拓撲結構，對應路由器擁有五個方向的輸入輸出端口，分別是本地(Local，L)、東(East，E)、西(West，W)、南(South，S)與北(North，N)。當數據微片進入路由器的緩存后，路由計算模塊根據微片輸入端口位置、當前路由器的位置信息、源節點與目的節點信息以及路由器狀態，按照硬件固化的路由算法進行路徑規劃，建立路由器輸入端口與輸出端口的連接。

表1 數據包格式

圖3 路由器結構圖

2.1 輸入緩存模塊

輸入緩存模塊的作用是緩存相鄰路由器以及本地計算IP核發送的數據。對于文中的2D Mesh片上網絡，需要有5組緩存單元來滿足北(N)、南(S)、東(E)、西(W)與本地(L)方向輸入微片的緩存。緩存單元的位寬等于微片的位寬，緩存單元的深度可以根據網絡面向的應用與路由算法進行調整，其作用是將依次接受到的微片按需順序輸出。由于片上網絡支持異步全局，局部同步的設置，也需要用緩存模塊來保證片內互連層，即路由網絡與資源IP核的跨時鐘域數據傳輸。結合以上幾點，每個數據通道的緩存單元均用先進先出(first in first out)的異步FIFO實現。圖4是經典的異步FIFO硬件結構，它主要由一個雙端口的RAM、寫控制模塊、讀控制模塊與同步邏輯組成。雙端口RAM主要用于數據微片的緩存，寫控制模塊和讀控制模塊主要作用是響應外部設備發出的讀寫請求、讀寫指針的產生和格雷碼轉換，并根據讀寫指針位置輸出表示FIFO滿或空的信號。由讀控制模塊和寫控制模塊輸出的格雷碼指針信號會進入同步邏輯，同步邏輯會將格雷碼格式的讀指針或者寫指針同步到寫模塊和讀模塊用于產生空或者滿信號。

圖4 FIFO結構圖

2.2 路由計算模塊

路由算法的實現載體是片上網絡路由器的路由計算模塊，算法會以數字電路的形式固化在路由計算模塊中。路由計算模塊會綜合數據包頭微片包含的信息與路由算法來計算微片的輸出端口。本文的路由計算模塊是XY路由算法的硬件實現。它的運算過程是：路由計算模塊首先依據微片里的Type位信息判斷該微片是否為頭微片。如果是頭微片，路由計算單元就會依據頭微片包含的源節點、目的節點與固化的路由算法計算出微片的輸出端口，并向控制交叉開關的仲裁模塊提交相應的申請信號。如果微片類型為體微片或者尾微片，則不進行路由計算，直接提交輸出端口使用申請。

對于本文應用的XY路由算法，首先需要解析頭微片中包含的目的節點信息，隨后與當前節點的位置信息進行比較。接著判斷當前節點與目的節點的X坐標大?。寒斍肮濣cX坐標小于目的節點時，向X正方向路由；當前節點X坐標大于目的節點時，向X負方向路由；當前節點X坐標等于目的節點時，接著判斷當前節點與目的節點Y坐標的大小。當前節點Y坐標小于目的節點時，向Y正方向路由；當前節點Y坐標小于目的節點時，向Y負方向路由；當前節點Y坐標等于目的節點時，表明數據微片到達目的節點，停止路由。

2.3 路由仲裁模塊

在片上網絡運行的過程中，同時存在多對IP核進行數據的發送與接收，部分路由器節點會因此同時接收到多個頭微片。路由計算單元讀取頭微片的附加信息，計算出結果后向路由仲裁單元申請交叉開關的使用權。路由仲裁單元批準某一輸入端口的請求后，會向交叉開關發送對應的控制信號，建立固定的輸入輸出端口連接，并發送緩存讀取信號讀取微片數據，輸入交叉開關對應的輸入端，使微片從指定端口輸出。

路由仲裁單元會在同一時刻收到某輸出端口的多個使用請求，需要設計仲裁策略進行處理。仲裁策略一般分為固定優先級仲裁策略與輪詢仲裁策略(Round-Robin，RR)。固定優先級策略賦予每個輸入通道固定的優先級，如輸入通道的優先級從高至低依次為北(N)、南(S)、西(W)、東(E)、本地(L)。一旦北(N)輸入通道需要使用某輸出端口時，不管剩余輸入通道是否請求使用該端口，總是響應北(N)通道的請求。固定優先級策略的硬件實現較為簡單，但不會均衡資源的分配。輪詢仲裁策略(Round-Robin，RR)會對輸入通道設置默認的優先級，在首輪仲裁中會對提出請求的通道

進行比較，批準最高優先級通道的請求。隨后，該通道的優先級降至最低，優先級比該通道低的端口依次提升優先級別，原理如圖5所示。在圖5中，路由器輸入通道的默認優先級為北(N)，南(S)，西(w)，東(E)與本地(L)。五個通道會用相應的Req_n、Req_s、 Req_w、Req_e與Req_l信號表示對輸出端口的申請。在圖5中，對于第一次仲裁，由于北(N)通道的優先級是最高的，即使北(N)、南(S)、西(W)、東(E)與本地(L)通道均發起申請，仲裁的結果仍為批準北(N)方通道的請求。仲裁結束后，北(N)方通道的優先級降到最低，其余通道的優先級依次提升。對于第二次仲裁，只有南(S)、西(W)、東(E)與本地(L)方向輸入通道的請求信號數據。根據第一次仲裁過后的優先級，仲裁分配單元批準南(S)方向通道的請求。仲裁器響應全部申請流程的波形如圖6所示，可以看到仲裁器會按照優先級依次批準申請。

圖5 輪詢仲裁示意圖

圖6 輪詢仲裁波形圖

2.4 交叉開關模塊

交叉開關模塊是數據路由器的核心結構，其作用是建立各輸入通道緩存單元與輸出端口的連接，使某端口的輸入數據從指定端口輸出。由于二維片上網絡路由器有5組輸入輸出通道，交叉開關會有5組輸入端口與5組輸出端口的控制信號接口。二維片上網絡路由器的交叉開關可以看做5個5輸入多路選擇器的組合。每個多路選擇器的輸入端對應5個通道的輸入，輸出端對應特定方向上的輸出端口，其會按照控制信號輸出指定輸入通道的內容。交叉開關模塊的控制信號則來源于路由仲裁模塊，具體結構如圖7所示。

圖7 交叉開關結構圖

交叉開關的工作波形如圖8所示，5個輸入通道分別輸入不同的微片。測試時對于每個輸出通道對應的多路選擇器，輸入了特定的激勵信號使得同方向輸入端口數據被原路輸出，以便觀察。例如本地(L)通道輸入32’h40044000，在向本地(L)輸出端的多路選擇器控制信號端(Sel_l)輸入相應的控制信號后，本地(L)輸出端就會輸出32’h40044000。

圖8 交叉開關波形圖

3 仿真與結果分析

路由器仿真驗證是片上網絡仿真的一個重要環節，為了確保NoC路由器的設計符合目標，本文采用Verilog HDL實現了路由器的各個模塊，并在Modelsim 10.1中對模塊進行了測試，最后進行了路由器整體測試。

圖9是路由器整體測試波形圖，為了顯示清晰，數據包采用3個微片的長度。假設路由器所在節點為(3，3)，對于東(E)方向通道輸入的數據包，解析其頭微片信息可知其目的節點為(2，2)。根據XY路由算法可知路由器節點應該向X軸負方向路由數據包，即將數據包從西(W)方向端口輸出至(2，3)節點。圖8中西(W)方向端口以流水的方式輸出東(E)方向輸入的數據包，證明路由器工作正常。為了測試路由器中的路由仲裁模塊與交叉開關模塊功能，在五個方向上的輸入端口均輸入了數據包。實驗結果表明，路由器能夠建立各端口的輸入輸出連接，交叉開關模塊與仲裁模塊的功能符合設計目標。

圖9 路由器波形圖

4 結束語

NoC是未來眾核芯片的主流架構，而路由器又是NoC片內互連的關鍵部件，因此研究路由器的設計實現有著重要的意義。本文提出了一種可應用于2D Mesh拓撲結構，采用輪詢仲裁機制與蟲孔交換流控的片上網絡路由器設計。隨后對路由器的輸入緩存模塊、交叉開關模塊、路由計算模塊與路由仲裁模塊進行了硬件設計與仿真，最后對路由器整體功能進行測試。實驗結果表明，該路由器設計工作正常，能夠正確收發數據包。