一種低延時片上網絡路由器的設計與實現

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

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

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

1 相關研究

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

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

2 低延時路由器的設計

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

圖1 低延時路由器結構框圖Fig.1 Implementation architecture of low latency router

2.1預先路由機制

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

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

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

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

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

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

2.4 VC分配和交換分配內部模塊說明

2.4.1 快速響應模塊

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

圖2 VC分配快速響應模塊Fig.2 VC allocation fast response unit

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

圖3 交換分配快速響應模塊Fig.3 Switch allocation fast response unit

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

此模塊的主要功能是精確地計算下一個時鐘周期所需要的請求信號（VC請求和交換請求），以便于預先分配器模塊能夠對計算出來的請求信號進行仲裁。

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

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

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

2.4.3 預先分配器模塊

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

2.5 時鐘頻率優化

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

圖6 關鍵路徑Fig.6 Key path

圖7 更新后的關鍵路徑Fig.7 Improved key path

3 ASIC實現與測試

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

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

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

圖9 芯片測試結果Fig.9 Test result of chip

4 結束語

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