面向片上網絡通信的可重構路由算法

面向片上網絡通信的可重構路由算法

劉堅強
(咸寧職業技術學院，湖北咸寧437100)

上互連網絡(Network orl Chip，NoC)采用包交換和路由的方法替代傳統總線，沒有全局的連線，具有很好的可擴展性，是未來多核處理器內核間的主要通信方式.NoC在片上系統中的應用有很多研究，片上系統在通信模式和網絡負載分配等方面一般具有穩定性.在通用多核處理器中，由于受核間通信模式不確定性、系統的可重構性等諸多因素影響，NoC的研究和設計更具復雜性和挑戰性.本文重點分析面向NoC通信的可重構路由算法.

NoC;路由算法;網絡協議;QoS

在片上網絡中，由于通信資源共享帶來的競爭，需要對關鍵部件的網絡帶寬或者延遲進行保證.另外，在深亞微米工藝下，串擾和壓降等問題使得部件之間的連線是不可靠的，可能會造成數據傳輸的錯誤或丟失.因此，通信服務質量(QoS)是分組交換的片上通信網絡中一個重要問題.服務質量是指需求的吞吐量和保證核之間的端到端的通信延遲.為保證服務質量，需要將NoC中的鏈接專用化.鏈接專用化是指根據期望的通信量調整鏈接的帶寬，帶寬通過線的數目或數據頻率調整.雖然在并行計算機中對互連網絡已經有了很多研究，有許多可以借鑒的概念和技術，但是

NoC與片外網絡在線寬、延遲、可靠性、結點計算能力和功耗等方面存在著一些重要的區別.設計專用的NoC要求以最小成本提供需求的通信性能QoS.成本包括面積和功耗兩方面.在面積方面，鏈接、緩沖器和路由被裁減;在功耗方面，使用最短的路徑路由［1］.

1 片上網絡通信的網絡協議

片上網絡的通信協議也采用層次化設計，協議的每一層為它的上一層提供相應的接口.從下到上分別為:物理層、數據鏈路層、網絡層、傳輸層、系統層和應用層.

NoC借鑒了開放系統互連(Open System Interconnection，OSI)參考模型中的分層思想，通常包含5個層次.

(1)物理層.主要解決通信通道的物理實現問題，包括互連結構、電氣性能等.

(2)數據鏈路層.通過數據分包技術解決物理層信號不可靠的問題.

(3)網絡層.主要研究數據包如何在網絡中傳輸，包括路由算法.交換算法決定建立連接類型，而路由算法則決定數據傳輸的路徑.發送節點根據接收節點的目的地址發送數據包.［2］

(4)傳輸層.主要研究在發送方如何將數據分解并建立數據包以及在接受方如何從數據包中獲得數據信息.

(5)系統層.系統軟件負責提供一個抽象的物理平臺.簡單地講，NoC系統是由網絡結點按照一定的拓撲結構連接成的網絡，NoC體系結構設計包括拓撲結構、路由和資源網絡接口的設計為基礎的許多方面.a.網絡拓撲.即片上網絡結點和連接網絡結點的鏈路的布局和連接方法，增加結點度，縮短網絡直徑，降低結點間通信的跳數，是目前拓撲結構研究的熱點.b.路由策略.用來決定通過什么樣的路線將消息從源結點送到目的結點.源結點和目的結點之間的線路可以是確定的，也可以是自適應的.好的路由算法能夠保證消息的傳輸延遲盡可能地小，同時在網絡中各部分的負載盡量平衡.c.資源網絡接口.用來連接片上資源與網絡結點，負責數據在片上資源與網絡結點之間的數據傳遞，是片上系統的重要組成部分.網絡接口的設計應該盡量簡單和通用.

(6)應用層.主要是應用軟件.片上網絡的應用層用于處理應用程序的通信、數據傳輸、消息傳輸和同步機制.在進行應用層的設計時，要考慮片上網絡的具體應用需求，針對不同應用的特點進行設計.此外，片上網絡沒有專用的協處理機來對協議進行處理，協議必須由硬件來實現，這就要求片上網絡的協議不能太復雜［3］.

在片上網絡中，通信協議比總線協議要復雜得多，為了便于擴展，同計算機網絡一樣，NoC也采取了分層協議的設計思想(如下圖1所示)，協議的每一層提供特定的功能和接口.

圖1 片上網絡通信協議

