基于加权轮询仲裁的NoC 容错路由设计*

张培雯 于宗光 陈振娇 徐新宇

(1.江南大学物联网工程学院,江苏 无锡 214122；2.中国电子科技集团公司第五十八研究所,江苏 无锡 214072)

片上网络(Network-on-Chip,NoC)本质上是一种为解决片上多核系统设计中核间通信以及核与非核硬件单元之间数据传输问题的通信方案。相比于片上总线(On-Chip-Bus,OCB),NoC 因其集成度高、扩展性强、并行度高以及功耗低等优势,已经逐渐取代OCB 成为新的片上通信标准[1]。

路由器作为NoC 中负责通信数据暂存和转发的模块,其设计对NoC 的传输效率具有重要影响。随着NoC 中处理器核心数目的增多以及通信量的增大,出现网络拥塞问题的概率也相应增加。路由器的设计中应考虑拥塞缓解,平衡网络负载。目前,有很多文献提到路由器设计中的拥塞缓解问题,例如通过专门的拥塞信息传播网络来获取拥塞信息,或者在相邻节点间设置旁路路径来传输拥塞信息,也有通过下游路由节点的空闲缓存数量来判断拥塞程度,最后根据拥塞情况选择一条拥塞程度最小的传输路径[2-4]。对于拥塞情况的处理,此类研究大多采用路由算法的优化,但是自适应算法可能存在数据包中切片无序到达目的节点问题,需要在目的端对包进行重新排序,如此网络接口的设计复杂度增加,设计的面积开销过大,并且很少考虑到网络中链路故障的情况。为此,本文在现有研究的基础上,提出基于加权仲裁的路由器设计方案,对路由仲裁模块采用双层仲裁机制,第一层仲裁采用权重策略,基于本地输入负载情况以及报文剩余跳数的考虑给每个输入请求赋予不同的权重Wi,Wi作为第二层轮询仲裁的指针。本地负载较重且报文剩余跳数较少的请求被赋予更高的权重,对其优先进行传输,当传输完成后根据权重值的大小依次传输其他报文。与此同时,本文路由计算模块采用具有容错功能的自适应路由算法,避免因链路故障而面临的阻塞情况,提高了网络传输效率。

1 NoC 路由概述

1.1 2D_Mesh NoC 结构

一个典型的NoC 包括物理链路(Link,L)、路由器(Router,R)、网络接口(Network Interfaces,NI)和处理单元(Processing Elements,PE)。如图1 所示为一个典型二维网格(2D-Mesh)NoC 结构。

图1 一个典型2D-Mesh NoC 结构

1.2 路由器架构

根据在网络中所处位置不同,路由可分为内部路由节点,边沿路由节点和对角路由节点,其路由器结构也因此有所差异。内部路由节点具有五个输入输出端,边沿路由节点具有四个输入输出端,而对角路由节点只有三个输入输出端。以内部路由节点为例,输入和输出分别有东(E)、南(S)、西(W)、北(N)四个方向,通过双向链路连接相邻路由器,还有一个本地(L)端口连接资源节点(PE)。其内部由输入单元、路由计算单元(Routing Computation,RC)、虚通道分配单元(Virtual-Channel Allocation,VA)和交叉开关分配单元(Switch Allocation,SA)、交叉开关以及输出单元组成[5]。

输入模块由寄存器搭建的缓存单元和相应的控制逻辑,缓存单元被组织成队列的形式,每一个队列是一条虚通道(VC)。RC 基于头切片中目的节点位置信息等计算出报文从当前节点到目的节点的传输路径,即路由算法的实现。完成RC 后,头切片发起输出端VC 请求,VA 收集所有输入请求后,对输出VC 进行分配,保证每条输出VC 最多被分配给一条输入请求,每一输入请求最多获得一条输出VC 授权。RC 和VA 都是以报文为粒度,只需要头切片执行,体切片和尾切片则随头切片进行传输,即头切片带动整个报文的传输。当输入获得输出VC 的授权后,路由器检查输出端VC 缓存情况,如果有空闲缓存,切片会向SA 单元发起交叉开关传输请求。交叉开关是由多个多路选择器组成,当切片获得授权,经过交叉开关传输至输出端口,交叉开关则向上游路由器反馈一个credit 信号,表示释放一个缓存单元。输出单元由多个寄存器组成,记录下游VC 状态。本文路由器的结构如图2 所示。

