基于维序路由的片上网络容错机制设计

王春华, 孙 琦, 朱新宇, 张多利, 宋宇鲲

(合肥工业大学 电子科学与应用物理学院,安徽 合肥 230601)

近年来,随着集成电路设计技术的飞跃发展,单个芯片内部可能集成了几百甚至上千个处理器核和通信部件,传统的基于总线的片上系统(system-on-chip,SoC),已经不能高效地处理处理器核心之间快速的数据资源交换。片上网络(network-on-chip,NoC)由于其集成度高、扩展性强、高并行度的通信能力和功耗低等优势,已经逐渐取代总线成为新的片上通信的标准。

但是随着集成电路工艺进入纳米时代,更小的特征尺寸、更低的工作电压以及不断提升的工作频率,导致片上网络很容易受到故障的影响而破坏网络中传输的数据。尤其是在大气层外,电子设备暴露在有大量宇宙射线的强辐射环境中,这些宇宙射线由电子、质子、α粒子等高能带电粒子构成,穿透能力强,易对电子元器件产生诸多危害。一旦高能粒子轰击集成电路,会引发永久效应或瞬时效应。高可靠性已成为片上网络系统发展的重要方向[1]。研究结果表明,计算机系统中80%～90%的失效都是由瞬时故障引起的[2]。

基于此,本文提出了一种针对数据瞬时故障的传输机制,即基于维序路由的NoC容错方案。该方案通过双链路发送数据配合路由容错算法提高整个NoC的容错能力,以达到减少延时和提高吞吐的目的。

1 相关研究

为了解决数据传输中的瞬时故障问题,国内外研究者提出了许多具有容错性能的NoC传输机制方案[3-5],主要分为基于检错纠错码的请求重传机制[6]和基于随机通信的路由算法2类[7]。针对NoC的瞬时故障,文献[8]提出了一种基于XYX路由的方法,有效地提高了网络的容错能力;文献[9]提出了一种低延时的可靠传输算法,利用发送端主动重传分组技术以及端到端的反馈技术,有效地降低了数据重传过程的平均延时;文献[10]提出了一种混合容错方案,该方案通过自适应编码来调节各路由器之间的容错能力。随机通信算法是路由节点以一定的概率向相邻节点以广播的形式发送数据包,直到目的节点收到数据包,目的节点从它相邻的节点得到数据包的多个备份,从中选取一份正确的数据包[11]。文献[12]提出了一种直接扩散与冗余随机走动算法,改善了随机扩散目的端被忽略的缺点。但对于扩散算法,不论哪种算法,都需要在网络中传输大量的冗余包,从而造成很大的开销。

2 基于维序路由的容错设计

2.1 设计思想

基于维序路由的容错设计是一种多径路由的容错算法,以2条路径进行数据传输配合奇偶校验码,利用双模数据自检容错,对瞬时故障进行屏蔽。

瞬时故障的产生具有随机性和偶然性,可能出现在NoC的控制信号或者传输数据中,对控制信号采用三模冗余可以很好地屏蔽瞬时故障的干扰。而对于传输数据,无论空间三模冗余或时间三模冗余,对NoC的资源消耗都十分巨大[13]。双模冗余自校验方案相对于传统的三模冗余既不会增加太多资源,又可以实现容错目的,是当前研究的一个重要方向。

奇偶校验码是一种简单有效的校验码,它在源端记录数据包中0的个数是奇数还是偶数,在目的端再检测0的个数是奇数还是偶数,仅需要1位即可检验出数据在传输过程中是否出现错误。奇偶校验码检错性能好、消耗资源少,是一种优质的检错方案,但劣势在于无法检验出偶数个错误,因此可以将双模冗余和奇偶校验结合起来,完成对瞬时故障的屏蔽。

2.2 故障模型与容错机制

瞬时故障引起的单粒子效应一般表现为单粒子翻转(single event upset,SEU)和单粒子瞬态(single event transient,SET),在集成电路中主要为SEU错误。在近地轨道电子设备中每天1 bit产生SEU的概率[9]为10-7。本文研究的目标多核系统1次任务的传输量约为106bit。结合瞬时故障产生的概率,假设在1次数据传输过程中,同一个数据包中瞬时故障至多发生1次,因此可以采用基于维序路由的容错设计。

