基于OPNET的片上网络路由算法的建模与仿真

陈良昌，刘召军，张彦军

(1.中北大学仪器科学与动态测试教育部重点实验室，山西 太原 030051；2.中北大学电子测试技术重点实验室，山西 太原 030051)

1 引言

随着大规模集成电路和半导体技术的快速发展，在有限的空间中，可以放置越来越多的电子器件。这就使得越来越多的功能模块可以集成在一块芯片上，片上系统(System-on-Chip，SoC)的概念应运而生[1]。片上系统包含多个可以实现某一功能的知识产权核(Intellectual Property，IP)，这些知识产权核通过总线的方式与处理器保持通信[2]。但由于总线带宽的限制，IP核与处理器之间的通信会受到制约，产生一定的延时。片上系统所集成的IP核越多延时越高，集成电路芯片的工作效率就会受到很大的影响[3]。

为了解决总线通信中存在的这些问题，研究人员从计算机网络受到启发，提出了片上网络(Network on Chip，NoC)这样全新的通信架构[4]。文献[5]介绍了片上网络应用在集成电路上的依据与原理。与片上系统不同的是，IP核连接在路由节点上，路由节点间相互连接，形成一个网络[6]。在片上网络中，每个IP核在与处理器进行通信的时候，有很多条链路可以选择。这样就避免了数据传输过程中因带宽不够而造成的不必要等待，很好的解决了IP核与处理器之间通信的时延问题[7]。但是，在片上网络的热点区域很容易发生堵塞，所以片上网络路由的研究成为当前片上网络研究的一个重要方向[8]。

片上网络路由算法的研究过程中，国外主要把算法分为两种类型：确定性路由算法和自适应路由算法[9]。其中确定性路由算法是最简单和最容易实现的路由算法。但是确定性路由算法由于其本身的局限性，在大量数据包进入网络时，由于不能自主选择路径，存在平均延时较大，链路利用率不高等缺点。在自适应路由算法中，目前研究最简单的是维序XY路由算法，MIT的RAW、Tile64以及Intel公司的Tera-Scale都采用这种算法进行NoC上的数据通信[10]。国内对片上网络的研究较国外起步晚，主要研究是对原有的通用路由算法进行改进。本文路由算法采用两种约束条件，提高了节点间数据路由的自适应性，大大提高了数据传输的端对端延时和链路利用率。

2 片上网络路由算法

路由算法在很大程度上决定着片上网络的各项性能。目前，片上网络硬件搭建最普遍的是在二维拓扑结构下展开的。所以本文基于最典型的4×4 2D-Mesh结构对片上网络的一种路由算法进行仿真。该路由算法通过两个步骤的约束条件对数据包进行路径的选择。第一步，比较中间地址与目的地址的坐标；第二步，比较各个通道间链路利用率的大小。

各个节点的地址由(x，y)两个参数表示，传输方向由E、S、W、N、L表示，分别代表东、南、西、北、本地五个传输方向，如图1所示。节点源地址用(xs，ys)表示，目的地址用(xd，yd)表示，在数据包传输的过程中，地址是实时变化的，称为中间地址，用(xm，ym)表示。

图1 片上网络各节点坐标

中间地址与目的地址的比较关系有以下8种情况。①当xm=xd且ymyd时，数据包向N方向传输；③当ym=yd且xmxd时，数据包向W方向传输；⑤当xmxd且ymyd时，数据包在N和E两个方向中进行选择；⑧当xm>xd且ym>yd时，数据包在N和W两个方向中进行选择。

之后，比较各个通道间的链路利用率，主要是对上一约束条件中有两种路径选择的情况进行再次判断，以确定数据传输的路径。它通过比较两条路径上的链路利用率大小，选择链路利用率小的路径进行传输。路由算法具体流程图如图2所示。

图2 路由算法流程图

3 OPNET模型建立

3.1 网络层

OPNET[11]-[13]的网络层建模主要描述了模型的拓扑结构和数据传输的方式，本次建模是基于4×4 2D-Mesh结构建立的片上网络数据传输模型。如图3所示，由16个节点和24条链路构成。根据数据在网络模型中传输的要求，链路采用全双工链路。

图3 网络层模型图

3.2 节点层

根据所连接的链路的个数的不同，建立三种类型的节点。主要区别在于发信机和接信机的数量不同和仲裁模块接收来自各个方向的统计量的数量不同。其中node0、3、13、16节点模型如图4(a)所示，node1、2、4、7、8、11、13、14节点的模型如图4(b)所示，node5、6、9、10节点模型如图4(c)所示。节点层的建模主要包括rcv模块、xmt模块、src模块、queue模块、dest_select模块、arbiter模块、proc模块、fifo模块和sink模块。

图4 节点层模型图

从各个方向传输到本节点的数据包，通过rcv模块接收后传输到queue模块进行存储，数据包想要传输到proc模块，需要经过arbiter模块的仲裁。arbiter模块收集来自queue模块和proc模块的统计量并进行分析，反馈给queue模块一个统计量来控制queue模块中的数据包传输到proc模块中。proc模块首先对数据包的中间地址进行更新，然后确定数据包的传输方向。之后将数据包传输到相应方向的fifo模块中，fifo模块再将数据包传输到xmt模块发送出去。src模块用来产生数据包，然后由dest_select模块标定数据包的源地址和目的地址。sink模块用来销毁目的地址为本节点的数据包。

