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

山 蕊，蔣 林，杜慧敏，鄧軍勇

（1.西安郵電學(xué)院 電子工程學(xué)院，陜西 西安 710061；2.西安郵電學(xué)院 研究生學(xué)院，陜西 西安 710061）

隨著設(shè)計復(fù)雜度的提高，以總線為通信基礎(chǔ)設(shè)施的SoC面臨著全局連線增長、延遲增加、擴展性能變差、全局同步困難等問題，近些年來，學(xué)術(shù)界提出采用片上網(wǎng)絡(luò)（Network on Chip，NoC）來解決SoC所面臨的問題。 在片上網(wǎng)絡(luò)的研究中，結(jié)點之間的通信延時一直是研究的熱點，目前普遍采用虛通道流控機制來降低通信延時[1-2]。作為片上網(wǎng)絡(luò)的核心部件包交換路由器，其設(shè)計直接影響整個NoC的通信效率。一般的路由器設(shè)計均采用流水線結(jié)構(gòu)[3]；文獻[4]提出了預(yù)先路由的方法來降低路由器的流水線級數(shù)；文獻[5]對虛通道（Virtual Channel，VC）分配和交換分配進行了改進，提出了并行VC分配和交換分配的策略；文獻[6，7]對快速VC分配和交換分配的方法進行了詳細的解釋。本文在上述方法[5-7]的基礎(chǔ)上，設(shè)計了一個具有快速VC分配和交換分配機制的低延時的片上網(wǎng)絡(luò)路由器。在相同網(wǎng)絡(luò)負載情況下，本文所設(shè)計的路由器能夠極大降低片上網(wǎng)絡(luò)的通信延遲，提高片上網(wǎng)絡(luò)的通信效率。

1 相關(guān)研究

近年來，片上網(wǎng)絡(luò)路由器作為SoC的重要基礎(chǔ)部件，已經(jīng)成為學(xué)術(shù)界研究的熱點問題之一。大量文獻中提出了各種片上路由器的實現(xiàn)機制，如文獻[3]中提出了四級流水線結(jié)構(gòu)的路由器：第一級流水線完成路由功能；第二級流水線完成虛通道（Virtual Channel，VC）分配功能；第三級流水線完成交換分配功能；第四級流水線完成數(shù)據(jù)包的物理鏈路傳送功能。文獻[4]中提出了一種兩級流水線結(jié)構(gòu)的路由器：第一級流水線進行預(yù)先路由和預(yù)測分配，預(yù)先選擇一條最優(yōu)的物理鏈路；第二級流水線進行數(shù)據(jù)包物理鏈路的傳送。同時，該路由器中的路由算法采用自適應(yīng)路由算法。文獻[7]中提出了一種無流水線結(jié)構(gòu)的路由器，該路由器采用預(yù)先路由，預(yù)測分配，快速分配，全響應(yīng)，沖突檢測等機制，使得該路由器能夠在單時鐘周期內(nèi)完成數(shù)據(jù)包的轉(zhuǎn)發(fā)功能。

文獻[7]中指出資源預(yù)分配而產(chǎn)生的沖突情況只會出現(xiàn)在網(wǎng)絡(luò)負載很輕的情況下，對于網(wǎng)絡(luò)負載較重的情況下，全響應(yīng)和沖突檢測的功能則被閑置。因此，在文獻[7]的基礎(chǔ)上，本文提出的片上路由器去除了全響應(yīng)和沖突檢測的機制，對關(guān)鍵路徑和設(shè)計模塊進行了優(yōu)化，提高片上路由器的工作頻率，滿足技術(shù)指標要求。

2 低延時路由器的設(shè)計

文中設(shè)計的低延遲路由器是單周期的路由器，總體結(jié)構(gòu)如圖1所示。路由器主要包括輸入模塊、虛通道（Virtual Channel，VC）分配模塊、交換分配模塊，交叉開關(guān)和輸出模塊。其中輸入模塊包含4個虛通道，每個虛通道由4個40位的數(shù)據(jù)片深度的FIFO構(gòu)成；虛通道分配模塊采用快速分配機制實現(xiàn)；交換分配模塊采用快速交換分配機制；交叉開關(guān)和輸出模塊采用crossbar構(gòu)成。為了降低數(shù)據(jù)轉(zhuǎn)發(fā)的延時，在輸入模塊中采用了提前路由策略，VC分配和交換分配采用了并行機制和快速響應(yīng)機制。路由器在單個時鐘周期內(nèi)完成整個路由轉(zhuǎn)發(fā)過程，大大降低了數(shù)據(jù)轉(zhuǎn)發(fā)的延遲，提高了網(wǎng)絡(luò)性能。

