呂瑞，李洋

（長春理工大學 電子信息工程學院，長春 130022）

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

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

1 DARA算法

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

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

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

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

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

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

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

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

圖1 源節(jié)點和目的節(jié)點的相對位置

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

圖2 邊緣節(jié)點對應的Turn Model模型

對2D-Mesh拓撲結構上的網(wǎng)絡節(jié)點，設(dx,dy)為目的路由節(jié)點地址，(lx,ly)為當前路由節(jié)點地址，在DARA算法下的路由流程如圖3所示。

2 實驗設置與性能分析

2.1 OPNET建模與仿真

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

圖3 DARA算法流程圖

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

在OPNET Modeler平臺上對5×5的2D-Mesh拓撲結構進行建模，它由25個IP核、25個交換節(jié)點以及40條雙向鏈路構成，如圖4所示。對交換節(jié)點和IP核實現(xiàn)xy坐標編碼(xi,yj)，其中1≤i,j≤5。

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

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

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

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

2.1.3 2D-Mesh進程層建模

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

（1）源進程

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

（2）接收進程

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

（3）路由進程

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

2.2 性能分析

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

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

圖6 進程層建模

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

圖8 熱點模式三種路由算法平均時延和吞吐量的比較

3 結論

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

［1］王坤鵬.片上網(wǎng)絡面向路由算法的研究［D］.西安：西安電子科技大學，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)絡擁塞感知算法研究［J］.長春理工大學學報：自然科學版，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)絡動態(tài)路徑分配算法研究［D］.南京：南京航空航天大學，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)絡仿真［M］.北京：清華大學出版社，2004.

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