一种低延迟的无虚通道NoC容错路由算法

李 娇, 徐海鹏, 崇云锋, 刘 鹏, 冉 峰

(1.上海大学微电子研究与开发中心,上海200444;2.上海大学新型显示技术及应用集成教育部重点实验室,上海200444)

随着单个芯片上集成的处理器单元数目的增多,多处理器片上系统(multiple processor system-on-chip,MPSoC)的传统总线结构效率变低,因此需要一种新型的通信结构.鉴于此,片上网络(network on chip,NoC)应运而生.NoC技术具有可扩展性、可重用性、灵活性和平行度等优点,已成为多处理器片上系统互联问题的最佳解决方案[1-2].由于电路特征尺寸的不断减小,芯片受到串扰、耦合、制造工艺和电路老化等问题影响的可能性增大,更易产生瞬时故障或永久性故障,降低了NoC的可靠性[3].为了有效减小故障对NoC带来的影响,具有容错性能的NoC路由算法成为了研究的热点.

Zhang等[4]提出了一种可重构无虚通道容错路由算法(简称Zhang’s算法).该算法在无故障区域使用XY路由算法,同时为了避免绕过故障节点时发生死锁,根据转向模型禁止东北和北东两个转向.Zhang’s算法复杂度较低,但其每个节点需要获取8个方向上相邻节点的故障信息,且只能对一个故障节点容错.之后,姚磊等[5]对Zhang’s算法进行了扩展,提出基于内建自测试(build in self test,BIST)的容错路由算法.该算法利用BIST提供的故障信息,分别在x轴方向和y轴方向上优化绕行环(链)路上的数据包分布,缩短了数据包的路由距离.基于BIST的容错路由算法能够均衡故障区域周围的链路负载,降低网络的时延,提高网络吞吐量,但其仍只是对单故障区域进行容错.

Ebrahimi等[6]提出一种最短路径容错路由算法(简称Ebrahimi’s算法),该算法能够保持NoC在发生故障时的性能,但当位于对角线上的两个相邻节点发生故障时,存在数据包不能到达目的节点的情况,且NoC的可靠性也会随着故障节点的增多而降低.另外,为避免死锁,Ebrahimi’s算法使用了虚通道,使得NoC路由节点的复杂度上升.

为提高NoC的容错能力,提高网络传输效率,本工作主要提出了一种低延迟的无虚通道NoC容错路由算法.该算法利用旁路结构,缩短了多核间数据包传输时的路径,降低延迟时间,同时也能提高NoC的容错性能.通过NoC研究中常用的仿真器NIRGAM对算法进行仿真,验证了本算法的有效性.

1 NoC路由节点旁路结构

传统的路由节点内部包括输入缓存、路由计算单元、虚通道分配器、仲裁分配单元和交叉开关等[7].由于虚通道的使用会增加NoC路由节点的复杂度,增加芯片成本和功耗,因此本工作对传统的路由节点结构进行修改,去除了虚通道分配器,同时增加旁路结构.旁路结构能够在该路由节点发生故障时启用,保持了一定方向上的连接,避免因故障而增加路由算法的复杂度.路由节点旁路结构模型如图1所示.从图可知,旁路结构中4个输入输出通道处(东、西、南、北)共增加了4个多路复用器和多路选择器(虚线部分)以及旁路连线,其控制信号中的故障信号由故障检测模块生成.通过多路复用器、多路选择器和旁路连线,路由节点上的南、北输入通道分别直接连接北、南输出通道,东、西输入通道分别直接连接西、东输出通道.因此,当节点发生故障时,故障检测模块产生的故障信号选通旁路,使得数据包可以直接通过旁路传输到下一个路由节点.

将旁路结构运用于整个NoC时,对于NoC边界上的路由节点,由于边界处会缺失与某一方向相连的路由节点,因此对边界故障进行容错时,势必会存在转向限制性.为改变这一限制,修改边界上路由节点的旁路结构,改变路由节点输入、输出通道的连接,从而保持节点与其相邻节点的连接性.