圖1 低延時路由器結(jié)構(gòu)框圖Fig.1 Implementation architecture of low latency router

2.1預(yù)先路由機制

路由的功能是根據(jù)本級路由器網(wǎng)絡(luò)地址及目標網(wǎng)絡(luò)地址，利用路由算法計算出本級應(yīng)該輸出的端口號。從流水線結(jié)構(gòu)路由器[3-4]中我們可以看出，路由算法占用一級流水，只有完成了路由的功能后才能夠進行后續(xù)的VC分配、交換分配以及物理鏈路傳送。所以，降低流水線級數(shù)應(yīng)該從路由算法開始。在本文的設(shè)計中，目標網(wǎng)絡(luò)地址信息可以從數(shù)據(jù)中獲得（與具體包格式有關(guān)），根據(jù)一定的編碼規(guī)則，可以通過上一級路由器來完成本級的路由計算。這樣，在本級所需要的路由信息在上一級路由器中可預(yù)先得到，并將路由計算結(jié)果隨著數(shù)據(jù)一起下發(fā)到本級路由器。通過提前路由，可以減少路由器一級流水線，從而降低網(wǎng)絡(luò)延遲。

2.2 VC分配和交換分配并行工作機制

在虛通道路由器的設(shè)計中，必須獲得了下一級虛通道資源時才能進行交換分配。即交換分配等待VC分配的結(jié)果。VC分配是利用下一級路由器中虛通道的可用資源作為分配依據(jù)；交換分配是利用輸出端口號來控制交換開關(guān)為交換請求分配輸出帶寬，VC分配和交換分配的計算并沒有直接的關(guān)系，所以文獻[5]提出了一種將VC分配和交換分配并行執(zhí)行的算法，即假設(shè)VC是在已經(jīng)分配好的情況下，對交換請求進行分配。

在并行執(zhí)行的過程中，為了避免交換分配器在存在已經(jīng)分配好VC的請求的情況下對等待VC分配的請求進行響應(yīng)，文中將交換請求標記為2種請求：1）已經(jīng)分配好VC號的請求；2）等待VC分配的請求。交換分配器只有在沒有1）的情況下，才會對2）進行響應(yīng)。而對于2）是否最終分配好VC號，則在數(shù)據(jù)進入交叉開關(guān)時進行檢查。這樣就可以將流水級數(shù)降低一級，從而進一步降低網(wǎng)絡(luò)延遲。

2.3 VC分配和交換分配快速工作機制

雖然VC分配和交換分配已經(jīng)并行執(zhí)行，但是其仍然要占用一級流水，為了將整個路由器的流水級數(shù)降為一級即無流水線工作方式，必須將VC分配，交換分配及物理鏈路傳送并為一級。文獻[7]提出了一種快速VC分配和交換分配的工作機制，通過利用緩存在輸入虛通道中數(shù)據(jù)片的信息，提前仲裁出下一個時鐘周期對VC和物理鏈路資源的分配結(jié)果并暫存，當下一個時鐘周期到來時，將緩存的分配結(jié)果和當前的請求信號進行相應(yīng)的組合邏輯操作，快速的產(chǎn)生輸入端口和物理鏈路所需的控制信息。

2.4 VC分配和交換分配內(nèi)部模塊說明

2.4.1 快速響應(yīng)模塊

VC分配模塊的快速響應(yīng)單元主要是利用當前VC請求和上一個時鐘周期緩存的分配結(jié)果進行相應(yīng)的組合邏輯操作，產(chǎn)生當前請求的響應(yīng)信號，以及分配好的VC號。其工作過程為：當前請求信號到達VC分配模塊后，與上一個時鐘周期緩存的預(yù)先分配使能信號進行對應(yīng)位（如虛通道1的請求信號對應(yīng)于各個時能信號的最低位）的“與”邏輯操作，然后對各個操作結(jié)果，進行對應(yīng)位（如所有操作結(jié)果的最低位）的“或”邏輯操作，操作的結(jié)果即為所要產(chǎn)生的響應(yīng)信號。根據(jù)所請求的輸出端口號，通過“多路選擇電路”產(chǎn)生分配好的VC號。具體實現(xiàn)結(jié)構(gòu)，詳見圖2。