图2 NoC 路由器结构框图

1.3 虚通道技术

本文考虑到在网络拥塞时,出现头切片被阻塞,从而导致整个包的切片都无法传输,其传输的整个链路被阻塞的情况,为每个端口设置了2 条VC 缓存区间,每条VC 的深度为16。图3 所示为缓存模块框图,图中每个缓存空间对应一条VC,数据的输入和输出通过数据选择器(MUX)控制。模块中计数器用以记录每个缓存区间的剩余可用空间。常规VC 分配中,当持有VC 的尾切片离开路由器时,VC就可重新分配。本文采用原子VC 分配,在路由器接收到前一个包的尾切片的信元之前,VC 不能被重新分配。这确保了每个VC 在任何给定的时间只持有一个包,从而避免了网络中连续包之间的依赖关系。虽然常规的VC 分配可以在有限数量的VC下提供更高的吞吐率,但是原子VC 分配由于可以避免头阻塞,从而体现出更好的传输性能。

图3 单端口数据缓存

2 路由算法

路由算法负责为报文计算源节点到目的节点之间的传输路径。路由算法包括路由协议和路由策略,路由协议根据收集的网络信息形成路由表,路由策略则规定了查询路由表选择下一跳路由节点的方式。在网络无故障的情况下,本文采用的路由算法遵循最短路径原则[6],首先,比较源节点与目的节点的坐标,得到其X维度和Y维度上距离差值ΔX和ΔY。当ΔX＜＝ΔY,使用XY路由算法,先进行X维度寻径,当Xlocal＝Xdes时,进行Y维度寻径直到Ylocal＝Ydes,报文传输至目的节点；当ΔX＞ΔY,使用YX路由算法,先进行Y维度寻径,当Ylocal＝Ydes,再进行X维度寻径直到Xlocal＝Xdes,报文传输至目的节点。

对网络中可能出现的故障情况,本文采用的检测方法是,在一定周期内每个路由节点向相邻节点发送测试向量,当节点获取到响应向量后,与发送的向量相比对,若两者相同则链路无故障,否则断定链路存在故障[7-9]。确定故障后,将故障链路标记在路由表中,通过绕开故障点完成数据传输[10-11]。首先,根据无故障情况下默认路由算法,计算从源节点到目的节点的传输路径。若被标记的故障点不在其传输路径上,则根据默认路由算法进行传输至目的节点；若被标记故障点在其传输路径上,报文传输至故障点前一级路由后,往另一维度传输一跳路由,接着从当前节点到目的节点根据默认路由算法计算得到传输路径进行传输。具体算法流程如图4 所示。

图4 路由算法流程图

3 加权轮询仲裁设计

在NoC 路由节点中,路由仲裁单元主要是为处理多个输入端请求同一输出端的情况。目前路由仲裁单元大多采用固定仲裁和轮询仲裁策略,固定仲裁是对每个输入端设置固定优先级,当优先级最高的输入端一直存在对此输出端口的请求时,则其一直被响应,其他输入请求就会有“饿死”的风险,所以固定优先级仲裁不够公平,资源分配不够合理。轮询仲裁首先对各输入端设置默认优先级,第一轮仲裁批准最高优先级的输入端请求传输,随后其在下一轮仲裁优先级降至最低,其他输入端优先级顺次上升,如图5 所示为轮询算法原理图。轮询仲裁使得每个输入通道请求得以批准的概率相同,保证了公平性,但是当NoC 中IP 发送的信息不是同一类型,以及各端口流量具有较大差异时,轮询仲裁则并不适合[12-15]。

图5 轮询仲裁原理图