(1)4个顶点.西北顶点路由节点为其东方向和南方向上输入输出通道的双向连接,东北顶点路由节点为其西方向和南方向上输入输出通道的双向连接,东南顶点路由节点为其西方向和北方向上输入输出通道的双向连接,西南顶点路由节点为其东方向和北方向上输入输出通道的双向连接.

图1 路由节点旁路结构模型Fig.1 Bypass structure model of router

(2)其他边界节点.对于西边界上的路由节点,因其没有西输入输出通道,则其南、北、东输入通道分别通过旁路连接到其北、东、南输出通道;对于北边界上的路由节点,因其没有北输入输出通道,则其西、东、南输入通道分别通过旁路连接到东、南、西输出通道;对于东边界上的路由节点,因其没有东输入输出通道,则其北、南、西输入通道分别通过旁路连接到南、西、北输出通道;对于南边界上的路由节点,因其没有南输入输出通道,则其东、西、北输入通道分别通过旁路连接到西、北、东输出通道.以3×3 Mesh NoC为例,修改后的NoC旁路结构如图2所示.由图可以看出,单向的通道连接会在边界节点上形成环路,为避免死锁,需要对部分转向进行限制.

图2 3×3 Mesh NoC的旁路连接Fig.2 Bypass connection of 3×3 Mesh NoC

2 无虚通道容错路由算法

2.1 转向模型

在NoC容错路由算法中,死锁是一个必须解决的问题.死锁是指数据包之间相互等待形成环形,使得数据包无法继续传输.在无虚通道的容错路由算法中,转向模型[8]是一种有效解决死锁的方案,在不需要添加虚通道的情况下,通过禁止部分转向避免死锁.文献[8]中给出了3种自适应的路由算法:西优先、北最后、逆向优先,这些算法的禁用转向如图3(a),(b)和(c)所示.本工作采用的转向模型根据后续的无虚通道容错路由算法,在数据包路由时,首先自适应地向西、北、南路由,然后才是东方向.即东方向是最后一个被传输的方向,该算法在数据包路由时禁止由东到南和由东到北的转向,从而避免产生环路形成死锁(见图3(d)).

图3 容错路由算法的禁用转向示意图Fig.3 Schematic diagram of forbidden turnings for fault-toleront routing algorithm

2.2 容错路由算法

为了计算数据包的合理输出端口,本算法中每个节点会有一个4 bit的寄存器fault表示4个相邻节点的故障信息.fault 0,fault 1,fault 2,fault-3分别表示东(E)、南(K)、西(W)、北(N)4个相邻节点的故障信息,数值为0时表示无故障,1则表示有故障.考虑到转向模型下数据包可存在多条传输路径,为了均衡传输的负载,增加1 bit的标识位 fl ag来决定数据的输出端口.在n×n Mesh NoC下,当前节点坐标为(XC,YC),目的节点坐标为(XD,YD),本算法描述如下.

(1)目的节点为当前节点(XC=XD,YC=YD)时,数据包转发到当前节点的知识产权(intellectual property,IP)核,即输出端口Out=L(本地).

(2)目的节点与当前节点位于同一轴(XC=XD或YC=YD)时,数据包转发到该轴靠近目的节点的下一节点.

(3)目的节点位于当前节点东南(XCYD)时,如果当前节点不在西边界(XC6=0),南相邻节点故障且其不位于南边界(fault 1=1,YC6=1)时,数据包的输出端口Out=W;其他情况下,Out=S.