圖2 VC分配快速響應(yīng)模塊Fig.2 VC allocation fast response unit

交換分配模塊的快速響應(yīng)單元主要是利用當前交換請求和上一個時鐘周期緩存的分配結(jié)果進行相應(yīng)的組合邏輯操作，產(chǎn)生分配好的兩級控制信息：第一級控制信號，用于產(chǎn)生從輸入端口中請求輸出的四個虛通道之間的仲裁信息；第二級控制信號，用于產(chǎn)生端口與端口之間的對于請求同一個輸出端口的仲裁信息。需特別注意，對于某一個輸出端口，兩級控制信號應(yīng)該能夠同時得到響應(yīng)。其工作過程為：當請求信號到達交換分配模塊后，與上一個時鐘周期緩存的第一級預(yù)先分配使能信號進行對應(yīng)位（如輸入端口1中虛通道1，2，3，4的請求信號對應(yīng)于輸入端口1的預(yù)先分配使能信號）的“與”邏輯操作，利用操作的結(jié)果，通過“多路選擇電路”，選擇出第一級允許輸出虛通道所請求的端口，利用該端口號和第二級預(yù)先分配使能信號進行對應(yīng)位的“與”邏輯操作，從而產(chǎn)生第二級控制信號。利用第二級控制信號和第一級“與”的操作結(jié)果，產(chǎn)生第一級控制信號。從而保證兩級控制信號應(yīng)該能夠同時得到響應(yīng)的要求。具體實現(xiàn)結(jié)構(gòu)，詳見圖3。

圖3 交換分配快速響應(yīng)模塊Fig.3 Switch allocation fast response unit

2.4.2 下一個時鐘周期請求計算模塊

此模塊的主要功能是精確地計算下一個時鐘周期所需要的請求信號（VC請求和交換請求），以便于預(yù)先分配器模塊能夠?qū)τ嬎愠鰜淼恼埱笮盘栠M行仲裁。

對于VC請求而言，我們利用當前請求信號，請求響應(yīng)信號、下一個被緩存數(shù)據(jù)片是否頭片信息和輸出端口信息，精確的計算出下一個時鐘周期是否會有VC請求信號，電路的實現(xiàn)結(jié)構(gòu)詳見圖4。而對于交換請求信號，出于對時鐘頻率和設(shè)計復(fù)雜度的考慮，只是利用目標VC空/滿狀態(tài)來進行計算，電路的實現(xiàn)結(jié)構(gòu)詳見圖5。

圖4 計算下一節(jié)拍VC請求電路Fig.4 Computing next cycle’s VC request circuit

圖5 計算下一節(jié)拍交換請求電路Fig.5 Computing next cycle’s switch request circuit

2.4.3 預(yù)先分配器模塊

預(yù)先分配器模塊主要由一組仲裁器構(gòu)成，其能夠在多個請求之間進行裁決，將目標資源分配給一個確定的請求，仲裁的原則我們采用輪循的方式。

2.5 時鐘頻率優(yōu)化

如圖6所示，該電路的關(guān)鍵路徑：請求信號產(chǎn)生—＞VC請求快速響應(yīng)/交換請求快速響應(yīng)—＞輸入端口選擇輸出數(shù)據(jù)片—＞輸出端口選擇輸出數(shù)據(jù)片。產(chǎn)生請求信號所需要的信息為輸出端口號和VC是否分配信號，這些信號均可以提前一個時鐘周期得到。為了提高時鐘頻率，將請求信號產(chǎn)生電路提前到上一個時鐘周期，這樣關(guān)鍵路徑更新為：VC請求快速響應(yīng)/交換請求快速響應(yīng)—＞輸入端口選擇輸出數(shù)據(jù)片—＞輸出端口選擇輸出數(shù)據(jù)片，詳見圖7。為了進一步優(yōu)化時序，減少不必要的譯碼電路，關(guān)鍵路徑上的信號均采用獨熱碼譯碼。由于減少了產(chǎn)生請求信號和電路進行譯碼所需耗費的時間，電路的時鐘頻率得到顯著提高。

圖6 關(guān)鍵路徑Fig.6 Key path

圖7 更新后的關(guān)鍵路徑Fig.7 Improved key path

3 ASIC實現(xiàn)與測試

