一種基于OPNET的NoC路由算法設計

呂瑞，李洋

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

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

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

1 DARA算法

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

1.1 中間區域節點的路由方式

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

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

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

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

1.2 邊緣節點的路由方式

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

圖1 源節點和目的節點的相對位置

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

圖2 邊緣節點對應的Turn Model模型

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

2 實驗設置與性能分析

2.1 OPNET建模與仿真

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

圖3 DARA算法流程圖

2.1.1 2D-Mesh網絡層建模

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

圖4 網絡層建模

2.1.2 2D-Mesh節點層建模

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

圖5 路由節點建模

2.1.3 2D-Mesh進程層建模

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

（1）源進程

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

（2）接收進程

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

（3）路由進程

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

2.2 性能分析

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

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

圖6 進程層建模

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

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

3 結論

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

［1］王坤鵬.片上網絡面向路由算法的研究［D］.西安：西安電子科技大學，2012.

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

［3］才華，楊勇，李洋.片上網絡擁塞感知算法研究［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的片上網絡動態路徑分配算法研究［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網絡仿真［M］.北京：清華大學出版社，2004.

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