呂瑞，李洋

（長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院，長(zhǎng)春 130022）

隨著集成電路工藝技術(shù)的飛速發(fā)展，當(dāng)前系統(tǒng)級(jí)芯片需要嵌入大量處理器，這就使得基于總線結(jié)構(gòu)的SoC技術(shù)在時(shí)延、功耗、全局同步等方面遇到瓶頸。NoC作為一種新型的大規(guī)模集成電路設(shè)計(jì)方法，取代傳統(tǒng)的互連技術(shù)，能夠解決復(fù)雜的SoC所面臨的難題。

NoC通常采用交叉開(kāi)關(guān)式路由結(jié)構(gòu)，它主要由鏈路控制器、輸入輸出緩存、交叉開(kāi)關(guān)、路由和仲裁構(gòu)成。其中鏈路控制器負(fù)責(zé)控制物理通道間的數(shù)據(jù)流量；緩沖器負(fù)責(zé)存儲(chǔ)不能立刻轉(zhuǎn)發(fā)的數(shù)據(jù)；交叉開(kāi)關(guān)負(fù)責(zé)將輸入端輸入的數(shù)據(jù)傳輸?shù)揭粋€(gè)或者多個(gè)輸出端口；路由仲裁單元主要負(fù)責(zé)實(shí)現(xiàn)通信節(jié)點(diǎn)間的路由算法。路由算法作為NoC路由模塊的的關(guān)鍵技術(shù)，決定了分組發(fā)送的路徑選擇，對(duì)網(wǎng)絡(luò)吞吐量、時(shí)延、網(wǎng)絡(luò)鏈路利用率等通信性能將產(chǎn)生很大的影響［1］，同時(shí)，算法的死鎖發(fā)生率、邏輯復(fù)雜度以及硬件實(shí)現(xiàn)成本等問(wèn)題在評(píng)估和優(yōu)化路由算法的過(guò)程中也起到至關(guān)重要的作用。Ville Rantala等人將NoC的路由算法主要分為兩大類［2］：（1）確定性路由算法（Deterministic Routing），XY路由是一種無(wú)死鎖的典型確定性路由算法，該算法在網(wǎng)絡(luò)負(fù)載較輕時(shí)具有低延遲和高吞吐的性能，當(dāng)網(wǎng)絡(luò)發(fā)生故障或擁塞時(shí)，由于不能根據(jù)網(wǎng)絡(luò)狀態(tài)作出動(dòng)態(tài)的響應(yīng)，會(huì)造成網(wǎng)絡(luò)性能的下降［3］。（2）自適應(yīng)路由（Adaptive Routing）算法，Ali等人提出的NoC-LS路由算法［4］，是一種充分利用鏈路狀態(tài)且具有容錯(cuò)能力的動(dòng)態(tài)路由算法，但路由邏輯控制復(fù)雜；Daneshtalab等人基于蟻群理論提出的Ant Net路由算法［5］，能夠有效緩解網(wǎng)絡(luò)熱點(diǎn)、提高網(wǎng)絡(luò)吞吐量和鏈路利用率，同時(shí)也加大了硬件開(kāi)銷。本文提出一種確定性和自適應(yīng)性路由相結(jié)合的DARA路由算法，相對(duì)于通用的XY路由可以更好地適應(yīng)網(wǎng)絡(luò)擁塞或熱點(diǎn)的現(xiàn)象，相對(duì)于復(fù)雜的自適應(yīng)路由，實(shí)現(xiàn)成本更優(yōu)。

1 DARA算法

通過(guò)分析數(shù)據(jù)流特征及網(wǎng)絡(luò)狀態(tài)，本文提出一種結(jié)合確定性路由和自適應(yīng)路由的動(dòng)態(tài)自適應(yīng)路由算法DARA（Dynamic Adaptive Routing Algorithm）。對(duì)于通用型2D-Mesh拓?fù)浣Y(jié)構(gòu)的NoC，片上資源和存儲(chǔ)單元均勻分布在網(wǎng)絡(luò)節(jié)點(diǎn)中，當(dāng)網(wǎng)絡(luò)邊緣節(jié)點(diǎn)與中間區(qū)域節(jié)點(diǎn)之間的通信負(fù)載加重時(shí)，中間區(qū)域容易成為網(wǎng)絡(luò)的擁塞區(qū)域，成為熱點(diǎn)（hotspots）。因此，針對(duì)受資源限制的NoC，對(duì)邊緣節(jié)點(diǎn)采用確定性路由的方式，而對(duì)中間區(qū)域節(jié)點(diǎn)采用動(dòng)態(tài)的路由方式。

