基于二进制退避算法和流量感知的片上网络在线故障检测

崔艳 王刘涛

摘 要： 针对片上网络（NoC）中互连线容易发生串扰故障问题，提出了一种基于二进制退避算法（BEBOA）结合流量感知的NoC串扰在线诊断故障方案。当NoC信道空闲时，使用信道检测器检测信道以最小化NoC入侵吞吐量；当临时故障恢复时，使用基于BEBOA的检测间隔时间参数动态设定检测时间，使网络快速恢复。此外，构建一种优先级仲裁机制，避免应用程序和检测程序发生信道访问冲突。实验结果表明，提出的方案能够准确检测和诊断故障，并能够迅速恢复吞吐量，同时具有最小的额外芯片面积开销需求。

关键词： 故障检测； 片上网络； 二进制退避算法； 互连线串扰； 监控模块； 优先级仲裁机制

中图分类号： TN711?34； TP399 文献标识码： A 文章编号： 1004?373X（2016）05?0014?05

片上网络（Networks?on?Chip，NoC）[1]是一种用于复杂片上系统（System?on?Chip，SoC）的可扩充且有效的通信架构，片上网络越来越高的复杂性导致出现多种互连问题[2]。为了保证现代NoC能适应故障且正常运行，需要开发一种能在互连结构中进行自我检测和自我维修的容错策略[3]。

由于NoC网络中存在大量互连结构，传统测试机制不能有效诊断和定位故障。因此，本文提出一种利用监控模块（Monitoring Module，MM）在线检测和诊断NoC互连线串扰故障，并以并行方法运行，最小化NoC入侵吞吐量。

1 NoC故障模型

NoC中常见的故障为逻辑层的门级故障、桥接故障和串扰故障[4]，本文主要针对串扰故障进行研究。

在NoC互连中，串扰故障通常由空间相近的两条逻辑信道线路的信号相互影响而形成。本文使用最大激励串扰故障（Maximal Aggressor Fault，MAF）[5]模型描述导致串扰故障的所有原因。在MAF模型中，线路受相邻线路传输数据信号的干扰而形成串扰故障，如图1所示MAF模型形成的6种串扰方式，分别为正/负脉冲、上升/下降延迟、上升/下降加速。

图1表明检测器需给每条线路发送2个测试向量来形成各种可能干扰，因此需要12种测试向量来检测6种可能干扰。MAF模型对于一种[N]位信道，设定第4 b作为受干扰线路，测试向量[（v1，v2，…，v8）]依次发送特定测试向量，用于检测6种可能串扰故障，如图2所示。

2 提出的串扰故障检测方案

本文利用CCD组件[6]的监控模块来增强路由器检测故障的能力，监控模块通过隔离测试过程的流量和执行常规应用程序流量来管理NoC测试过程的入侵流量，使用基于二进制退避算法（Binary Exponential Back?off Algorithm，BEBOA）[7]的检测间隔时间参数动态设定检测时间，使网络快速恢复。

图3所示为监控模块与路由器中其他组件的连接结构。对一种n b数据包，最重要的4 b定义为头，目标地址占16 b，其余bit为有效负荷。以“（002025A5A）16”为例，则头字段为（0）16，目标地址为（0202）16，有效负荷为（5A5A）16。仅使用1 b的MSB表示数据包类型，若头字段的MSB为1，则该数据包为测试数据包，否则为常规应用程序数据包。

图4为两个路由器通过East端口和West端口相互连接的例子。监控模块（MM）有4个子组件，信道拥堵检测器（CDD）、信道检测器（CT）、流量传感器模块（TSM）和测试间隔时间决策模块（TID），下面详细介绍这些模块。

2.1 信道拥堵检测器

本文使用信道拥堵检测器（Channel Congestion Detector，CCD）[8]检测信道的当前流量状态，为流量传感器模块提供信道拥堵信息。流量状态分类为：信道不拥堵、信道繁忙和信道拥堵。该方法能有效地做出路由决策，选择轻拥堵路由，提高信道吞吐量。

2.2 流量传感器模块

由于故障检测应用程序和常规应用程序共享使用信道，所以流量传感器模块（TSM）定义了一种优先级仲裁方案，以避免冲突。TSM通过每个信道局部CCD提供的繁忙/拥堵/故障信号来获得端口状态，以此做出仲裁。共享信道的优先级定义如图5所示。

