一種二維片上網(wǎng)絡(luò)路由器的設(shè)計實現(xiàn)

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

0 引言

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

1 NoC體系結(jié)構(gòu)

NoC的互連層與分布式計算機系統(tǒng)的互連網(wǎng)絡(luò)有相似之處，如支持包交換、擁有路由協(xié)議與高可拓展性等。由于NoC內(nèi)部的IP核通過數(shù)字電路工藝互連，與分布式計算機采用的物理線路互連差別較大，這讓NoC發(fā)展出了獨有的拓撲結(jié)構(gòu)，路由算法、數(shù)據(jù)格式與流控策略。

1.1 NoC拓撲結(jié)構(gòu)

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

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

圖1 Mesh拓撲結(jié)構(gòu)圖

1.2 NoC路由算法

路由算法確定數(shù)據(jù)包下一跳路由所需要的輸出端口，能夠?qū)?shù)據(jù)從源節(jié)點準確的傳輸?shù)侥康墓?jié)點，是影響片上網(wǎng)絡(luò)性能的重要因素。NoC路由算法的電路實現(xiàn)不能太復雜，因為復雜的電路會增加關(guān)鍵路徑的延時，占用更多的硬件面積，并增加功耗。路由算法按照是否具有適應(yīng)性可分為自適應(yīng)路由算法與確定性路由算法。

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

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

1.3 NoC數(shù)據(jù)格式

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

1.4 NoC流控機制

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

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

圖2 蟲孔交換流控機制

2 路由器設(shè)計

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

表1 數(shù)據(jù)包格式

圖3 路由器結(jié)構(gòu)圖

2.1 輸入緩存模塊

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

圖4 FIFO結(jié)構(gòu)圖

2.2 路由計算模塊

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

對于本文應(yīng)用的XY路由算法，首先需要解析頭微片中包含的目的節(jié)點信息，隨后與當前節(jié)點的位置信息進行比較。接著判斷當前節(jié)點與目的節(jié)點的X坐標大小：當前節(jié)點X坐標小于目的節(jié)點時，向X正方向路由；當前節(jié)點X坐標大于目的節(jié)點時，向X負方向路由；當前節(jié)點X坐標等于目的節(jié)點時，接著判斷當前節(jié)點與目的節(jié)點Y坐標的大小。當前節(jié)點Y坐標小于目的節(jié)點時，向Y正方向路由；當前節(jié)點Y坐標小于目的節(jié)點時，向Y負方向路由；當前節(jié)點Y坐標等于目的節(jié)點時，表明數(shù)據(jù)微片到達目的節(jié)點，停止路由。

2.3 路由仲裁模塊

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

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

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

圖5 輪詢仲裁示意圖

圖6 輪詢仲裁波形圖

2.4 交叉開關(guān)模塊

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

圖7 交叉開關(guān)結(jié)構(gòu)圖

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

圖8 交叉開關(guān)波形圖

3 仿真與結(jié)果分析

路由器仿真驗證是片上網(wǎng)絡(luò)仿真的一個重要環(huán)節(jié)，為了確保NoC路由器的設(shè)計符合目標，本文采用Verilog HDL實現(xiàn)了路由器的各個模塊，并在Modelsim 10.1中對模塊進行了測試，最后進行了路由器整體測試。

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

圖9 路由器波形圖

4 結(jié)束語

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