1.1 中間區(qū)域節(jié)點(diǎn)的路由方式

目前，NoC的路由算法通常以單個(gè)性能作為約束條件。在中間區(qū)域節(jié)點(diǎn)上，DARA的設(shè)計(jì)思想是在限制分組通過(guò)最短路徑滿足延時(shí)約束的基礎(chǔ)上的動(dòng)態(tài)分配路徑的路由算法。

根據(jù)數(shù)據(jù)流的傳輸方向，定義S、N、E、W分別代表南、北、東、西四個(gè)方向。針對(duì)2D-Mesh拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)分布特征，可將源節(jié)點(diǎn)和目的節(jié)點(diǎn)的相對(duì)位置劃分為六種情況：EW、SN、WS、WN、ES、NE，如圖1所示，其中s和d分別代表源節(jié)點(diǎn)和目的節(jié)點(diǎn)。由此判斷路由節(jié)點(diǎn)之間存在的最短路徑，并給出下一跳路由的方向。

分別用(xs,ys)、(xd,yd)表示節(jié)點(diǎn)s和d的坐標(biāo)，x維由北向南遞增，y維由東向西遞增，在保證最短路徑的條件下，其路徑分配為：當(dāng)相對(duì)位置為EW時(shí)，xs=xd且 ys≠yd，若 ys＞yd，節(jié)點(diǎn) s的下一路由節(jié)點(diǎn)為(xs,ys-1)；若ys＜yd，節(jié)點(diǎn)s的下一路由節(jié)點(diǎn)為(xs,ys+1)。當(dāng)相對(duì)位置為SN時(shí)，xs≠xd且 ys=yd，若 xs＞xd，節(jié)點(diǎn) s的下一路由節(jié)點(diǎn)為(xs-1,ys)；若 xs＜xd，節(jié)點(diǎn) s的下一路由節(jié)點(diǎn)為(xs+1,ys)。當(dāng)相對(duì)位置為WS時(shí)，xs＜xd且ys＜yd，節(jié)點(diǎn)s可以選擇(xs+1,ys)或(xs,ys+1)作為滿足條件的下一路由節(jié)點(diǎn)。當(dāng)相對(duì)位置為WN時(shí)，xs＞xd且 ys＜yd，節(jié)點(diǎn) s可以選擇(xs-1,ys)或(xs,ys+1)作為滿足條件的下一路由節(jié)點(diǎn)。當(dāng)相對(duì)位置為ES時(shí)，xs＜xd且ys＞yd，節(jié)點(diǎn)s可以選擇(xs+1,ys)或(xs,ys-1)作為滿足條件的下一路由節(jié)點(diǎn)。當(dāng)相對(duì)位置為NE時(shí)，xs＞xd且 ys＞yd，節(jié)點(diǎn)s可以選擇(xs-1,ys)或(xs,ys-1)作為滿足條件的下一路由節(jié)點(diǎn)。

兩節(jié)點(diǎn)間曼哈頓距離越大，最短路徑就越多，令dx=|xs-xd|，dy=|ys-yd|，在2D-Mesh拓?fù)浣Y(jié)構(gòu)的NoC中，節(jié)點(diǎn)s到d滿足曼哈頓距離的最短路徑數(shù)為 N=(dx+dy)！/(dx！dy！)［6］。因此，隨著網(wǎng)絡(luò)負(fù)載的不斷加大，對(duì)易產(chǎn)生網(wǎng)絡(luò)熱點(diǎn)或擁塞的中間區(qū)域節(jié)點(diǎn)，在通信節(jié)點(diǎn)間滿足多條最短路徑的情況下，需要?jiǎng)討B(tài)分配下一路由節(jié)點(diǎn)的路徑，其規(guī)則是：當(dāng)存在多條最短路徑時(shí)，則當(dāng)前節(jié)點(diǎn)根據(jù)相鄰節(jié)點(diǎn)的擁塞情況，選擇輸入端口緩沖器已存儲(chǔ)隊(duì)列長(zhǎng)度的積壓最小的鄰居節(jié)點(diǎn)發(fā)送分組；在滿足延時(shí)約束的基礎(chǔ)上，若最短路徑唯一，則該路徑是最優(yōu)路徑。