3.3 进程层

OPNET进程层通过构建状态转移图和Proto-C语言编程，来模拟节点层各个模块内部的工作状态[14]。其中xmt模块与rcv模块分别为发信机模块、接收机模块，用来发送和接收数据包，无进程模型。src模块使用OPNET提供的simple_source进程模型，fifo模块使用acb_fifo进程模型，sink模块使用sink进程模型。其余进程模型根据片上网络路由方法的具体内容进行设计。

dest_select模块的进程层模型如图5所示。首先执行idle状态的进入执行(Enter Executives)对本节点的地址进行设定，然后当有数据流到来时，触发PK_ARRVL中断，执行rout_pk()函数。将本节点的地址赋值给数据包源地址，并设置数据包的目的地址。

图5 dest_select模块进程层模型

queue模块的进程层模型如图6所示。queue模块与fifo模块都为队列模块，不同的是进入queue模块的数据包必须接受到来自arbiter模块的传输命令后，才能移出队列。首先执行init状态进行一系列的初始化设定和统计量的定义，然后跳转到wait状态进行等待。当有数据流到来时触发ARRIVAL中断，跳转到insert状态，将传输来的数据包插入到队列中去。当来自arbiter模块的统计流到来时触发FLOW_CONTROL中断，跳转到svc_start状态。当统计流中有arbiter模块反馈来的传输命令时，产生一个自中断。此时触发SVC_COMPLETION中断，跳转到svc_compl状态，使数据包强制移出队列，传输到proc模块。当模块处于wait状态时，会产生统计流给arbiter模块。表示模块空闲，可以传送数据包。

图6 queue模块进程层模型

proc模块的进程层模型如图7所示。首先执行init状态的Enter Executives对本节点的地址进行设定，跳转到idle状态。当有数据流到来时，触发PK_ARRVL中断，执行rout_pk()函数。更新数据包的地址，并根据上述约束条件进行路径选择，确定数据包的传输方向。之后将数据包传输到相应方向的fifo模块中，准备发送出去。当模型中无数据流的时候，会产生统计流给arbiter模块。表示模块空闲，可以接收数据包。

图7 proc模块进程层模型

arbiter模块的进程层模型如图8所示。Init状态中对控制各个queue模块的统计量进行设定，然后跳转到idel状态。当同时接收到某个queue模块的空闲统计流和proc模块的空闲统计流后，便会产生一个统计流传送到相应的queue模块中。若有多个queue模块满足条件，则随机选择一个queue模块发送统计流。

图8 arbiter模块进程层模型

4 仿真研究

经过以上三个层次的建模后，片上网络模型已经搭建完成。基于该模型进行仿真，测试本模型数据传输的吞吐量和时延性能。比较网络在正常状态和繁忙状态下的吞吐量，观察在数据量较大的情况下，数据包选择路径的情况；将该路由算法与确定性路由算法的平均延时进行比较。在模型中设置7个节点产生数据包，相应的设置7个节点接收数据包。数据包具体的传输为node0到node10，node3到node9，node6到node12，node8到node1，node10到node4，node11到node2，node15到node7。

在节点层添加source interarrival time的参数值3和10，代表数据包产生的间隔分别为3s和10s。这样来区分大量数据传输情况与正常数据传输情况。设置仿真时间长度为2000秒。实验一的source interarrival time设置为3，实验二的source interarrival time设置为10，其它条件都一样。分别得出在数据包产生时间间隔为3s和10s时的各个链路的吞吐量如图9和图10所示。

图9 时间间隔为3s的各链路吞吐量

图10 时间间隔为10s的各链路吞吐量

根据两个实验的吞吐量可以得出两个实验中数据包的传输路径，如图11和图12所示。

图11 时间间隔为10s的路径图

图12 时间间隔为3s的路径图

可以看出，在包产生时间间隔为10秒的时候，节点node5，node6为热点节点。当时间间隔变小，产生的数据量变多的时候，仿真模型会适当的避开热点节点node5和node6，寻找新的路径进行传输。表明该模型在遇到大量数据传输的时候，可以根据各节点的利用率，有效的选择合适的路径，避免了大量数据因选择同一路径而造成的拥堵。

对传统的确定性路由算法进行建模，与本文所诉路由算法相比。在数据包传输的源地址与目的地址相同，产生数据包时间间隔为3s的条件下，查看仿真的端到端的平均延时，如图13所示。起初的时候由于链路畅通延时很小，随着数据包产生数量的增多，延时会迅速增加，之后产生包和销毁包的数量达到动态平衡，故在曲线上显示为一条直线。可以看出，与传统的确定性路由相比，该路由算法平均延时小，传输速度快。

图13 端到端平均延时

5 结语

本文提出了一种片上网络路由算法，建立了一个基于4×4 2D-Mesh拓扑结构的片上网络模型，并对该模型进行了网络层、节点层、进程层的建模。对该模型在正常状态和繁忙状态下进行仿真，分别得出各个链路的吞吐量，在此基础分析后得出数据包的传输路径，进行比较。可以看出在大量数据包涌入网络的时候，会根据各个节点的具体情况，选择传输路径。减少某些热点节点的压力，有效的避免了因数据量大而造成的延时增大或堵塞现象。与传统的确定性路由相比，延时更小，效率更高。