摘 要: 重點分析了RIP和OSPF協議在大型NoC中的適用性，在此基礎上提出了一種分布式路由管理框架，它能有效地實現大型NoC動態路由" title="動態路由">動態路由方法。
關鍵詞:動態路由管理? NoC? 分布式
?
??? 據有關資料介紹，到2010年，單顆芯片集成的晶體管數量將達到10億、工作頻率將達到10GHz、特征尺寸將小于100nm(當特征尺寸為35nm時，集成在一顆芯片內的IP核可以達到1000以上)、工作電壓將小于1V[1]。因系統互連的可伸縮性受限于當前SoC所采用的基于總線的共享通信資源，而NoC可伸縮性好、能兼容已有IP核的設計和重用性、能滿足SoC設計者將產品盡快地推向市場的時間要求。因此人們提議采用片上網絡NoC(Network-on-Chip)來解決系統互連的可伸縮性問題[2-6]。 ?NoC的概念源于計算機網絡[7]。OSI參考模型[8]將計算機網絡分成七層以減少設計復雜性，每層向上層提供特定的服務，并屏蔽本層的實現細節，只有同層的實體才能通信和交換數據。為便于研究和設計實現，NoC的通信復雜性也可以由OSI參考模型進行描述。與計算機網絡相比，用于NoC的硅面積和功耗受到嚴格限制。
??? NoC面向的應用不僅包括計算機系統內訪存、中斷，還包括視頻、語音、實時控制信號傳送等應用，因此，NoC必須提供可靠的高性能服務。要提供可靠服務及可伸縮性，NoC必須實現動態路由，為此，需要采用分布式路由管理策略。
??? RIP[9]和OSPF[10]是因特網普遍使用的動態路由協議" title="路由協議">路由協議，本文著重分析了RIP和OSPF協議在NoC中的適用性，并在此基礎上提出一種分布式路由管理框架，它能有效地實現NoC動態路由方法。
1 NoC的路由問題
??? 在英特網中，基于分組的通信代替了電路交換以增加通信的可靠性。NoC采用了因特網基于分組通信的思想，但是弱化了可靠通信的優點，因為在NoC中沒有實現動態路由。當前，人們在研究NoC時都假定NoC是穩定的，不會發生鏈路" title="鏈路">鏈路或路由器失敗，但是隨著單顆芯片集成的晶體管數量和工作頻率的增加以及特征尺寸減少和工作電壓降低，使深亞微米問題日益嚴重，鏈路或路由器失敗問題不可忽視。目前NoC普遍采用靜態XY路由策略[6]，它實現簡單，但是不能處理鏈路或路由器失敗等問題，而動態路由在路徑發生變化時可以動態選擇新的路由，因此NoC實現動態路由是必然選擇。
下面分析英特網普遍使用的動態路由協議RIP和OSPF在NoC中的適用性。
1.1 RIP
??? RIP協議使用距離向量路由，每臺路由器維持一張路由表" title="路由表">路由表，存放可用的目的地址和能到達該目的地址的鏈路信息，并能將該信息送往所有鄰居路由器。距離向量路由僅使用目的地址和鄰居路由器信息，是一種簡單路由機制。但是距離向量路由可能導致無限計數問題，若分組在鏈路失敗，則可能導致在兩個結點無限循環，該問題的解決方法對于NoC同樣適用。例如，“split horizon with poisoned reverse”限制最大跳數，并觸發更新[9]。
1.2 OSPF
??? OSPF協議使用鏈路狀態，與RIP協議不同，它將鄰居路由器信息廣播給網絡上所有的路由器。該機制基于“一張分布式表”，每臺路由器均保留該表的備份，并按一定規則更新。其目標是每臺路由器均有整個網絡狀態的相同視圖；鏈路狀態協議需要每臺路由器均知道一條鏈路的up/down狀態和通信代價，計算到達目的地的總代價。
??? 在NoC環境中，可通過實現靜態路由表來簡化鏈路狀態協議的復雜性。NoC環境中不可能有新結點加入網絡，路由表不會增加，當一條鏈路進入down狀態時，只有相關表項需要從路由表中刪除，不需要對NoC拓撲結構" title="拓撲結構">拓撲結構進行手工干預。因此可以對鏈路狀態協議進行改造，使之適合于NoC。適合于NoC的鏈路狀態協議簡化模型描述如下：（1）每次上電時進行網絡配置。網絡拓撲、結點之間的距離及數目可提前預知，每個鄰居的通信代價可在上電時通過計算得到，基于這些信息即可在每臺路由器建立和存儲路由表。（2）當網絡拓撲發生明顯變化時，如鏈路進入down狀態或路由器失去功能時，發送ECHO分組，以計算新路徑的通信代價并改變網絡配置，其路由表要用最新的配置信息進行構建，但不需要在網絡上頻繁發送更新信息。（3）拓撲結構發生改變時，使用Dijkstra最短路徑優先算法計算最佳路徑。
2 大型NoC分布式路由管理框架
??? 通常，NoC路由器功能簡單，不具有路由表的建立和管理功能，需由與NoC路由器鄰近的CPU核完成。而目前所提議的NoC結構中路由器與IP核有一一對應關系，路由器與IP核通過惟一接口互連，但與路由器相連的IP核不一定具有計算功能(如存儲器核)；為減少互連代價，一臺NoC路由器可與鄰近的多個IP核相連；為提高可伸縮性和可靠性， IP核可以通過多個網絡接口與鄰近的多個NoC路由器相連。一個CPU核可能完成鄰近多臺路由器路由表的建立和管理及路由轉發表的分發工作（該CPU核稱為路由主機Ghost）。但是，當網絡規模變大時，使用一級編址方式路由轉發表的規模將變得龐大，占用大量存儲器資源和大量面積，消耗大量功耗。因此，本文提出一種適合大型NoC結構的分布式路由管理框架來解決這些問題。
??? 互連IP數N為1 024的一種NoC結構如圖1所示，每個NoC路由器與鄰近的四個IP核相連，采用二維環網(torus)或二維網格(mesh) 拓撲結構。其優點是網絡規模相對較小，但是可伸縮性、可靠性相對較差，因此可以作為大型NoC低成本的組網方法。
為提高可伸縮性和可靠性，可采用IP核同時具有多個網絡接口的NoC結構，其優點：(1)同一對IP核之間可并發進行數據傳送，可伸縮性好。(2)通過自適應路由可提高NoC的可靠性與健壯性。(3)通過多到多CSM(Core-Switch Mapping)綜合算法可降低功耗、提高吞吐率[9]。IP核同時具有四個網絡接口的NoC結構如圖2所示。該結構也可使用二維環網或二維網格拓撲結構，其缺點是網絡規模相對較大。
?
?
??? 由于本文介紹的網絡規模龐大(兩種NoC結構路由器數量分別為256或1 024)，因此采用分布式路由管理策略及分發和轉發策略。每16(32)個路由器為一組，將本組所連的某個CPU核設為路由主機Ghost，負責本組路由策略管理與分發，組內擬采用RIP和OSPF路由協議。全系統共有16(32)個Ghost，Ghost之間使用組間路由協議GRP(Group Router Protocol)進行通信，Ghost根據鄰近Ghost的拓撲結構變化更新本地路由表，并將本地拓撲結構變化信息送往鄰近Ghost。
?
?
??? 兩種NoC結構均使用八端口路由器，分別連接東、西、南、北四個相鄰路由器與IP核，NoC路由器交換開關為8×8，其結構如圖3所示。路由器由輸入端口控制器、路由管理單元、交換開關和輸出端口控制器構成，輸入、輸出端口控制器各有8個，為簡化圖示，僅畫出1個。
?
??? NoC支持四類QoS服務，每類分組都設置專門的虛鏈路緩沖器(VCB)；輸入端口控制器由分類部件和VCB構成，分類部件識別每一分組所屬的類(該過程稱為分類)，將分組放入相應的VCB中；路由管理單元根據分組頭目的地址查找路由轉發表確定分組輸出端口(該過程稱為路由查找，分類與路由查找可由一組硬件機制實現)，并將相應請求信號送往流控單元，對可用緩沖器計數器做減法，路由轉發表由8讀1寫存儲器實現，可供8個端口同時查找，路由轉發表的內容由Ghost建立與更新；交換開關將輸入端口控制器交換至輸出端口控制器(該過程稱為交換)。為簡化交換開關設計，使用多路復接設備將同一端口所屬的VCB進行時分復用，發生沖突時由專門的仲裁器進行仲裁，成功傳送分組后須送流控信號給上一級路由器流控單元，對可用緩沖器計數器做加法；輸出端口控制器由流控單元和調度器組成，流控單元實現鏈路流控算法，調度器則調度分組算法決定分組的服務順序，分配網絡資源給接受的每條連接。
??? 本文重點分析了因特網普遍使用的動態路由協議RIP和OSPF在NoC中的適用性，并在此基礎上提出了一種分布式路由管理框架，該框架能有效地實現NoC動態路由方法。分布式路由管理框架下的高速路由查找算法將是下一步的重要研究內容。
參考文獻
[1] ?International technology roadmap for semiconductors.http://www.itrs.net,2006-02-28.
[2] ?BENINI L, MICHELI G D. Networks on chips: A New?SoC paradigm. IEEE Computers, Jan. 2002：70-78.
[3] ?JANTSCH A, TENHUNEN H. Networks on chip. Kluwer?Academic Publishers, 2003.
[4] ?RIJPKEMA E. Trade-offs in the design of a router with?both guaranteed and best-effort services for??? networks on?chip. Mar. 2003:350-355.
[5] ?KARIM F. An interconnect architecture for network systems?on Chips. IEEE Micro, 2002,22(5):36-45.
[6] ?DALLY W, TOWLES B. Route packets, not wires: on-chip interconnection networks. 38th Design Automation
?Conference(DAC' 01), June 2001:684~689.
[7] ?TANENBAUM A S. Computer networks, upper sadle river, ?New Yersey: Pearson Education, Inc., 2003.
[8] ?ZIMMERMANN H, OSI reference model - the ISO model?of architecture for open systems interconnection. IEEE
?Transactions on Communications,1980,28(4):425-432.
[9] ?HENDRICH C. Routing information protocol: RFC1058.IETF Network Working Group, June 1988.
[10]?HENDRICH C. The OSPF specification: RFC1131. IETF?Network Working Group, June 1988.