1.2 邊緣節(jié)點(diǎn)的路由方式

當(dāng)源節(jié)點(diǎn)處于邊緣節(jié)點(diǎn)時(shí)，在滿足最短路徑的前提下，由目的節(jié)點(diǎn)與源節(jié)點(diǎn)x維的方向值做出確定性路由判斷。如圖2所示，當(dāng)路由需要轉(zhuǎn)向時(shí)，基于Turn Model模型［7］，路由轉(zhuǎn)向禁止WN、SW、SE和EN。

圖1 源節(jié)點(diǎn)和目的節(jié)點(diǎn)的相對(duì)位置

在邊緣節(jié)點(diǎn)上，路由方法概括為：如果源節(jié)點(diǎn)x維方向的值與目的節(jié)點(diǎn)相同，則將數(shù)據(jù)包沿x維方向轉(zhuǎn)發(fā)；同理，源節(jié)點(diǎn)y維方向的值與目的節(jié)點(diǎn)相同，則沿y維方向轉(zhuǎn)發(fā)；如果上述情況不滿足，由目的節(jié)點(diǎn)與源節(jié)點(diǎn)x維的方向值做出路由判斷，當(dāng)xs＜xd時(shí)，采用先垂直后水平方向的路由方式，允許的轉(zhuǎn)向?yàn)镹W和NE；反之采用先水平后垂直方向的路由方式，允許的轉(zhuǎn)向?yàn)镋S和WS。這樣，相對(duì)于通常的XY路由方式，不僅能減少路由時(shí)在x維上的阻塞，還可以大大節(jié)約網(wǎng)絡(luò)實(shí)現(xiàn)的硬件資源。

圖2 邊緣節(jié)點(diǎn)對(duì)應(yīng)的Turn Model模型

對(duì)2D-Mesh拓?fù)浣Y(jié)構(gòu)上的網(wǎng)絡(luò)節(jié)點(diǎn)，設(shè)(dx,dy)為目的路由節(jié)點(diǎn)地址，(lx,ly)為當(dāng)前路由節(jié)點(diǎn)地址，在DARA算法下的路由流程如圖3所示。

2 實(shí)驗(yàn)設(shè)置與性能分析

2.1 OPNET建模與仿真

OPNET［8，9］起源于 MIT，在 OPNET Modeler環(huán)境下提供網(wǎng)絡(luò)層、節(jié)點(diǎn)層以及進(jìn)程層的層次化網(wǎng)絡(luò)建模機(jī)制，是目前最先進(jìn)的網(wǎng)絡(luò)仿真平臺(tái)之一。OPNET通過(guò)執(zhí)行離散事件仿真來(lái)分析各種模擬系統(tǒng)的行為及性能，仿真效率相對(duì)于基于時(shí)間的連續(xù)仿真要高。

圖3 DARA算法流程圖

2.1.1 2D-Mesh網(wǎng)絡(luò)層建模

在OPNET Modeler平臺(tái)上對(duì)5×5的2D-Mesh拓?fù)浣Y(jié)構(gòu)進(jìn)行建模，它由25個(gè)IP核、25個(gè)交換節(jié)點(diǎn)以及40條雙向鏈路構(gòu)成，如圖4所示。對(duì)交換節(jié)點(diǎn)和IP核實(shí)現(xiàn)xy坐標(biāo)編碼(xi,yj)，其中1≤i,j≤5。

圖4 網(wǎng)絡(luò)層建模

2.1.2 2D-Mesh節(jié)點(diǎn)層建模

圖5為路由節(jié)點(diǎn)的建模。其中src用于封裝數(shù)據(jù)包，sink用于處理相關(guān)數(shù)據(jù)。四對(duì)收、發(fā)信機(jī)分別代表東南西北四個(gè)方向上與周圍節(jié)點(diǎn)的連接。router代表路由器功能，實(shí)現(xiàn)鏈路控制、輸入端FIFO、交叉開(kāi)關(guān)、路由和仲裁功能。

圖5 路由節(jié)點(diǎn)建模

2.1.3 2D-Mesh進(jìn)程層建模

在OPNET中，通過(guò)有限狀態(tài)轉(zhuǎn)移圖建立進(jìn)程模型，用圖標(biāo)表示狀態(tài)，狀態(tài)之間的轉(zhuǎn)換用連線表示。用Proto-C編寫(xiě)程序，實(shí)現(xiàn)網(wǎng)絡(luò)狀態(tài)的模擬。在NoC仿真模型建模中，需要對(duì)源進(jìn)程、接收進(jìn)程和路由進(jìn)程進(jìn)行建模。

