一种基于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.