对于NoC中的控制信号,均采用三模冗余表决进行容错,对于传输数据的容错采用双模冗余自校验的方式进行容错,双模冗余自检容错。双模冗余自检容错电路如图1所示。

图1 双模冗余自检容错电路

双模容错真值见表1所列,OUT的初始状态为0,单条路径奇偶校验结果分别为IN0和IN1。若单条路径校验结果正确,则记为0；若校验结果错误,则记为1。由表1可知,当1条链路中出现了SEU错误,不影响OUT的正常输出；当2条链路同时出现SEU错误,OUT输出值为1,此时向源节点和目标节点均反馈重传信号,进行整体重传,实现对单粒子错误进行屏蔽。

表1 双模容错真值

2.3 路由器结构

本文以二维网格结构来探讨容错方案的设计,为了实现双路径传输,在传统的单端口路由器结构下,添加一个本地端口,在源节点进行数据传输时,可以通过双端口将双路径数据同时送入NoC中。数据网络的网络节点结构如图2所示。由图2所知,每个路由节点包括编码器、输入控制器、优先级编码器、路由器、仲裁器、交叉开关、输出控制器、缓存器、解码器。

图2 数据网络的网络节点结构

基于维序路由的容错方案只在源节点的本地端口进行编码,在目的节点端口进行解码,网络节点的工作流程如下。

(1) 发送端。源节点的运算核心将准备好的运算包,通过本地节点0和本地节点1送入到网络节点的路由器中,经过端口编码,送入节点的路由器中进行传输。双路数据路由中传输协议一致,以发送头包的形式先建立链路,头包中采用三模冗余的方案对目标网络节点进行冗余表决,解析出正确的目的节点坐标；优先级编码器对各端口的请求优先级进行排序；路由器对优先级高的目的节点分配端口；仲裁器根据路由结果对链路通道进行仲裁,若处于空闲状态,则分配通道交予当前请求,若通道处于占用状态,则反馈拒绝信号,链路建立失败。交叉开关根据交叉开关将所允许的通道打开,头包发送至下一个路由节点。

需要注意的是,对于本地节点0输入的数据,采用XY路由规则进行传输,对于本地节点1输入的数据采用YX路由规则进行传输,保证数据链路不会互相占用。

(2) 目的端。头包经历中间路由节点后发送至目的节点,目的节点反馈成功信号将沿途的各网络节点进行锁定,源节点接收到反馈信号后发送数据包和尾包,经过编码后由输入控制器传输至数据网络,到达目的节点后目的节点的缓存器将传输数据进行缓存,缓存大小与网络规模有关。在解码器中,对数据的解码结果进行对比,对单粒子错误屏蔽,对多粒子错误反馈重传信号,重新发送当前事物。

解码器中奇偶校验的结果记为奇偶校验值value,通过比较各自链路的value来判断数据的正确与否。当校验值value为0时,数据正确；当value为1时,数据错误。若双链路中的数据奇偶校验值value均为0,说明双链路的数据均正确,则正确的数据会发送至目的端本地接口0和本地接口1中;若双链路数据的校验值value为01(10),说明一条链路发生瞬时故障,选取另一条校验值value为0的数据,发送至目的端本地接口0和本地接口1中,屏蔽瞬时故障的影响;若双链路数据的value均为1,说明双链路的数据均发生瞬时故障,则解码器中反馈重传信号给源节点与目的节点,同时将缓存器中数据清空,进行整体重传。

2.4 路由算法

本文的NoC拓扑结构采用2D Mesh结构,可以很好地避免死锁,同时扩展性也很高。路由算法采用维序路由确定性路由算法,从源端到目的端采用双链路发送数据,路由算法采用双路径发送数据,对于数据的传输,按照源节点和目的节点传输示意图进行传输,具体如图3所示。