（1）源進(jìn)程

在NoC中，源進(jìn)程用于產(chǎn)生數(shù)據(jù)包。如圖6（a）所示，在仿真系統(tǒng)啟動(dòng)時(shí)，發(fā)送的信息會(huì)在INIT狀態(tài)中進(jìn)行初始化，然后由GENERATE根據(jù)給定的函數(shù)，使源進(jìn)程按照一定的時(shí)間分布產(chǎn)生數(shù)據(jù)包，并將數(shù)據(jù)包發(fā)送出去。當(dāng)網(wǎng)絡(luò)狀態(tài)觸發(fā)STOP和DISABLED事件時(shí)，則終止發(fā)送。

（2）接收進(jìn)程

接收進(jìn)程主要用于收集仿真中所產(chǎn)生的數(shù)據(jù)，用于分析仿真情況。如圖6（b）所示，在仿真系統(tǒng)啟動(dòng)時(shí)，在初始化INIT狀態(tài)下，通過(guò)相應(yīng)函數(shù)的注冊(cè)進(jìn)而統(tǒng)計(jì)仿真量，并對(duì)接收模塊進(jìn)行必要的配置，初始化后直接進(jìn)入到DISCARD狀態(tài)等待下一事件的到來(lái)。DISCARD狀態(tài)用于拆分?jǐn)?shù)據(jù)包，同時(shí)統(tǒng)計(jì)網(wǎng)絡(luò)仿真量，等待完畢后返回DISCARD狀態(tài)，等待下次觸發(fā)。

（3）路由進(jìn)程

路由進(jìn)程主要是對(duì)數(shù)據(jù)包的存儲(chǔ)轉(zhuǎn)發(fā)、路徑分配和仲裁的功能模擬。如圖6（c）所示，在仿真系統(tǒng)啟動(dòng)時(shí)，處理的信息先在INIT狀態(tài)下進(jìn)行初始化，之后進(jìn)入到狀態(tài)機(jī)IDLE_0，如果在某時(shí)刻觸發(fā)PKT_ARR或者PK_SEND_INTRPT事件時(shí)，將執(zhí)行route_v1函數(shù)。如果在某時(shí)刻觸發(fā)CHANNEL_STAT_UPDATE或者PK_SEND_FLAG事件時(shí)，則執(zhí)行PK_RESET事件，從而完成數(shù)據(jù)包的路由。

2.2 性能分析

在芯片設(shè)計(jì)中，比較重要的指標(biāo)包括性能、功耗和面積等；對(duì)于通信網(wǎng)絡(luò)，較重要的性能指標(biāo)主要包括帶寬、時(shí)延和吞吐量等。其中，端到端時(shí)延和吞吐量是NoC路由算法設(shè)計(jì)的兩個(gè)重要的性能參數(shù)。本文建模并仿真了5×5的2D-Mesh拓?fù)浣Y(jié)構(gòu)，交換機(jī)制采用蟲(chóng)孔交換機(jī)制，仿真環(huán)境中數(shù)據(jù)的最小單元是Flit，每個(gè)數(shù)據(jù)包由8個(gè)Flit組成，且每個(gè)Flit是32bit。實(shí)驗(yàn)仿真通過(guò)均勻模式和熱點(diǎn)模式，同時(shí)收集了網(wǎng)絡(luò)平均端到端時(shí)延以及網(wǎng)絡(luò)平均吞吐量，對(duì)DARA路由算法與通常的XY路由算法及自適應(yīng)DyXY路由算法進(jìn)行比較。