(4)目的节点位于当前节点东北(XC

(5)目的节点位于当前节点西南(XC>XD,YC>YD)时,当南相邻节点故障且西相邻节点无故障(fault 1=1,fault 2=0),数据包的输出端口Out=W;当西相邻节点故障且南相邻节点无故障(fault 2=1,fault 1=0),数据包的输出端口Out=S;其他情况下,当标识位 flag=0时,输出端口Out=W,将标识位取反;当标识位 fl ag=1时,输出端口Out=S,将标识位取反.

(6)目的节点位于当前节点西北(XC>XD,YC

基于上述算法的描述可以看出:当目的节点位于当前节点东南或东北时,由于转向模型的限制,只存在一条固定的数据包传输路径;而当目的节点位于西南或西北时,算法可以采用多条路径,同时在节点中增加1 bit的标识位,避免数据包固定传输同一路径造成阻塞.这使得算法具有一定的自适应性,能够缓解热点的产生.

2.2.1 单故障节点

当NoC存在单个故障节点且故障节点不处于边界时,Zhang’s算法和本算法的原输路径如图4所示.由图可知,在单个故障存在情况下,按照Zhang’s算法,数据包分别从源节点4,6,2传输到目的节点6,1,6.由于故障节点的存在,故障节点以及相连的链路都无法使用,数据包需要在故障节点周围进行绕行才能到达目的节点;而基于本算法,在相同源节点和目的节点的情况下,由于故障节点的旁路被选通,数据包利用旁路结构能够通过故障节点,有效降低数据包的传输距离.本算法最大能优化数据包绕行减少3跳,即源节点和目的节点位于同一列或同一行的情况.当故障节点位于边界时,根据本算法的旁路规则,会产生边界故障,如图5所示.由图可以看出,当前节点与目的节点分别位于节点1与节点5时,由于转向模型的限制,数据包无法通过虚线所示路径传输到目的节点.

图4 两种不同容错路由算法的传输路径Fig.4 Transmission path of two different fault-toleront routing algorithms

图5 边界故障Fig.5 Boundary fault

为了解决图5所示的边界故障问题,提高NoC的容错性和可靠度,本算法允许故障边界节点相连的节点部分180◦转向,以便有效解决边界节点发生故障时数据包的传输限制.禁用的180◦转向如图6所示,其中边界故障的旁路连接可以类似表示为单向传输环路(单向实线箭头构成部分).对于西边界故障形成的单向传输环,允许其北相连节点(节点1)进行由南到南的转向,东相连节点(节点2)进行由西到西的转向,禁止其南相连节点(节点3)进行由北到北的转向;对于北边界故障而言,允许其西相连节点(节点4)进行由东到东的转向,南相连节点(节点5)进行由北到北的转向,禁止其东相连节点(节点6)进行由西到西的转向;对于东边界故障而言,允许其西相连节点(节点7)进行由东到东的转向,北相连节点(节点8)进行由南到南的转向,禁止其南相连节点(节点9)进行由北到北的转向;对于南边界故障而言,允许其西相连节点(节点10)进行由东到东的转向,北相连节点(节点11)进行由南到南的转向,禁止其东相连节点(节点12)进行由西到西的转向.

图 6 禁用的180◦转向(虚线)Fig.6 Forbidden 180◦turnings(dotted line)

因此,对于图5所示的边界故障,数据包可以先传输到节点7,进行180◦转向,然后通过故障节点4的旁路到达目的节点5.通过允许180◦转向,边界上的数据包可以不受转向模型的限制,正常地传输到相应的目的节点,且面对多故障节点情况时数据包也能够利用这些转向更有效的传输.

2.2.2 多故障节点

对于多故障情况,Zhang’s等[4]提出了将多个故障节点与一些无故障节点扩展成一个故障区域的设想,但因故障区域中的无故障节点被视为故障节点,无法进行数据的传输接收,降低了NoC的可靠性.图7所示为一对斜对角故障节点的情况.如果当前节点C与目的节点D位于图中位置时,此时目的节点位于当前节点的西南方.故障节点与节点C,D形成了一个故障区域(虚线框).按照Zhang’s算法,故障区域内的节点C和D被视为故障节点,无法进行传输与接收数据.而对于本算法,数据包可以通过故障节点的旁路传输到目的节点,且由于算法的自适应性,数据包可以通过两条路径(实线)进行传输.

图7 多故障节点下容错路由算法的传输路径Fig.7 Transmission path for fault-toleront routing algorithm with multiple faults

3 算法无死锁证明

本算法采用的转向模型是无死锁的,由于在边界故障节点上允许部分180◦转向,因此需证明在边界上允许180◦转向,算法仍无死锁.利用Dally等[9]提出的通道依赖图(channel dependency graph,CDG)的方法,即当网络对应的CDG无环路时,算法在该网络中无死锁.

根据Dally的方法,西边界故障时的网络连接如图8所示.由于本算法采用的转向模型禁止东南转向和东北转向,即不存在X56到X64的转向和X12到X24的转向.由于Z54到Y42以及Z54到Y46中也存在东南转向和东北转向,因此也不存在这两种转向.同时,为解决边界故障的问题,增加Y15到Y54的转向和Z54到Z41的转向,禁止Z41到Y15的转向.由采用本算法后网络对应的CDG可以看出,CDG中没有形成环路,即本算法是无死锁的.对于其他边界故障的情形,也可以类似证明.

图8 西边界故障的网络连接Fig.8 Network links in west boundary fault

4 仿真分析

采用NIRGAM仿真器[10]对本算法的性能进行仿真验证,并与Zhang’s算法和Ebrahimi’s算法进行比较.NIRGAM是一种基于System C的NoC专用仿真器,具有代码开源、扩展性好等特点.仿真器的主要参数配置如表1所示.

表1 仿真器的参数配置Table 1 Configuration of simulator parameters

为了体现本算法的性能,分别在单故障与多故障情况下进行仿真,比较Zhang’s算法、Ebrahimi’s算法和本算法的平均延迟.在单个故障的情况下,Zhang’s算法、Ebrahimi’s算法和本算法的数据包平均延迟曲线如图9所示.可以看出,在通信负载较低时,3种算法的平均延迟基本一致,但随着通信负载的不断增加,Zhang’s算法和Ebrahimi’s算法的平均延迟分别在通信负载20%和30%时迅速提升,而本算法的平均延迟则缓慢升高,在通信负载为40%后才大幅度升高.在通信负载为30%时,本算法的平均延迟相比于Zhang’s算法改善20.2%,相比于Ebrahimi’s算法改善4.35%.这是由于Zhang’s算法存在较长的绕行路径,在通信负载较高时延迟较大的问题显现出来;而Ebrahimi’s算法虽为最短路径,一定程度上降低了延迟,但由于采用了虚通道,当通信负载较高时会出现负载不平衡的情况,产生阻碍数据包传输的的热点,进而增加了延迟.本算法虽也存在绕行,但相比于Zhang’s算法,绕行距离要短.此外,本算法具有部分自适应性,能够有效避免热点的产生.

图9 单故障下3种不同容错路由算法的平均延迟Fig.9 Average latency of three different fault-toleront routing algorithms with single fault

在多故障的情况下,由于Zhang’s算法的性能并不高,因此仅比较Ebrahimi’s算法和本算法.图10为多个故障情况下两种算法的平均延迟曲线.可以看出,与单故障类似,本算法仍具有较低的平均延迟,且随着故障节点数目的增多,平均延迟均会有所增加.

图10 多故障下两种不同容错路由算法的平均延迟Fig.10 Average latency of two different fault-toleront routing algorithms with multiple faults

5 结束语

本工作提出了一种低延迟的无虚通道容错路由算法,通过旁路结构,保持了故障节点在部分方向上与相邻节点的连接,进而减少了数据包的传输延迟,同时对边界旁路结构加以改进,解决了算法在使用转向模型时边界节点故障时的路由限制.仿真分析的结果表明,本工作提出的算法能够有效降低数据包的平均延迟,且在多故障下仍能保持良好的性能.