樹結構在片上互連中也有應用，其布局比較復雜，擴展性較差，樹的不同分支之間的通信延遲比較大，它的主要優勢是片上通信具有較好的局部性.不規則的網絡拓撲結構主要是在一個網絡中混合使用不同形式的拓撲結構［4］.如改變原來的規則拓撲結構的鏈路，或者是將若干不同的規則拓撲結構鏈路連接起來實現的，或者是在網絡的不同層次使用不同的拓撲結構等.由于應用程序對網絡的需求存在不對稱性，實際的網絡拓撲結構會是一種不規則的結構.考慮到深亞微米下芯片中存在的不確定性，會有一些部件出現損壞，即使規則的網絡拓撲，也會因為一些結點的損壞而破壞網絡的規整性.研究不規則網絡拓撲結構具有很重要的意義.

2 蟲孔路由問題

NoC設計的一個重要問題之一是決定路由類型，這對網絡的性能和功耗有重要影響.路由策略越復雜，設計面積越大，因此需要在面積和性能之間進行折衷.實現的復雜性和性能需求是選擇路由策略要考慮的兩大問題.自適應路由、確定性路由需要的資源少，同時確保有序的分組到達，另外，自適應路由根據網絡擁塞而改變路徑，從而可提供更好的吞吐量和低延遲.然而無序的消息到達在自適應算法中是個難題.另外，避免死鎖和活鎖對NoC也是個關鍵，因為死鎖(活鎖)探測和恢復機制代價大且會導致不可預測的延遲［5］.確定性和部分自適應算法可以避免死鎖和活鎖操作，但完全自適應策略要求額外的預防.

如果考慮的應用生成的通信是可預測的，確定性路由更合適，因為那樣的話，應用依賴，路由算法可被定制(Cmstomized)，如通過路由表分配、通信劃分等以匹配應用通信模式，另外，還有對隨機路由在NoC中的研究.(1)死鎖.因為wormhole交換對片上網絡實現有很多優點，這里主要討論wormhole中的死鎖和活鎖問題.(2)活鎖.活鎖是許多自適應路由方案中潛伏的問題.當一個分組以循環方式圍著它的目的地一直運行下去時，就產生了活鎖.

3 交換技術與路由算法

電路交換是一種面向連接的交換機制，在源結點和目的結點之間建立電路連接，直到數據傳輸完成.AEthereal、 Nostrum和MANGO都使用了電路交換.由于具有低延遲和低存儲需求的特點，基于蟲孔尋徑的包交換是目前片上互連網絡所采用的主要交換方式.在確定性路由算法中，包的傳送路徑是由源結點和目的結點決定的，可分為源路由算法和X－Y維序路由算法.在自適應路由算法中，使用從其他結點收集來的有關網絡流量的信息來計算路由.路由算法的選擇應該考慮應用程序的通信特性.根據應用程序的通信特征設計合適的路由算法，可以從總體上降低網絡傳輸的平均延遲，提高系統的性能.自適應路由和確定性路由都有其適用范圍.當網絡中某結點損壞或關閉時，會破壞網絡的規整性，確定性路由往往無法完成其他結點間的通信.這就需要研究混合的動態路由算法.

4 片上網絡的典型路由算法

通信網絡中的數據流通信來自處理器之間和處理器與存儲器之間的事務.片上通信的性能和功耗不僅與網絡的物理特征(電壓擺動、線延遲和輸出負載電容等)有關，還依賴于處理器節點之間的交互.

分組(Packet)，也稱為包，是NoC中消息的傳輸形式.MPSoC網絡支持的分組傳輸由頭部、有效負荷(Payload)和尾部三個部分組成.一個分組的頭部包括目的地址、源地址和請求的操作類型(Read，Write，Invalidate等).有效負荷包含傳輸的數據.尾部包括檢錯和糾錯碼.片上網絡的分組有不同的來源，它們可分為以下類型［6］:

(1)存儲器訪問請求分組.分組頭包括目標存儲器(節點ID和存儲器地址)的目的地址和存儲器操作的類型(如存儲器讀)，因為沒有數據傳輸，有效負荷為空.

(2)Cache一致同步分組.由來自存儲器的Cache一致操作引起.這種類型的包來自被更新的存儲器，被發送到所有具有被更新數據副本的Caches中.分組頭包含存儲器標志和數據的模塊地址.如果同步使用更新的方法，包的有效負載是更新數據.如果同步使用“Invalidate”方法，分組頭包括操作類型(Invalidate)，有效負載為空.

(3)取數據分組.是來自存儲器的應答分組，含有請求的數據.分組頭包括目的地址(請求數據的Cache的節點D).數據包含在分組的有效負載內.

(4)數據更新分組.分組包括將被寫到存儲器的數據.這個數據來自要求進行存儲器寫操作的L2 Cache.分組頭包括目的存儲器地址，有效負載中含有數據.

(5)I/0和中斷分組.供I/0操作或中斷操作使用.分組頭包含目的地址或節點D.如果涉及數據交換，有效負載中就含有數據.

