文献标识码： A
DOI：10.16157/j.issn.0258-7998.2017.03.008
中文引用格式： 杭彦希，徐金甫，陈松涛，等. 面向片上网络路由器FIFO故障的实时容错设计[J].电子技术应用，2017，43(3)：36-39.
英文引用格式： Hang Yanxi，Xu Jinfu，Chen Songtao，et al. Design of fault-tolerant router for online FIFO fault detection on network-on-chip[J].Application of Electronic Technique，2017，43(3)：36-39.
0 引言
目前对路由器故障的检测与容忍研究是片上网络相关研究的一个重要方面。其解决办法主要有以下两类：(1)通过容错路由算法绕开故障节点，如文献[1]和文献[2]。但是这些方法容错粒度较大，一旦发现故障节点就选择绕开或者丢弃，极大地浪费了片上缓存等资源；(2)通过修改路由器微结构进行容错，如文献[3]和文献[5]，但是根据文献[4]，在FIFO深度为32的路由器中，FIFO占用了94%以上的面积，发生故障的概率也最大，文献[3]未对FIFO提出容错方案，这显然对于设计容错路由器是不够的。文献[5]的检错粒度大，且其采用的故障通道隔离技术浪费了片上一些仍然可用的资源。文献[4]提出了一种可靠的容错路由器架构Vicis，但是文中提出的故障诊断是线下的，降低了路由器的工作效率。文献[6]提出了一种在线的FIFO硬故障检查方法，能够在线对FIFO故障进行检测，但是故障覆盖率不高，也未对最关键的FIFO控制部分进行故障检测，而且在对故障检测后也未提出合适的容错方案。
综合以上研究，本文针对于片上网络FIFO提出了一种故障实时容忍设计方案，首先针对于片上网络FIFO中易发生的故障建立故障模型；然后提出一种针对于片上网络路由器FIFO的实时故障检测算法，最后提出了有效的容错机制容忍FIFO故障。
1 FIFO功能模型及故障模型
本文选用的路由器是基本的虫孔路由器，采用虫孔交换机制，输入通道中利用FIFO作为数据包缓存。
1.1 FIFO功能模型
本文讨论的是异步双端口RAM型FIFO，其功能模型如图1所示。
FIFO相关控制信号作用如下：
FF：FIFO满信号，为1表示满，为0表示不满；
EF：FIFO空信号，为1表示空，为0表示不空；
RS：复位信号，将读写地址恢复到初始地址（Initial Address,IA），即（RAR）:=IA||（WAR）:=IA||FF:=0||EF:=1，||代表操作同时独立发生；
WE：写使能，WE=1时允许写操作；
RE：读使能，RE=1时允许读操作；
WClk：写时钟；
RClk：读时钟。
1.2 FIFO故障模型
本文结合RAM型FIFO中寻址故障和功能故障发生相似性，将片上网络FIFO故障分为存储单元阵列故障和FIFO控制逻辑故障两大类。存储单元阵列故障模型包括：固定型故障(Stuck-At Fault，SAF)、开路故障(Stuck-Open Fault，SOF)、地址译码器故障(Address Decoder Fault，ADF)、跳变故障(Transition Fault，TF)、耦合故障（Coupling Fault，CF)(包括倒置耦合故障CFin，固化耦合故障CFid，状态耦合故障CFst)、数据延时故障(Data Retention Fault，DRF)和多端口故障(Multi-Port Fault，MPF)。FIFO控制逻辑故障模型主要有以下5种：
FF=0,while(WAR)=(RAR) and (LO)=WO；
FF=1,while(WAR)≠(RAR) or (LO)≠WO；
EF=0,while(WAR=RAR) and (LO=RO)；
EF=1,while(WAR)≠(RAR) or (LO)≠RO；
RS:(WAR)≠IA or (RAR)≠IA or (LO)≠RO。
2 容错设计
2.1 实时故障检测算法描述
i=test_address；//FIFO地址指针
j=0；//j代表单地址测试周期
while(j≤2) do
if(j == 1||j == 2)
delay；//发现DRF故障
temp1=read(i)；
if(j == 0)
if(0 < i < n-1) check(FF == 0&EF == 0);
if(i = n-1) check(FF == 0&EF == 1);
original = temp1;
write(i,!temp1) & temp2 = read(i);
result = compare(temp1,temp2);
else if(j == 1)
result = compare(temp1,original);
write(i,!temp1) & temp2 = read(i);
result = compare(temp1,temp2);
if(0 < i < n-1) check(FF == 0&EF == 0);
if(i = n-1) check(FF == 1&EF == 0);
else
result = compare(temp1,original);
end if
j = j+1;
endwhile
算法中i代表FIFO的测试地址，每次测试分为3个阶段，由j来控制，当j为0时执行算法的第一个阶段，读出测试地址test_address的值，保存在一个临时寄存器temp1中，并通过判断是否是FIFO最后一个地址来检查空标志EF的状态，随后将temp1的值保存在一个寄存器original中，然后对temp1取反，将取反值写到测试地址上，与此同时，读出测试地址上的值与temp1做比较；当j为1时，进入第二个测试阶段，先经过一段时间的延迟，然后读出测试地址上的值存在temp1中，与original值作比较，并将temp1值取反写回到测试地址上，与此同时，读出测试地址上的值，与temp1值作比较，并通过判断是否是FIFO最后一个地址来检查满标志FF的状态；当j为2时，同样经过一段延时，然后读出测试地址上的值，最后一个阶段的读操作保证了对前两个阶段未发现的故障再次进行检测，有效增强了故障检测能力。
2.2 故障覆盖率分析
针对前文描述的不同故障类型，本文对提出的测试算法能达到的故障覆盖率分析如下。
耦合故障(CF)： 算法对FIFO每个地址的值都采取了翻转和读写交替操作，但是地址只递增遍历一次，对于侵略单元地址大于受害单元地址的故障不能检出，因此只能覆盖50%的耦合故障。
数据延时故障(DRF)：算法描述中的Del代表了一定的延时操作，可覆盖DRF。
控制逻辑故障：可对空满信号FF/EF故障进行检测，但是因为算法强调实时性和无损性，所以对复位信号RS故障无法检测。
2.3 FIFO重定向机制
本文引入FIFO读写指针重定向表（Redirection Table），提出一种FIFO故障检测与重定向机制。读写地址生成器生成的读写指针输入到重定向表中，产生输入到FIFO缓存的读写指针，其原理图如图3所示，深色方块代表故障槽。在未检测到故障时，重定向表与FIFO中地址一一顺序对应；当检测到故障后，测试电路产生地址更新信号address_update对重定向表进行更新，有效避开了故障并充分节省了片上资源。
3 功能比较及实验结果
3.1 功能比较
本文提出的路由器FIFO检错容错方法与文献[4]、文献[6]提出的方法在故障覆盖率、测试在线性和是否有容错机制分析比较如表1所示。可以发现本文方案故障覆盖率较高，具有实时测试性，且包含容错机制。
3.2 仿真实验
本文采用修改的开源片上网络仿真器作为仿真实验平台，使用systemC作为硬件描述语言，搭建的拓扑结构为4×4的mesh结构，FIFO深度为6个微片，路由算法采用XY维序路由方式。根据提出的算法设计相应的FIFO故障测试电路，并通过设置故障测试电路不同的时钟周期观察网络的延时和吞吐率。
图4所示的是在不同的测试周期下网络的吞吐率变化图。随着测试周期的不断增加，吞吐率增长越来越缓慢，逐渐接近一个固定值，这是因为当测试周期增加，对FIFO测试的频率减少，测试过程对片上网络正常工作模式的影响越来越小。
图5所示为不同测试周期下的网络延时变化图，随着测试周期的不断增加，平均网络延时逐渐接近一个固定值。
为测试本文容错机制对故障容忍的效果，在FIFO注入相同故障的情况下，比较基准虫孔路由器和本文提出的路由器在不同数据包注入率下的吞吐率和延时。图6所示为吞吐率对比图，随着注入率增大，采用基准路由器和本文路由器的网络的吞吐率都逐渐接近饱和值，但是因为本文路由器采取了容错措施，吞吐率改善约为17.89%。
图7所示为延时对比图，可以看出本文的路由器随数据包注入率增加，延时均小于基准路由器，这是因为基准路由器未设计合适的容错机制，随注入率增加，基准路由器的堵塞和丢包现象越来越严重。与基准虫孔路由器相比，本文路由器延时改善约25.67%。
4 结论
本文根据FIFO读写特性，提出了一种可对片上网络路由器FIFO故障实时检测并对故障容忍的方法。实验结果表明，在故障条件下，能有效提高片上网络吞吐率，并且降低了网络延时。
参考文献
[1] 姚磊，蔡觉平，李赞，等.基于内建自测技术的Mesh结构NoC无虚通道容错路由算法[J].电子学报，2012，40(5)：983-989.
[2] Liu Junxiu，Jim Harkin，Li Yuhua，et al.Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead[J].IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems，2016，35(2)：260-273.
[3] Pavan Poluri，Ahmed Louri.Shield：a reliable network-on-chip router architecture for chip multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems，2016.
[4] Andrew DeOrio，David Fick，Valeria Bertacco，et al.A reli-able routing architecture and algorithm for NoCs[J].IEEE Transactions on Computer-aided design of Integrated Circuits and Systems.2012，31(5)：726-739.
[5] 欧阳一鸣，陈义军，梁华国，等.一种故障通道隔离的低开销容错路由器设计[J].电子学报，2014，42(11)：2142-2149.
[6] Bibhas Ghoshal，Kanchan Manna，Santanu Chattopadhyay et al.In-field test for permanent faults in FIFO buffers of NoC routers[J].IEEE Transactions on Very Large Scale Integration Systems.2016，24(1)：393-397.
[7] SEBASTIAN W，JAVIER N，MIKEL L.A survey on design approaches to circumvent permanent faults in networks-on-chip[J].ACM Computing Surveys.2016，48(4)：5920-5936.
作者信息:
杭彦希，徐金甫，陈松涛，郭朋飞
（解放军信息工程大学，河南 郑州450001）