当信道处于无故障状态时，常规应用程序能随时通过无故障信道传输数据，因此常规应用程序（[pregular]）的优先级高于故障检测应用程序（[ptest]）优先级，即[pregular>ptest。]常规应用程序完成数据传输后，信道变为空闲状态时，则[pregular

如果信道发生故障，故障检测应用程序将重复检测信道且限制常规应用程序传输数据，即[pregular

如果信道处于诊断状态，传统检测周期被定义为诊断周期。此时，信道限制常规应用程序流量传输数据，所以故障检测优先级高于常规应用程序优先级，即[pregularptest]。如果信道在诊断阶段通过所有检测，则设定信道无故障且信道的状态变为无故障状态。

2.3 信道检测器

信道检测器（Channel Detector，CT）[9]负责检测信道，若信道出现故障，CT将给其他模块发出警告标志。根据警告标志，自适应仲裁机制随后做出路由决策。CT由两个主要子模块组成：检测向量生成器和检测响应分析器。

若故障检测的优先级高于常规应用程序优先级且检测时间间隔等于0，则只进行信道故障检测过程。CT能检测每个信道中多种类型的故障，如果线路#1发生故障，CT单元将检测线路#2到线路n，直到检测到故障线路。对一个n b信道，受干扰线路的范围为从1～n-1。对每个受干扰线路，测试向量生成器顺序发送测试向量[（v1，v2，…，v8）]来诊断线路是否为6种串扰故障[{sf，sr，gn，…，gp}]中的一种。接收端的检测响应分析器生成标准检测向量，用于与接收到的检测向量作比较。如果它们不匹配，则该线路存在串扰故障且生成故障标签。检测向量生成器需要9个时钟周期检测一条线路，其中1个时钟周期用于发送初始数据包（表明需检测线路位置），8个时钟周期用于发送检测向量。因此，它需要总共9[×]（n-1）个时钟周期检测完n b信道。

信道检测器模块中生成检测向量的流程图，如图6所示。在每次检测的开始，CT读取来自TID的检测间隔时间并启动计数器。当计数器值等于检测间隔时间值时，CT初始化一个新的检测过程，且顺序发送检测向量[（v1，v2，…，v8）]。CT完成检测后，TID模块增加间隔时间，这是因为如果信道已经成功通过先前检测，则没有必要持续检测信道。间隔时间参数可以控制故障检测过程占有信道的平均时间。

3 实验结果与分析

3.1 实验平台

构建测试平台，使用VHDL实现NoC路由器和信道中的监控模块，路由器的吞吐量可用来分析故障检测应用程序对常规应用程序产生的影响。本文开发了基于SystemC的数据包生成器和计数器平台[10]来测量常规应用程序的吞吐量。数据包生成器根据图3描述的常规数据包结构生成数据，数据包计数器测量输出数据包率，用来推导路由器吞吐量和未成功发送的数据包数量。

图8为实现监控模块各种功能的3×3的NoC路由器平台。监控模块能处理NoC在实际中遇到的不同场景情况。基于XY路由选择算法，路由器[2，3]的Western输入信道在特定时间周期内是空闲的，但是Eastern信道总是拥堵的，如图9所示。根据这些信道的实时吞吐量来分析常规应用程序的入侵流量。

仿真实验中，设置数据包大小为36 b，系统频率为100 MHz。不同数据包发送率能产生不同流量，这些不同流量可以用来分析监控模块性能（特别是入侵流量分析）。通过故障分发器给一些信道分配串扰故障，引起一些永久故障（PF）或暂时故障（TF）。另外，本文使用基于SADE 90 nm CMOS的集成电路设计编译工具获取监控模块的面积开销（检测单元占路由器整体面积的百分比）。

3.2 实验结果

图10为不同故障情况（永久性故障、暂时故障）和不同[β]值的TID模型下的信道吞吐量，分析监控模块行为对平均常规应用程序吞吐量产生的影响。

如果信道无故障，则对常规应用程序吞吐量而言，故障检测流量不为入侵流量。图10（a）和图10（b）中，检测周期0～3之间，信道无故障且常规应用程序能在任何时间传输数据，因此[pregular>ptest，]信道吞吐量保持最大值（即3.6 Gb/s）。另一方面，当给信道引入故障时，第4个检测周期检测到了故障，故障检测过程将继续检测该信道。因此，常规应用程序不能通过该信道传输数据，其吞吐量为0。对于暂时故障，故障从第7个周期开始恢复，如图10（a）所示，在此诊断期间，常规应用程序在检测间隔时间内仍能传输数据。在监控模块诊断信道为无故障后，随着检测间隔时间呈指数增长，常规应用程序占有信道时间加长，信道吞吐量逐渐恢复。对永久性故障，故障检测过程总能检测到故障，因此常规应用程序吞吐量总是为0。

图10 发生故障时的信道吞吐量

另外，从图10（a）能清楚地看到，TID模型中检测过程的恢复速度依赖于[β]值（后退程度）。例如，如果[β=2，]则第一次检测过程的[Ncount（1）=2]。如果没有检测到故障，则第二次检测过程的[Ncount（2）=4]。[Ncount（n）]的变化趋势依赖于[β。][β]值越大，检测间隔时间[Ncount（n）-Ncount（n-1）]越大。在诊断阶段，常规应用程序在两次检测之间可以传输数据，因此[β]值越大，则吞吐量恢复速度越快。但如果[β]值太大，在故障检测阶段又出现故障时，模型的反应能力会下降。

在两种常见的通信模式下（均匀随机、位补码）评估各种算法随着网络中故障链路数目的增加对网络吞吐率的影响。故障条件设为无故障，5%链路故障和15%链路故障三种情况，另外，故障链路中设置一半为永久故障，一半为暂时故障。网络吞吐率为网络的最大通信量，单位为packet·（cycle·node）-1。4种算法的吞吐量比较，如表1所示。

从表1可以看出，本文方案的故障情况对网络吞吐量的影响最小。因为本文方案有效地检测故障，快速回复暂时故障的吞吐量，另外，检测模块所需的流量较小，并采用仲裁机制避免冲突，大大提高了检测和数据传输的效率。

以使用4个监控模块的路由器为例，每个信道有1个监控模块。路由器拥有32 928个逻辑门，假设其中11.56%（3 808个）的逻辑门有4个监控模块。各个算法的硬件面积开销如表2所示，可以看出，本文方案的硬件面积开销最小，约为12%，具有良好的可扩展性。

4 结 语

本文提出了一种针对NoC互连的流量感知串扰故障自适应在线检测和诊断方案，使用TSM组件监控信道流量，使用后退算法和优先级定义构建一种信道访问仲裁机制，避免了应用程序和检测程序发生访问冲突。此外，还提出了快速故障恢复策略，故障消除后，能够使常规应用程序吞吐量快速恢复到最大值。在不同信道故障情况下评估本文方案性能，实验结果表明，本文方案能够在线准确诊断故障，在故障情况下能获得最大吞吐量，且需要的额外面积开销也较小。

检测时间间隔参数[β]的值影响着检测效率和吞吐量恢复速度，如何确定合适的[β]值非常重要。因此，在未来工作中，将进一步研究故障优化恢复决策。

参考文献

[1] 王谛，赵天磊，唐遇星，等.一种面向通信特征的3D NoC体系结构设计[J].计算机研究与发展，2014，51（9）：1971?1979.

[2] DALL′OSSO M， BICCARI G， GIOVANNINI L， et al. A latency insensitive parameterized network?on?chip architecture for multi?processor SoCs [C]// Proceedings of 2012 30th IEEE International Conference on Computer Design. [S.l.]： IEEE， 2012： 45?48.

[3] 胡婧瑾.基于环形拓扑的片上网络架构设计与性能评估研究[D].杭州：浙江大学，2013.

[4] CARRILLO S， HARKIN J， MCDAID L， et al. Advancing interconnect density for spiking neural network hardware implementations using traffic?aware adaptive network?on?chip routers [J]. Neural networks， 2012， 33（4）： 42?57.

[5] LIU J， HARKIN J， LI Y， et al. Online fault detection for networks?on?chip interconnect [C]// Proceedings of 2014 NASA/ESA Conference on Adaptive Hardware and Systems. [S.l.]： IEEE， 2014： 31?38.

[6] 张士鉴，韩国栋，沈剑良，等.基于故障链路缓存再利用的NoC容错路由算法[J].计算机辅助设计与图形学学报，2014，26（1）：131?137.

[7] TAMRAKAR D， BHATTACHARYA S， JAIN S. A scheme to eliminate redundant rebroadcast and reduce transmission delay using binary exponential algorithm in Ad?Hoc wireless networks [J]. International journal of scientific research in network security and communication， 2014， 31（2）： 1?5.

[8] 欧阳一鸣，张一栋，梁华国，等.基于虚通道故障粒度划分的 3D NoC 容错路由器设计[J].计算机研究与发展，2014，51（9）：1993?2002.

[9] GRECU C， IVANOV A， SALEH R， et al. Testing network?on?chip communication fabrics [J]. IEEE transactions on compute?raided design of integrated circuits and systems， 2007， 26（12）： 2201?2214.

[10] HERVE M， ALMEIDA P， KASTENSMIDT F L， et al. Concurrent test of network?on?chip interconnects and routers [C]// 2010 11th Latin American of Test Workshop. Pule del Este： IEEE， 2010： 1?6.