除I/O和中斷操作，大多數分組在存儲器和Cache之間傳輸.不同的分組來自不同的源，但是分組的長度由有效負載的大小決定.實際上，MPSoC網絡中有兩種不同大小的分組:短分組和長分組.短分組是沒有有效負載的分組，如存儲器訪問請求分組和Cache一致分組(使用Invalidate方法)，這些分組只有頭和尾組成，有兩個Flits長度.長分組是含有有效負載的分組，如取數據分組、數據更新分組和Cache一致分組(使用更新方法).有效負載中包含的數據或來自Cache模塊，或發送回節點Cache來更新Cache模塊.

在片上網絡的路由中，每個輸入端口的緩沖區的大小對路由所占的面積有較大的影響，增加緩沖區的大小會使路由的面積急劇增加.與此同時，增加緩沖區會極大地改善整個片上網絡的性能，不過由于片上網絡各部分之間傳輸的不均衡，可能在整個片上網絡中，增加的緩沖區起作用的只是一個較小的范圍.有的研究給出了通過確定網絡中負載最重的通道并為其分配較大緩沖區的方法.在片上互連網絡的設計中，應該選擇合適的網絡鏈路通道寬度，從而達到如下目的:在符合面積、線長和功耗的限制下，使網絡消息傳遞的延遲最小化或者使整個網絡的吞吐量最大化.由于在確定鏈路的寬度時，會同時影響到連線的尺寸及間距，從而會影響到網絡的頻率，所以不能簡單地只單獨考慮頻率和通道寬度中的某一方面.網絡接口是計算資源與通信網絡間的接口，它主要考慮地址信號、數據的打包、解包、編碼和同步等問題.通過網絡接口，計算資源與網絡通信實現分離，允許計算資源和通信結構分別設計.網絡接口的設計需要與現存的總線協議兼容，如OCP、AXI協議.在片上網絡中，由于通信資源共享帶來的競爭，需要對關鍵部件的網絡帶寬或者延遲進行保證.因此，通信服務質量(QoS)是分組交換的片上通信網絡中一個重要問題.

設計NoC是MPSoC的主要任務之一.系統的一大部分延遲花在互連上的信號傳播上，一大部分的能量消耗在連線的負載電容的充放電上.因此，優化互連網絡版圖對MPSoC性能和功耗都非常重要.片上互連網絡(Networkon-Chip，NoC)采用包交換和路由的方法替代傳統總線，沒有全局的連線，具有很好的可擴展性，是未來多核處理器內核間的主要通信方式.雖然在并行計算機中對互連網絡已經有了很多研究，有許多可以借鑒的概念和技術，但是NoC與片外網絡在線寬、延遲、可靠性、結點計算能力和功耗等方面存在著一些重要的區別.NoC在片上系統中的應用有很多研究，片上系統在通信模式和網絡負載分配等方面一般具有穩定性，可以針對應用的特點對片上網絡進行設計和優化.在通用多核處理器中，由于受核間通信模式不確定性、系統的可重構性等諸多因素影響，NoC的研究和設計更具復雜性和挑戰性.庫中元件的高度參數化是通過使用全局專用網絡參數和局部專用模塊參數實現的.全局專用網絡參數包括Flit大小、差錯冗余度控制邏輯、核地址空間、兩個節點之間的最大跳數、為端到端流控制分組分配的位的最大數目等.另一方面，網絡接口的專用參數是:接口類型(主、從或主/從)、輸出端口Flit緩沖器的大小等.

5 結論

目前，片上網絡方面的研究才剛起步，未形成產品.片上通信網絡還有很多問題如專門平臺結構、片上網絡的物理布局、容錯和魯棒性傳輸、異構網絡路由算法、編程抽象、任務層分析和優化、代碼優化和分布式操作系統等需要研究.

［1］李靜梅，馮剛，王海霞，等編著.現代計算機體系結構［M］.北京:清華大學出版社，2009.

［2］馬光勝，馮剛編.SOC設計與IP核重用技術［M］.北京:國防工業出版社，2006.

［3］潘中良.系統芯片SOC的設計與測試［M］.北京:科學出版社，2009.

［4］孫光，張媛媛.基于虛擬化片上網絡的二級優先維序路由算法［J］.清華大學學報(自然科學版)，2011，(3): 77～78.

［5］付斌章，韓銀和.面向高可靠片上網絡通信的可重構路由算法［J］.計算機輔助設計與圖形學學報，2011，(3):152～153.

［6］張磊，李華偉，李曉維.用于片上網絡的容錯通信算法［J］.計算機輔助設計與圖形學學報，2007，19(4):508～514.

TN47

A

1006－5342(2012)06－0041－03

2012－02－15