摘 要: 重點(diǎn)分析了RIP和OSPF協(xié)議在大型NoC中的適用性，在此基礎(chǔ)上提出了一種分布式路由管理框架，它能有效地實(shí)現(xiàn)大型NoC動(dòng)態(tài)路由" title="動(dòng)態(tài)路由">動(dòng)態(tài)路由方法。
關(guān)鍵詞:動(dòng)態(tài)路由管理? NoC? 分布式
?
??? 據(jù)有關(guān)資料介紹，到2010年，單顆芯片集成的晶體管數(shù)量將達(dá)到10億、工作頻率將達(dá)到10GHz、特征尺寸將小于100nm(當(dāng)特征尺寸為35nm時(shí)，集成在一顆芯片內(nèi)的IP核可以達(dá)到1000以上)、工作電壓將小于1V[1]。因系統(tǒng)互連的可伸縮性受限于當(dāng)前SoC所采用的基于總線的共享通信資源，而NoC可伸縮性好、能兼容已有IP核的設(shè)計(jì)和重用性、能滿足SoC設(shè)計(jì)者將產(chǎn)品盡快地推向市場(chǎng)的時(shí)間要求。因此人們提議采用片上網(wǎng)絡(luò)NoC(Network-on-Chip)來(lái)解決系統(tǒng)互連的可伸縮性問(wèn)題[2-6]。 ?NoC的概念源于計(jì)算機(jī)網(wǎng)絡(luò)[7]。OSI參考模型[8]將計(jì)算機(jī)網(wǎng)絡(luò)分成七層以減少設(shè)計(jì)復(fù)雜性，每層向上層提供特定的服務(wù)，并屏蔽本層的實(shí)現(xiàn)細(xì)節(jié)，只有同層的實(shí)體才能通信和交換數(shù)據(jù)。為便于研究和設(shè)計(jì)實(shí)現(xiàn)，NoC的通信復(fù)雜性也可以由OSI參考模型進(jìn)行描述。與計(jì)算機(jī)網(wǎng)絡(luò)相比，用于NoC的硅面積和功耗受到嚴(yán)格限制。
??? NoC面向的應(yīng)用不僅包括計(jì)算機(jī)系統(tǒng)內(nèi)訪存、中斷，還包括視頻、語(yǔ)音、實(shí)時(shí)控制信號(hào)傳送等應(yīng)用，因此，NoC必須提供可靠的高性能服務(wù)。要提供可靠服務(wù)及可伸縮性，NoC必須實(shí)現(xiàn)動(dòng)態(tài)路由，為此，需要采用分布式路由管理策略。
??? RIP[9]和OSPF[10]是因特網(wǎng)普遍使用的動(dòng)態(tài)路由協(xié)議" title="路由協(xié)議">路由協(xié)議，本文著重分析了RIP和OSPF協(xié)議在NoC中的適用性，并在此基礎(chǔ)上提出一種分布式路由管理框架，它能有效地實(shí)現(xiàn)NoC動(dòng)態(tài)路由方法。
1 NoC的路由問(wèn)題
??? 在英特網(wǎng)中，基于分組的通信代替了電路交換以增加通信的可靠性。NoC采用了因特網(wǎng)基于分組通信的思想，但是弱化了可靠通信的優(yōu)點(diǎn)，因?yàn)樵贜oC中沒(méi)有實(shí)現(xiàn)動(dòng)態(tài)路由。當(dāng)前，人們?cè)谘芯縉oC時(shí)都假定NoC是穩(wěn)定的，不會(huì)發(fā)生鏈路" title="鏈路">鏈路或路由器失敗，但是隨著單顆芯片集成的晶體管數(shù)量和工作頻率的增加以及特征尺寸減少和工作電壓降低，使深亞微米問(wèn)題日益嚴(yán)重，鏈路或路由器失敗問(wèn)題不可忽視。目前NoC普遍采用靜態(tài)XY路由策略[6]，它實(shí)現(xiàn)簡(jiǎn)單，但是不能處理鏈路或路由器失敗等問(wèn)題，而動(dòng)態(tài)路由在路徑發(fā)生變化時(shí)可以動(dòng)態(tài)選擇新的路由，因此NoC實(shí)現(xiàn)動(dòng)態(tài)路由是必然選擇。
下面分析英特網(wǎng)普遍使用的動(dòng)態(tài)路由協(xié)議RIP和OSPF在NoC中的適用性。
1.1 RIP
??? RIP協(xié)議使用距離向量路由，每臺(tái)路由器維持一張路由表" title="路由表">路由表，存放可用的目的地址和能到達(dá)該目的地址的鏈路信息，并能將該信息送往所有鄰居路由器。距離向量路由僅使用目的地址和鄰居路由器信息，是一種簡(jiǎn)單路由機(jī)制。但是距離向量路由可能導(dǎo)致無(wú)限計(jì)數(shù)問(wèn)題，若分組在鏈路失敗，則可能導(dǎo)致在兩個(gè)結(jié)點(diǎn)無(wú)限循環(huán)，該問(wèn)題的解決方法對(duì)于NoC同樣適用。例如，“split horizon with poisoned reverse”限制最大跳數(shù)，并觸發(fā)更新[9]。
1.2 OSPF
??? OSPF協(xié)議使用鏈路狀態(tài)，與RIP協(xié)議不同，它將鄰居路由器信息廣播給網(wǎng)絡(luò)上所有的路由器。該機(jī)制基于“一張分布式表”，每臺(tái)路由器均保留該表的備份，并按一定規(guī)則更新。其目標(biāo)是每臺(tái)路由器均有整個(gè)網(wǎng)絡(luò)狀態(tài)的相同視圖；鏈路狀態(tài)協(xié)議需要每臺(tái)路由器均知道一條鏈路的up/down狀態(tài)和通信代價(jià)，計(jì)算到達(dá)目的地的總代價(jià)。
??? 在NoC環(huán)境中，可通過(guò)實(shí)現(xiàn)靜態(tài)路由表來(lái)簡(jiǎn)化鏈路狀態(tài)協(xié)議的復(fù)雜性。NoC環(huán)境中不可能有新結(jié)點(diǎn)加入網(wǎng)絡(luò)，路由表不會(huì)增加，當(dāng)一條鏈路進(jìn)入down狀態(tài)時(shí)，只有相關(guān)表項(xiàng)需要從路由表中刪除，不需要對(duì)NoC拓?fù)浣Y(jié)構(gòu)" title="拓?fù)浣Y(jié)構(gòu)">拓?fù)浣Y(jié)構(gòu)進(jìn)行手工干預(yù)。因此可以對(duì)鏈路狀態(tài)協(xié)議進(jìn)行改造，使之適合于NoC。適合于NoC的鏈路狀態(tài)協(xié)議簡(jiǎn)化模型描述如下：（1）每次上電時(shí)進(jìn)行網(wǎng)絡(luò)配置。網(wǎng)絡(luò)拓?fù)?、結(jié)點(diǎn)之間的距離及數(shù)目可提前預(yù)知，每個(gè)鄰居的通信代價(jià)可在上電時(shí)通過(guò)計(jì)算得到，基于這些信息即可在每臺(tái)路由器建立和存儲(chǔ)路由表。（2）當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生明顯變化時(shí)，如鏈路進(jìn)入down狀態(tài)或路由器失去功能時(shí)，發(fā)送ECHO分組，以計(jì)算新路徑的通信代價(jià)并改變網(wǎng)絡(luò)配置，其路由表要用最新的配置信息進(jìn)行構(gòu)建，但不需要在網(wǎng)絡(luò)上頻繁發(fā)送更新信息。（3）拓?fù)浣Y(jié)構(gòu)發(fā)生改變時(shí)，使用Dijkstra最短路徑優(yōu)先算法計(jì)算最佳路徑。
2 大型NoC分布式路由管理框架
??? 通常，NoC路由器功能簡(jiǎn)單，不具有路由表的建立和管理功能，需由與NoC路由器鄰近的CPU核完成。而目前所提議的NoC結(jié)構(gòu)中路由器與IP核有一一對(duì)應(yīng)關(guān)系，路由器與IP核通過(guò)惟一接口互連，但與路由器相連的IP核不一定具有計(jì)算功能(如存儲(chǔ)器核)；為減少互連代價(jià)，一臺(tái)NoC路由器可與鄰近的多個(gè)IP核相連；為提高可伸縮性和可靠性， IP核可以通過(guò)多個(gè)網(wǎng)絡(luò)接口與鄰近的多個(gè)NoC路由器相連。一個(gè)CPU核可能完成鄰近多臺(tái)路由器路由表的建立和管理及路由轉(zhuǎn)發(fā)表的分發(fā)工作（該CPU核稱為路由主機(jī)Ghost）。但是，當(dāng)網(wǎng)絡(luò)規(guī)模變大時(shí)，使用一級(jí)編址方式路由轉(zhuǎn)發(fā)表的規(guī)模將變得龐大，占用大量存儲(chǔ)器資源和大量面積，消耗大量功耗。因此，本文提出一種適合大型NoC結(jié)構(gòu)的分布式路由管理框架來(lái)解決這些問(wèn)題。
??? 互連IP數(shù)N為1 024的一種NoC結(jié)構(gòu)如圖1所示，每個(gè)NoC路由器與鄰近的四個(gè)IP核相連，采用二維環(huán)網(wǎng)(torus)或二維網(wǎng)格(mesh) 拓?fù)浣Y(jié)構(gòu)。其優(yōu)點(diǎn)是網(wǎng)絡(luò)規(guī)模相對(duì)較小，但是可伸縮性、可靠性相對(duì)較差，因此可以作為大型NoC低成本的組網(wǎng)方法。
為提高可伸縮性和可靠性，可采用IP核同時(shí)具有多個(gè)網(wǎng)絡(luò)接口的NoC結(jié)構(gòu)，其優(yōu)點(diǎn)：(1)同一對(duì)IP核之間可并發(fā)進(jìn)行數(shù)據(jù)傳送，可伸縮性好。(2)通過(guò)自適應(yīng)路由可提高NoC的可靠性與健壯性。(3)通過(guò)多到多CSM(Core-Switch Mapping)綜合算法可降低功耗、提高吞吐率[9]。IP核同時(shí)具有四個(gè)網(wǎng)絡(luò)接口的NoC結(jié)構(gòu)如圖2所示。該結(jié)構(gòu)也可使用二維環(huán)網(wǎng)或二維網(wǎng)格拓?fù)浣Y(jié)構(gòu)，其缺點(diǎn)是網(wǎng)絡(luò)規(guī)模相對(duì)較大。
?
?
??? 由于本文介紹的網(wǎng)絡(luò)規(guī)模龐大(兩種NoC結(jié)構(gòu)路由器數(shù)量分別為256或1 024)，因此采用分布式路由管理策略及分發(fā)和轉(zhuǎn)發(fā)策略。每16(32)個(gè)路由器為一組，將本組所連的某個(gè)CPU核設(shè)為路由主機(jī)Ghost，負(fù)責(zé)本組路由策略管理與分發(fā)，組內(nèi)擬采用RIP和OSPF路由協(xié)議。全系統(tǒng)共有16(32)個(gè)Ghost，Ghost之間使用組間路由協(xié)議GRP(Group Router Protocol)進(jìn)行通信，Ghost根據(jù)鄰近Ghost的拓?fù)浣Y(jié)構(gòu)變化更新本地路由表，并將本地拓?fù)浣Y(jié)構(gòu)變化信息送往鄰近Ghost。
?
?
??? 兩種NoC結(jié)構(gòu)均使用八端口路由器，分別連接?xùn)|、西、南、北四個(gè)相鄰路由器與IP核，NoC路由器交換開關(guān)為8×8，其結(jié)構(gòu)如圖3所示。路由器由輸入端口控制器、路由管理單元、交換開關(guān)和輸出端口控制器構(gòu)成，輸入、輸出端口控制器各有8個(gè)，為簡(jiǎn)化圖示，僅畫出1個(gè)。
?
??? NoC支持四類QoS服務(wù)，每類分組都設(shè)置專門的虛鏈路緩沖器(VCB)；輸入端口控制器由分類部件和VCB構(gòu)成，分類部件識(shí)別每一分組所屬的類(該過(guò)程稱為分類)，將分組放入相應(yīng)的VCB中；路由管理單元根據(jù)分組頭目的地址查找路由轉(zhuǎn)發(fā)表確定分組輸出端口(該過(guò)程稱為路由查找，分類與路由查找可由一組硬件機(jī)制實(shí)現(xiàn))，并將相應(yīng)請(qǐng)求信號(hào)送往流控單元，對(duì)可用緩沖器計(jì)數(shù)器做減法，路由轉(zhuǎn)發(fā)表由8讀1寫存儲(chǔ)器實(shí)現(xiàn)，可供8個(gè)端口同時(shí)查找，路由轉(zhuǎn)發(fā)表的內(nèi)容由Ghost建立與更新；交換開關(guān)將輸入端口控制器交換至輸出端口控制器(該過(guò)程稱為交換)。為簡(jiǎn)化交換開關(guān)設(shè)計(jì)，使用多路復(fù)接設(shè)備將同一端口所屬的VCB進(jìn)行時(shí)分復(fù)用，發(fā)生沖突時(shí)由專門的仲裁器進(jìn)行仲裁，成功傳送分組后須送流控信號(hào)給上一級(jí)路由器流控單元，對(duì)可用緩沖器計(jì)數(shù)器做加法；輸出端口控制器由流控單元和調(diào)度器組成，流控單元實(shí)現(xiàn)鏈路流控算法，調(diào)度器則調(diào)度分組算法決定分組的服務(wù)順序，分配網(wǎng)絡(luò)資源給接受的每條連接。
??? 本文重點(diǎn)分析了因特網(wǎng)普遍使用的動(dòng)態(tài)路由協(xié)議RIP和OSPF在NoC中的適用性，并在此基礎(chǔ)上提出了一種分布式路由管理框架，該框架能有效地實(shí)現(xiàn)NoC動(dòng)態(tài)路由方法。分布式路由管理框架下的高速路由查找算法將是下一步的重要研究?jī)?nèi)容。
參考文獻(xiàn)
[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.