本文設(shè)計的低延時路由器芯片采用SMIC 0.13um Mixedsignal/RF 1.2V/3.3V工藝進行流片，其中核心邏輯采用基于標準單元的方法。由于SMIC的IO PAD最高支持27 MHz的時鐘[8]，故在芯片內(nèi)部設(shè)計了一個中心頻率260 MHZ，最高頻率320 MHz的環(huán)振。因此整個芯片屬于數(shù)?；旌显O(shè)計，芯片布局圖如圖8所示。

圖8 路由器芯片布局圖Fig.8 Layout of router chip

為了測試芯片功能的正確性，增加了必要的外圍電路：流量產(chǎn)生器和數(shù)據(jù)包收集器。在300 MHz的工作頻率下，采用軟件控制寄存器配置，通過ARM LPC2214芯片產(chǎn)生讀寫配置寄存器時序，經(jīng)串口發(fā)送給PC機，完成芯片性能的測試。測試結(jié)果如圖9顯示：當吞吐量較低時，數(shù)據(jù)包長度對于網(wǎng)絡(luò)的平均延遲影響較小；當吞吐量較高時，數(shù)據(jù)包的片數(shù)決定了網(wǎng)絡(luò)的平均延遲。數(shù)據(jù)包片數(shù)較少時，隨著吞吐量的增加，網(wǎng)絡(luò)平均延遲變化不大；當數(shù)據(jù)包的片數(shù)增加到一定程度，數(shù)據(jù)包網(wǎng)絡(luò)平均延遲隨著吞吐量的增加而急劇增加。

圖9 芯片測試結(jié)果Fig.9 Test result of chip

4 結(jié)束語

與流水線結(jié)構(gòu)的片上路由器相比，本文提出的路由器結(jié)構(gòu)在一個時鐘周期內(nèi)完成數(shù)據(jù)片的傳送，降低了網(wǎng)絡(luò)延遲；同時，通過對關(guān)鍵路徑的優(yōu)化，時鐘頻率得到顯著提高。與文獻[7]中所提出的低延遲路由器相比較，考慮文獻[7]中所提到的由于資源預(yù)分配而產(chǎn)生的沖突情況只會出現(xiàn)在網(wǎng)絡(luò)負載很輕的情況下，對于網(wǎng)絡(luò)負載較重的情況下，全響應(yīng)和沖突檢測的功能則被閑置，根據(jù)這樣的情況，本文通過對電路的結(jié)構(gòu)進行優(yōu)化，去掉了文獻[7]中的全響應(yīng)和沖突檢測的模塊，這樣不僅減小了電路規(guī)模，同時降低了電路實現(xiàn)的復(fù)雜度，但是其網(wǎng)絡(luò)性能卻沒有降低。同時，通過對電路關(guān)鍵路徑和部分內(nèi)部模塊（快速分配模塊，仲裁器等）的優(yōu)化設(shè)計，使得本文所設(shè)計的低延遲路由器，在所有輸入端口在相同負載的情況下，可以穩(wěn)定工作在300 MHz；在只有一個端口接收數(shù)據(jù)的情況下，時鐘頻率可以達到355 MHz。

[1]Salminen E，Kulmala A，Inen TDHML.Survey of Networkon-chip Proposals[C]//White Paper，OCP－IP，MARCH，2008.

[2]Brackenbury L E M，Plana L A.Jeffrey Pepper.System-on-Chip and Implementation[J].IEEE Transactions on Education，2010，53（2）：272－281.

[3]Kumar，A.A 4.6 Tbits/s 3.6 GHz single-cycle NoC router with a novel switch allocator in 65nm CMOS[C]//Computer Design，2007：63－70.

[4]Kim J，Park D，T.Theocharides et al.A low latency router supporting adaptivity for on-chip interconnects[C]//The 42nd annual Design Automation Conference，2005：559－564.

[5]Peh L S，Dally W J.A delay model and speculative architecture for pipelined routers [C]//In International Symposiumon High-Performance Computer Architecture，Jan 2001：255－266.

[6]Mullins，R.，West A，Moore S.Low-latency virtual-channel routers for on-chip networks[C]//The 31st annual international symposium on Computer Architecture，2004：188－197.

[7]Mullins，West R A，Moore S.The design and implementation of a low-latency on-chip network [C]//ASP-DAC ’06 Proceeding of the 2006 Asia and South Pacific Design Automation Conference，2006：164－169.

[8]VeriSilicon SMIC 0.13m 1.2V/3.3V I/O Cell Library Databook[S].Semiconductor Manufacturing International Corporation，2006.