如圖7所示，在均勻模式下，每一節(jié)點(diǎn)等概率發(fā)送分組到其他節(jié)點(diǎn)。在低注入率的情況下，網(wǎng)絡(luò)不容易擁塞，XY路由具有較好的性能。當(dāng)注入率達(dá)到0.3時(shí)，XY路由的平均時(shí)延開(kāi)始迅速增長(zhǎng)；DyXY路由由于自身的適應(yīng)性，可以很好的緩解Mesh網(wǎng)絡(luò)在高負(fù)載情況下的擁塞狀況，相對(duì)XY路由平均端到端時(shí)延較??；DARA路由具有一定的適應(yīng)性且路徑最短，平均端到端時(shí)延最低。對(duì)于網(wǎng)絡(luò)吞吐量，XY路由和DARA路由最先飽和，由于DyXY路由對(duì)網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的自適應(yīng)性，性能最好。如圖8所示，在熱點(diǎn)模式下，設(shè)置多個(gè)節(jié)點(diǎn)為熱點(diǎn)，與其他節(jié)點(diǎn)相比，它們將接收更多的流量。XY路由無(wú)法繞開(kāi)熱點(diǎn)區(qū)域，隨著網(wǎng)絡(luò)注入率的增大，性能最差；DyXY路由由于自身的適應(yīng)性，性能稍好；DARA路由由于中心區(qū)域節(jié)點(diǎn)采用了最短路徑的動(dòng)態(tài)路由，能一定程度上繞開(kāi)熱點(diǎn)進(jìn)行路由，性能較好。當(dāng)注入率達(dá)到0.2-0.3時(shí)，網(wǎng)絡(luò)平均時(shí)延最低，且隨網(wǎng)絡(luò)注入率的逐漸增大，時(shí)延相對(duì)XY路由和DyXY路由有明顯的優(yōu)勢(shì)，對(duì)于網(wǎng)絡(luò)吞吐量，XY路由和DyXY路由隨網(wǎng)絡(luò)注入率的增大急劇下降，DARA路由則有所緩解。當(dāng)網(wǎng)絡(luò)注入率達(dá)到0.8～0.9時(shí)，網(wǎng)絡(luò)吞吐量最高。

圖6 進(jìn)程層建模

圖7 均勻模式下三種路由算法平均時(shí)延和吞吐量的比較

圖8 熱點(diǎn)模式三種路由算法平均時(shí)延和吞吐量的比較

3 結(jié)論

對(duì)于確定拓?fù)浣Y(jié)構(gòu)的NoC，一個(gè)高效的路由算法對(duì)網(wǎng)絡(luò)的性能有著重要的作用，在設(shè)計(jì)路由算法時(shí)需要考慮網(wǎng)絡(luò)時(shí)延、吞吐、死鎖發(fā)生率、邏輯復(fù)雜度等影響網(wǎng)絡(luò)性能的問(wèn)題。本文在研究現(xiàn)有的NoC確定性和適應(yīng)性路由算法的基礎(chǔ)上，針對(duì)2D-Mesh拓?fù)浣Y(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)，提出一種新的路由算法DARA，并在OPNET Modeler環(huán)境下進(jìn)行了建模仿真，通過(guò)仿真結(jié)果得出該算法在熱點(diǎn)模式下具有良好的性能；與通用的XY路由相比，可以更好地適用于高注入量下的網(wǎng)絡(luò)擁塞和熱點(diǎn)現(xiàn)象，與自適應(yīng)DyXY路由相比，實(shí)現(xiàn)成本更優(yōu)。

［1］王坤鵬.片上網(wǎng)絡(luò)面向路由算法的研究［D］.西安：西安電子科技大學(xué)，2012.

［2］Ville R，Teijo L，Juha P.Network on chip routing algorithms［R］.TUCS TechnicalReportNo.779，2006，51（2）：10-11.

［3］才華，楊勇，李洋.片上網(wǎng)絡(luò)擁塞感知算法研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（4）：178-181.

［4］Ali M，Welzl M，Hellebrand S.A dynamic routing mechanism for network on chip［C］.23rd NORCHIP Conference，2005，12（3）：70-73.

［5］Daneshtalab M，Sobhani A，Afzali-Kusha A，et al.NoC hot spot minimization using ant net dynamic routing algorithm［J］.Proceedings of Application-specific Systems，Architectures and Processors，2006，11（13）：33-38.

［6］王婷.保證QoS的片上網(wǎng)絡(luò)動(dòng)態(tài)路徑分配算法研究［D］.南京：南京航空航天大學(xué)，2010.

［7］Glass C J，Lionel M N.The turn model for adaptive routing［C］.Proc of the 19th Annual International Symposium on Computer Architecture，1992，25（7）：278-287.

［8］陳敏.OPNET網(wǎng)絡(luò)仿真［M］.北京：清華大學(xué)出版社，2004.

［9］李馨，葉明.OPNET Modeler網(wǎng)絡(luò)建模與仿真［M］.西安：西安電子科技大學(xué)出版社，2006.