摘 要: 重點(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)品盡快地推向市場的時(shí)間要求,。因此人們提議采用片上網(wǎng)絡(luò)NoC(Network-on-Chip)來解決系統(tǒng)互連的可伸縮性問題[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)訪存,、中斷,，還包括視頻、語音,、實(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ǎng)中,，基于分組的通信代替了電路交換以增加通信的可靠性,。NoC采用了因特網(wǎng)基于分組通信的思想，但是弱化了可靠通信的優(yōu)點(diǎn),，因?yàn)樵贜oC中沒有實(shí)現(xiàn)動(dòng)態(tài)路由,。當(dāng)前，人們?cè)谘芯縉oC時(shí)都假定NoC是穩(wěn)定的,，不會(huì)發(fā)生鏈路" title="鏈路">鏈路或路由器失敗,，但是隨著單顆芯片集成的晶體管數(shù)量和工作頻率的增加以及特征尺寸減少和工作電壓降低，使深亞微米問題日益嚴(yán)重,，鏈路或路由器失敗問題不可忽視,。目前NoC普遍采用靜態(tài)XY路由策略[6]，它實(shí)現(xià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á)該目的地址的鏈路信息,，并能將該信息送往所有鄰居路由器,。距離向量路由僅使用目的地址和鄰居路由器信息，是一種簡單路由機(jī)制,。但是距離向量路由可能導(dǎo)致無限計(jì)數(shù)問題,，若分組在鏈路失敗，則可能導(dǎo)致在兩個(gè)結(jié)點(diǎn)無限循環(huá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)境中,，可通過實(shí)現(xiàn)靜態(tài)路由表來簡化鏈路狀態(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é)議簡化模型描述如下：（1）每次上電時(shí)進(jìn)行網(wǎng)絡(luò)配置,。網(wǎng)絡(luò)拓?fù)?、結(jié)點(diǎn)之間的距離及數(shù)目可提前預(yù)知，每個(gè)鄰居的通信代價(jià)可在上電時(shí)通過計(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路由器功能簡單,，不具有路由表的建立和管理功能，需由與NoC路由器鄰近的CPU核完成,。而目前所提議的NoC結(jié)構(gòu)中路由器與IP核有一一對(duì)應(yīng)關(guān)系,，路由器與IP核通過惟一接口互連，但與路由器相連的IP核不一定具有計(jì)算功能(如存儲(chǔ)器核),；為減少互連代價(jià),，一臺(tái)NoC路由器可與鄰近的多個(gè)IP核相連；為提高可伸縮性和可靠性,， IP核可以通過多個(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)的分布式路由管理框架來解決這些問題,。
??? 互連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)通過自適應(yīng)路由可提高NoC的可靠性與健壯性,。(3)通過多到多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è)，為簡化圖示,，僅畫出1個(gè)。
?
??? NoC支持四類QoS服務(wù),，每類分組都設(shè)置專門的虛鏈路緩沖器(VCB),；輸入端口控制器由分類部件和VCB構(gòu)成，分類部件識(shí)別每一分組所屬的類(該過程稱為分類),，將分組放入相應(yīng)的VCB中,；路由管理單元根據(jù)分組頭目的地址查找路由轉(zhuǎn)發(fā)表確定分組輸出端口(該過程稱為路由查找，分類與路由查找可由一組硬件機(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ā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)路由方法。分布式路由管理框架下的高速路由查找算法將是下一步的重要研究內(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.