本文采用优先级可配置的仲裁策略,采用双层仲裁。第一层为权重仲裁,对输入端的负载量Li和请求报文的传输剩余跳数综合考虑,赋予不同请求不同的权重。负载量较大的输入端存在拥塞的可能性较大。同时,报文的传输剩余跳数(Remaining Hop Count,RHC)是报文在当前路由到目的路由之间的传输距离。传输方向上RHC 小的报文需要较少的时间在网络中传输,对其优先传输,能够使其占用的网络的缓存资源尽快释放给其他报文使用,能够避免网络拥塞。所以报文权重正比于输入端负载量,与报文剩余跳数成反比。对输出端为东、南、西、北这四个方向时,权重的计算公式为:

式中:Li为输入端负载量,RHC 为当前报文的传输剩余跳数值。将不同输入请求根据权重值进行排序,权重值越高优先级越高。当输出端为本地方向时,权重直接由输入端负载量决定。

公平性仍然是仲裁不可以忽略的原则,为防止高优先级输入端一直占用资源,导致低优先级请求“饿死”,第二层仲裁采用轮询算法。

图6 为本文仲裁器的结构框图,由权重仲裁、和轮询仲裁两级组成。参与资源竞争的各报文的权重由第一层权重仲裁产生。生成的权重作为第二层轮询仲裁的指针,权重值越高其优先级越高,则此报文赢得仲裁,当此报文传输完成,则根据优先级高低顺次响应其他请求。

图6 优先级可配置仲裁器

4 仿真与结果分析

本文通过Verilog 实现路由器各个模块的设计,并使用Modelsim 进行仿真验证。图7 是优先级可配置仲裁的仿真波形,当东西南北四个方向的输入端均存在对本地输出的请求时,根据第一层基于输入端负载情况而确定各请求的权重,权重值越高则优先级越高,由图可知东输入端权重值最高,则其方向报文优先经交叉开关传输至本地,根据轮询仲裁算法,当最高优先级请求传输完成后,选择优先级次高的端口。

图7 仲裁波形图

当前某节点的西和南输入端口都存在数据包传输请求,但两输入请求不同输出端,即两组数据传输不存在冲突,则两请求各自传输,如图8 所示。

图8 无竞争时数据传输

当前某节点的西和南输入端均存在对节点的东输出端的请求,此时需要对两请求进行仲裁,经过仲裁后输出端口首先分配给西输入请求,待西端口数据包传输完成,接着南输入端口的请求被响应,如图9所示。

图9 存在竞争时数据传输

本文使用NoC 模拟仿真器Booksim,比较了本文仲裁和一般轮询仲裁的路由器在uniform 和Transpose 流量模式下的数据包传输平均延时。表1为仿真参数配置。

表1 模拟器参数设置

两种流量模式的延迟曲线如图10 所示。在uniform 流量模式下,网络中各节点的流量情况较平均,Transpose 是一种非均匀的流量模式,所以相较于uniform 流量下,在更小的数据包注入率下网络接近饱和。在此两种流量模式下,数据包注入率较低时,两种路由器的数据包平均延时相差不大,当注入率不断提高,优先级可配置仲裁路由平均包延时性能明显优于普通轮询仲裁路由。

图10 两种流量模式下平均包延时

5 结束语

本文设计了一种仲裁优先级可配置且具有容错功能的NoC 路由器,实现了对路由器的各个模块RTL 设计。首先,提出了权重轮询仲裁方案,实现仲裁优先级可配置,将报文RHC 值以及输入端负载作为权重计算变量,优先响应负载量较大且报文RHC值较小的请求,有利于避免网络拥塞。其次,本文采用了一种容错功能的自适应路由算法,通过向相邻节点发送测试向量确定故障点并进行标记,绕开故障点完成数据传输。最后,给出了本文实验仿真结果,以及将本文路由方案与采用普通轮询仲裁的路由方案相比较,结果表明本文路由功能正常,拥塞缓解和容错功能具有明显优势,是应对大通信量数据传输的有益方案。