在2D-Mesh结构中存在图3a所示的源节点与目的节点的相对位置,对于该相对位置,本文提出的容错机制采用一条链路沿XY路由方向发送数据,另一条链路沿YX路由方向发送数据,可以同时到达目的节点。对于图3b所示的节点相对位置,采用一条链路沿XY方向发送数据,另一条链路先传播到相邻节点,再沿XY方向发送数据,最后传播到目的节点。

图3 源端和目的端传输示意图

由于数据包经过数量不同的路由节点,为了保证数据能够同时到达目的端,在目的端接口增加缓存器对数据进行缓存。

实际的网络中会出现拥堵情况。若2条链路均处于拥堵状态,则反馈失败信号,等待再次传输；若一条链路建立成功,另一条链路遇到拥堵,则成功的链路反馈信号在缓存器中等待16个周期,若没有等到另一条链路信号,则反馈失败信号,等待再次传输；若2条链路建立成功,则反馈成功信号,锁定链路,进行数据传输。

对于图3b所示的边界情况条件,有4种边界传输情况,如图4所示。

图4 边界传输情况

对于边界条件下的路由转向,应该区分出来进行研究。

对于边界条件下的源节点和目的节点的数据传输,要采用改进的算法进行传输。

算法基本思想为:头包进入路由器后,路由模块对数据头包进行解析,提取出目的节点与源节点坐标；利用标示位区分由本地节点0/1进入网络的数据,通过源节点与目的节点的坐标是否相同来区分是否存在同轴的情况,从而根据目的节点与源节点的相对位置,确定固定的传输路径。

具体流程如下:从源节点到目的节点,若头包标示位为0,则按照XY路由传输规则进行传输,按图4中实线路由方向;若头包标示位为1,则按照虚线路由方向进行传输。若同X轴,从源节点发出的路由头包进行轮转选取输出端口,优先方向为南北,微片沿X轴传递到目的节点同维度的X轴上,数据包再进入目的节点;若同Y轴,头包微片轮转优先方向为西东,数据沿Y轴传递到目的节点同维度的Y轴上，再进入目标节点,通过本地端口发送双模数据进入数据层网络。

对于非边界条件下的源节点和目的节点的数据传输,在目的节点和源节点存在XY路径与YX路径2条数据传输路径的前提下,标示位为0,沿XY路径进行传输,标示位为1,沿YX路径进行传输。

路由算法描述如下,其中边界条件设置为4,可以根据网络规模进行调整。

if(!sign&&DestX>LocalX‖

sign&& DestY=LocalY&&DestX>LocalX‖

sign&&DestY=IntY&&DestX>LocalX

&&!request[east] ‖

sign&&DestX=IntX!=’d4&&IntY=LocalY&&!request[east]

)

dest[east]=1;

if(!sign&&DestX

sign&& DestY=LocalY&&DestX

sign&&DestY=IntY&&

DestX

sign&&DestX=IntX&&IntY=LocalY&&!

request[west]

)

dest[west]=1;

if(!sign&&DestX=LocalX&& DestY>LocalY‖

sign&& DestY>LocalY‖

sign&&DestX=IntX&& DestY>LocalY&& !request[south]‖

sign&&DestY=IntY!=’d4&& IntX=LocalX&& !request[south]

)

dest[south]=1;

if(!sign&&DestX=LocalX&&

DetsY

sign&& DestY

sign&&DestX=IntX&&DestY

&& !request[north]‖

sign&&DestY=IntY&&IntX=LocalX

&& !request[north]

)

dest[south]=1;

3 实验结果与分析

由于瞬时故障的随机性和偶然性,对上述设计进行NoC仿真实验,对比本文方案与传统的端到端检错重传方案。传统端到端设计采用汉明码编解码,对瞬时故障也具有纠一检二的功能,主要讨论基于维序路由的容错算法在容错性能、网络性能和面积开销3个方面的可靠性效果。

3.1 容错性能

基于维序路由的检错重传机制采用对传输协议控制信号三模冗余容错,对传输的数据包采用双模自校验的方法来实现容错,屏蔽单粒子错误,由于多粒子翻转故障出现概率极低(约为0),因此基于维序路由的检错重传的容错性能约为100%。传统的端到端检错重传对传输数据进行保护,缺乏对控制信号的保护,因此在容错性能上略逊于基于维序路由的设计。

3.2 网络性能

在NoC中,评价其性能主要有延迟和吞吐2类,因为瞬时错误的概率太小,并且具有随机性和偶然性,所以在实验仿真时要模拟故障注入。

设一个数据包为1 000个微片,每个微片大小为66 bit,设置注入率每个周期每个节点为1微片,因此故障注入率每个周期每个节点为10-6～10-1。

首先验证高故障注入率10-2的情况下多个任务对系统传输数据平均延迟的影响,结果如图5a所示,记录了在高故障率10-2和多个任务数的情况下,从源节点到目的节点数据包到达目的节点所需要的平均延迟。由图5a可知,在低任务数下,维序容错路由与端到端容错路由的平均延迟周期差距不大,这是由于任务数少、瞬时故障概率出现低的原因;但随着任务数的不断增加,瞬时故障产生增多,端到端平均延迟增大,同时由于任务数增多,导致维序路由可用链路减少,延迟升高,但从总体延迟性能来看，维序路由的设计优于端对端容错路由设计。

同一个任务在不同的故障注入率情况下,2种算法从源节点到目的节点的平均延迟如图5b所示。由图5b可知,随着故障率的不断提高,端到端容错易受到瞬时故障的影响,而维序路由算法则更加稳定;当故障注入率达到10-1时,基于维序路由检错重传的平均延迟比端到端检错重传延迟低近40%。在故障不断注入的情况下,基于维序路由检错重传依然能保持较低的传输延迟。可见,基于维序路由的算法明显优于端到端检错重传。

图5 平均延迟比较

不同故障率的注入会引发网络中吞吐量的变化,而吞吐量的大小可以直观地说明各个网络节点进入微片的平均数量。故障注入率与吞吐量的关系如图6所示。

图6 故障注入率与吞吐量的关系

由于维序路由具有双端口,微片可以从本地节点0与本地节点1同时进入到数据网络中,这虽然增加了一部分功耗,但是相比于端到端的路由算法,吞吐量有了一定的增长。从图6可以看出,在低故障率注入的情况下,2种容错算法的平均吞吐量相差不大,但随着故障率不断上升,端到端检错重传算法的劣势越来越明显,平均吞吐量开始下降,而基于维序路由的检错重传,在高故障率注入的情况下,吞吐量的变化依然不是很明显,容错效果很好;当故障注入率达到10-1时,基于维序路由检错重传的平均吞吐量比端到端检错重传高约33%。由此可见,本文基于维序路由的容错重传算法在吞吐量上明显优于端到端路由容错重传算法。

3.3 硬件开销

实验采用Xilinx公司的软件Vivado2016.3对本文提出的结构进行设计,采用Verilog语言分别对单端口路由结构、端到端容错重传和基于维序路由的容错方案进行建模。各方案硬件开销见表2所列。

表2 硬件开销对比

本文方案采用双端口设计,在硬件开销上增加了端口设计以及缓存单元,因此消耗资源增加。端到端容错方案数据采用汉明码编码,在路由中增加了复杂的编码和解码模块,导致资源消耗增加。两者相比,基于维序路由的容错方案对硬件的消耗略小,容错性能优于端到端容错重传。

4 结 论

本文设计了一种基于维序路由的容错重传方案,在2D Mesh结构下通过双链路发送数据,将数据从源端发送到目的端,并通过奇偶校验码双路径自检对瞬时故障进行屏蔽；在保证容错性能的同时,达到了延迟和吞吐量的优化。通过NoC仿真实验,在8×8的网络模型下,对容错机制进行了验证,多组实验结果表明,基于维序路由的容错重传方案具有良好的容错性能；在故障注入率为10-1时,传输延迟相对于端到端容错重传降低了约40%,同时吞吐量提高了约33%,完成了高可靠性的传输。