APP下载

一种SRAM型FPGA抗软错误物理设计方法

2013-07-25王祖林郭旭静华更新

电子与信息学报 2013年4期
关键词:线网桥接开路

赵 磊 王祖林 郭旭静 华更新

①(北京航空航天大学电子信息工程学院 北京 100191)

②(北京控制工程研究所 北京 100190)

1 引言

近年来,SRAM(Static Random Access Memory)型FPGA凭借其高性能、低功耗和灵活性等特点广泛应用于工业和航空航天等领域。然而,随着晶体管特征尺寸的减小、逻辑密度的增加以及工作电压的降低,使得SRAM型FPGA对高能粒子辐射,尤其是单粒子翻转(Single Event Upsets,SEU)表现出更强的敏感性,造成内部状态错误[1]。由于这种错误具有瞬态、随机和可恢复的特点,被称为“软错误”。频繁发生的软错误将导致可靠性降低,严重影响系统的稳定性。

在超深亚微米工艺的存储器中,由粒子入射引起的多位翻转(Multiple Bit Upset, MBU)在所有单粒子事件中的比例大约为 10%~30%[2,3]。ITRS(International Technology Roadmap for Semiconductors)预测至2016年,25 nm工艺下集成电路的软错误将全部来自于单粒子多位翻转[4]。因此,MBU正逐渐凸显成为影响可靠性的重要因素,同时多位翻转的特殊性,将极大地增加容错代价,对现有的容错技术提出挑战。当翻转发生在FPGA的逻辑资源,往往在下一个驱动时钟周期消除,采用TMR(Triple Modular Redundancy)冗余方式[5,6]或纠检错编码[7,8]可以有效地降低对系统的影响;但当翻转发生在可编程布线资源时,由于配置信息的改变影响电路的功能,造成持续性软错误,严重者会造成系统异常和故障。这种布线资源配置位翻转造成的软错误占SEU软错误的90%以上[9],通常只能通过回读擦写方式进行恢复,需要额外的硬件资源和时间才能实现容错[10]。

一些研究者尝试使用尽量少的容错开销来减缓SEU的影响,他们从物理设计的角度展开研究,通过优化逻辑综合、有效的布局布线,可以在不增加额外资源的前提下降低软错误的发生概率。文献[11]提出采用布线资源开路和短路故障对应的敏感比特来评价软错误的方法,将敏感比特作为成本函数引入布局布线寻优目标,从而减少 SEU对系统的影响,但成本函数相对简单;文献[12]在布线过程中通过减少相关比特数目来提升抗辐射性能;文献[13]通过计算开关矩阵的使用概率进一步完善了 SEU软错误成本函数,使其可以更准确地描述短路敏感位;文献[14]则从系统失效率的角度,通过使用错误传播概率驱动整个 CAD流程,但此方法在布局布线过程中使用错误传播概率,缺少布线资源的评估,因而是不准确的。以上方法都只针对单粒子翻转引起的单位翻转(Single Bit Upset, SBU),并没有考虑MBU会引起更多的桥接错误和更高的错误传播概率。文献[15]针对多位翻转发生在冗余结构的多个分模块造成冗余失效的问题展开研究,只针对 TMR进行减缓MBU的布局布线,不具有通用性。

因此,本文在分析软错误模型后,通过引入布线资源软错误发生概率,提出了可以减缓 MBU和SBU的物理设计的方法。通过采用更精确有效的方法评估软错误发生概率,并结合EPP驱动布局布线过程,用以减少软错误。实验结果表明,在不增加额外硬件资源的情况下,可以降低系统失效率18%,并可以较好地抵抗MBU对系统的影响。

2 FPGA软错误模型

岛链式SRAM型FPGA的布线资源主要由开关矩阵和互连线段组成,其中开关矩阵由开关盒(Switch Box, SB)和连结盒构成,开关盒是控制水平和垂直方向上互连的重要结构,由可编程互连点(Programmable Interconnection Points, PIPs)控制,通过SRAM配置存储单元决定连接关系。常用的开关盒有Universal, Wilton和Disjoint 3种形式,如图1所示。这3种结构中,每边可以连接其他边的数目是固定的,用开关盒连通度(flexibility of switch box,fs)表示,通常取值3或4,用以平衡开关盒复杂度和布通性;用W表示每个布线通道内的轨道数。由于3种开关盒结构具有相似性,本文以Xilinx经典的Disjoint开关盒为例研究软错误对开关盒的影响,主要的错误模式是开路错误、短路错误和桥接错误[11]。

图1 经典开关盒结构

2.1 开路错误

开路错误通常是可编程互连点存储的信息从“1”变成“0”引起,造成线网断开。例如在图 2中,线网1通过开关盒1的PIP(N0,W0)进行连接,如果SEU发生在PIP(N0,W0),会造成线网1发生开路错误。每个线网使用的PIP都可能发生开路错误,通过减少线网的长度能有效减少发生开路错误。因此,利用线网逻辑单元之间的曼哈顿距离|xp(i)-xq(i)|+|yp(i)-yq(i)|+1 可以有效地评估开路错误。其中,(xp(i),yp(i))和(xq(i),yq(i))分别表示线网i中需要进行连接的两个逻辑单元的坐标值。

图2 开关盒错误示意图

2.2 短路错误

所有未使用的可编程互连点都可能发生短路错误。当SEU造成可编程互连点从“0”到“1”翻转时,就会发生短路错误,例如开关盒2中的PIP(S1,E1)和PIP(S2,N2)。发生这种短路错误的PIP只连接一个线网或者没有连接线网,因此属于 SEU非敏感的,不会造成线网连接错误,只会造成工作电流的增加和功耗的增大。当PIP连接两个线网时,引起的短路错误会影响系统功能,为了以示区别,特将这类错误归类为桥接错误。

2.3 桥接错误

桥接错误可以发生在开关盒内,还可以发生在开关盒之间。例如图2中,开关盒1的PIP(W0,S0),PIP(N0,S0), PIP(N0,E0)发生SEU时,会导致线网1与线网2发生开关盒内的桥接错误;如果开关盒 2的PIP(W2,E2)发生翻转,就会造成线网2与线网4发生开关盒间的桥接错误。然而,开关盒内的 PIP发生单粒子翻转时,并不一定会引发桥接错误。因此,本文将在 3.1小节中讨论布线资源桥接错误发生概率,用以准确评估此类错误对系统的影响。

2.4 MBU软错误

与SBU引起的软错误相比,MBU在软错误中所占比例越来越大。研究表明 MBU主要集中在 4位以内,60%以上是 2位翻转(Double Bit Upset,DBU),很少发生4位以上翻转,其错误图样主要表现为同一行/列两位连续错误或者呈对角线错误[16,17]。由于DBU所占比例最大,本文对MBU的研究针对DBU展开。2位翻转表现为00→11, 01→10, 10→01和11→00,产生4种错误模式。

(1)1位开路或桥接错误:两位翻转中只有1位翻转产生错误,另1位产生短路或不影响。DBU的4种形式都可能引发这种错误,其错误模式和前文所述的单位翻转相同。

(2)2位开路错误:DBU同时发生开路错误,只有11→00才有可能导致这种类型的错误,等价于发生了两个SBU。

(3)2位桥接错误:DBU同时引发桥接错误,这种错误存在于00→11的表现形式中。如果两位翻转同时存在于一个开关盒内,将会增大桥接错误发生概率。

(4)1位桥接同时1位开路:DBU的这种情况等效于独立发生前文所述的单位桥接和单位开路错误。

3 软错误失效率评估

3.1 布线资源错误概率评估

如前文所述,布线资源的开路错误可以利用逻辑单元之间的曼哈顿距离进行量化评估,短路错误并不会引发系统功能错误,只有桥接错误缺少有效的评估方法。本小节在开关盒使用概率的基础上,提出了桥接错误概率,能够在布局阶段合理、精确地反映桥接错误。

(1)开关盒使用概率 在布局阶段可以采用减少线网之间的重叠来减少桥接错误,但这种粗略的评估方式必然会引起面积和时延的较大开销[13]。然而,通过计算开关盒使用概率可以更准确地描述桥接错误。如图3所示,假设某一线网的源端位于(1,1)的相对位置,漏端位于(m,n)的相对位置,f(m,n)表示从位置(1,1)到(m,n)所有可能的布线情况数目,那么从图3中可以得到递归表达形式:

图3 开关盒使用概率示意图

同时,由于布线器采用线长驱动,即选择最短路径进行布线,所以可以得到f(m, 1)=1 和f(1,n)=1 。结合式(1)解递归可得

于是,位于位置(i,j)处的开关盒使用概率PU(i,j)可以利用从(1,1)到(i,j)、从(i,j)到(m,n)分段布线所有可能情况的路径数与从(1,1)到(m,n)所有可用路径数目的比值进行表示,如式(3)所示。

(2)桥接错误概率 当两个线网使用同一个开关盒时,开关盒内的PIP发生单粒子翻转并非一定会引起桥接错误。因此,本文提出了桥接错误概率来准确计算桥接错误。假设通过开关盒的线网数目为NI,且都是单输入单输出,则此开关盒内可用的PIP数目为2Wfs-NI。对于Disjoint型开关盒,只有不同通道的同一端子号线网才有可能发生桥接错误,于是可能发生桥接错误的PIP数目为2·φ(NI)·(fs-1),其中φ(NI)是相同端子号评估函数,用来表示NI个线网中可能发生桥接错误的数目,其取值范围是0~NI/2。设λ(φ(NI))为φ(NI)在不同取值情况下的概率,于是发生在同一开关盒内的桥接错误概率可以表示为

例如,当W=4,fs=3,NI=4时,φ(NI)取值为0, 1, 2三种,对应的λ(φ(NI))分别为2/17, 12/17,3/17。于是PBI=18/85。图 4的 SBU曲线给出了W=4,fs=3时,不同NI值与错误概率的关系情况,横坐标为不同NI值,由于每个相同端子号可以容纳的线网数目最大为2,所以NI的最大值为2W;纵坐标为同一开关盒桥接错误概率。从图中可以看出随着NI的不断增大,即通道使用率越来越高,错误概率逐渐趋近于 1,这说明通过减少开关盒内的线网数目同样可以减小错误概率。

图4 同一开关盒错误概率与开关盒内线网数目的关系

对于 DBU发生在同一开关盒的情况,其桥接错误概率可以表示为

图4中给出了开关盒内2位、3位翻转与单位翻转的对比情况,从图中可以看出 MBU的翻转位数越大,发生错误的概率也越高。

结合开关盒使用概率就可以在布局阶段有效评估开关盒内的桥接软错误,设Nol表示可能使用(i,j)位置开关盒的线网数目,则某一开关盒的桥接软错误可以表示为

对于相邻开关盒的情况,设某线网使用了开关盒中的一个 PIP,则可能发生相邻开关盒桥接错误的PIP数目为(fs-1);若对应通道内相邻开关盒中有NN个线网通过,那么这NN个线网使用相同端子号的概率可以简单表示为NN/2W。于是,发生开关盒间桥接错误的概率为

如果 DBU分别位于两个相邻的开关盒,那么桥接错误概率为

结合前文所述开关盒使用概率,某一开关盒布局阶段可能发生开关盒间桥接故障的概率为

其中PUB(i,j)表示相邻开关盒的使用概率,Nnb表示可能使用的相邻开关盒数目。

3.2 系统失效概率评估

本文采用基于概率模型的方法评价软错误影响下的电路可靠性,首先假定电路中的一个节点是故障源,建立从此节点到可达输出端的通路,设定不在通路上的线端信号概率,计算在通路中的软错误传播概率(Error Propagation Probability, EPP),据此评估电路的失效概率。EPP通常采用错误发生后在线网中传播到输出并对电路正常功能产生影响的概率表示,其计算方法参见文献[18]。

然而这种方法在计算系统失效概率(System Failure Rate, SFR)时,不能有效地反映出布线资源的错误对系统失效率的影响,尤其是潜在的桥接错误影响。因此,本文利用前文提出的布线资源错误概率与 EPP相结合的方式来有效计算系统失效概率,即对每个网表,计算从输入到输出的EPP,同时利用布线资源错误评估得到节点错误概率(Node Error Rate, NER),最后采用乘积形式表示SFR,如式(10)所示:

NSB表示所用到的开关盒数目,α,β用来平衡不同软错误的贡献程度。

4 抗软错误CAD设计流程

本文提出的抗软错误CAD设计流程如图5所示。首先优化相关电路的逻辑,并将其映射到查找表和触发器上,其输出为.blif网表文件格式;其次,利用此网表计算所有线网的 EPP,然后利用 EPP将其打包转化为逻辑块为单位的网表.Net格式;接下来利用前文所述的布线资源软错误评估得到的信息驱动布局布线,最终形成配置信息,并计算系统失效概率。

4.1 抗软错误打包与优化

逻辑单元块的打包是把数个 LUT和寄存器按照一个的约束条件合并成一个逻辑块。首先选择具有最大关键度的未打包逻辑块作为新 Cluster的种子,再将未打包的单元按吸引因子的大小以此加入,直到Cluster被填满为止。其吸引因子由关键度、线网共享程度和错误传播概率EPP组成。这个步骤的优化目标是把彼此连接的LUT打包在一起,以减少逻辑单元快之间待布线的信号数目,并且尽可能达到每个逻辑单元块的绒线,使得用到的逻辑单元块数目最少。

图5 抗软错误CAD设计流程

4.2 抗软错误布局

布局算法确定了实现电路功能需要的各逻辑单元块在 FPGA中的位置。经典的 VPR[19]布局算法基于模拟退火算法,首先随机分配逻辑单元块到FPGA以得到初始布局,然后通过大量的随机移动或者局部优化来改进布局。每次移动后接受与否由成本函数差值决定,其优化目标是最大限度提高电路速度(时序驱动)和最大程度地减少所需的布线资源(线长驱动)。

设Dl(i,j)、Cr(i,j)和CE分别表示i,j连接的延时、关键性和关键性系数,CC表示所有使用的逻辑单元集合,那么时序驱动成本函数可以表示为

而线长驱动成本函数计算公式为

其中,bbx(i),bby(i)分别表示线网i的边界框的水平、垂直跨度;q(i)是与线网i端口数有关的函数,用于补偿随着端口递增而导致线网的非线性增加;Cav,x(i)和Cav,y(i)分别是线网i的边界框在x和y方向的平均通道宽度;β用于调整不同宽度通道的相对成本;Nn为线网数目。

通过前文分析,SEU导致的开路错误成本函数由线网的边界框决定,与线长驱动的成本函数和优化目标一致,因此,布局时不需要单独考虑开路错误,只需用式(14)替换式(11)计算系统失效概率。

考虑到开关盒内的桥接错误要略高于开关盒间的桥接错误,通过实验表明α取 0.75~0.90之间时能够较好地平衡两种错误形式。于是,在布局阶段预评估系统失效概率可以采用式(15)作为成本函数之一驱动布局过程。

本文在构建代价函数时,不但考虑了线长和时序的影响,还考虑了由SEU引起的FPGA内部软错误,其目标代价函数如式(16)所示:

4.3 抗软错误布线

FPGA的布线过程是设置合适的可编程开关来连接所有逻辑单元块的输入和输出引脚。VPR采用了PathFinder多次迭代算法,通过允许布线资源的重用,利用布线资源节点连接成本的变化来解决拥挤问题,可以同时考虑时序和布通性。布线资源节点n的成本函数可以表示为

其中,第1项表示延时,第2项表示拥挤度,b(n),h(n)和p(n)分别表示节点n的基本成本、历史拥挤度和当前拥挤度成本。

在考虑软错误影响因素后,将布线节点n的成本函数重新定义为

其中SEC是反映节点n对软错误的敏感程度,也就是发生桥接故障的可能性,由前文所述的软错误发生概率确定。

经典的布线算法反复拆线重布电路中每一条冲突的线网,直到所有的拥挤都消除。而本文所述的提高FPGA抗软错误的本质是减少开关盒出现开路和桥接错误的可能,SEC反映出节点n对软错误的敏感程度,其取值是与本次布线迭代中已使用的互连资源相关。如果n周围的开关盒未被使用,那么当前线网使用布线节点n将不会引起桥接错误,其影响在于使得布线结构更加分散,即各线网的分布更加稀疏。在每次拆线重布时,SEC需重新计算并计入互连资源的总成本,因此,该算法可以寻找出总成本最小的路径,实现在尽量少的互连资源情况下降低互连资源软错误的可能。

5 仿真实验与结果

为了对所提出的抗软错误物理设计方法进行验证,实验采用 MCNC(Microelectronics Center of North Carolina)基准电路集,每个网表通过SIS逻辑优化后,使用Flowmap进行工艺映射,利用引入EPP的T-VPack进行打包,然后采用修改后的VPR布局布线工具对电路网表进行实现,最后进行可靠性评估。设计开销由面积、延时和功率3部分组成,各占1/3。

对于只有一个单粒子翻转,为了和文献[14]中仅使用EPP驱动CAD进行对比,直接计算了系统失效概率改善比例(Soft Failure Rate Improvement,SFRI)。对于单粒子多位翻转的情况,采用故障注入方式模拟辐射环境进行可靠性评估[20]。故障注入基于局部重配置方法,将 FPGA中内嵌的 PowerPC核作为故障注入控制器,首先通过 PLB(Processor Local Bus)从BRAM中读取重配置比特流;其次对比特流进行随机翻转操作,模拟SEU的发生,生成故障注入序列;然后利用 ICAP(Internal Configuration Access Port)对FPGA进行重配置;最后对结果进行采集,与正确结果比较,判定SEU是否影响FPGA的正常工作。对于DBU,其比例分别为10%、30%、50%、80%和100%,注入次数为10000次;此外,实验还对MBU中的3位翻转进行故障注入实验,其比例与DBU相同(其余为单位翻转),注入次数为10000次。

表1给出了本文所述CAD流程与文献[14]中采用SEU-AWARE CAD流程在SFRI上的结果对比情况,SFRI从12.45%上升到18.01%,设计开销几乎没有增加。从表1中可知,本算法对不同电路的提升效果有所不同,其原因在于电路的输入输出管脚数目以及CLB数目不同,同时由于布局布线寻优的随机性导致电路提升效果存在差异。图6给出了以上电路在不同 DBU比例下的发生错误的平均百分比。从图中可以看出本文提出的算法可以有效地降低DBU对系统的影响,当DBU比例增加时,系统失效概率远低于其他方式,且没有显著地上升,这说明本文提出的算法对不同比例的 DBU有很好的适应性。由于配置单元数目较大以及故障注入的随机性,导致只有 1%~3%的注入实验引发了电路功能错误,但仍可以验证本算法缓解 DBU的有效性。图7给出了在不同3位翻转比例下发生错误的平均百分比,其结果与 DBU相似,从图中可以看出,本算法同样可以有效地缓解3位翻转对系统的影响。

图6 不同DBU比例下的错误发生比例情况(10000次故障注入)

图7 不同3位翻转比例下的错误发生比例情况(10000次故障注入)

表1 SFRI和开销对比

6 结论

本文对SRAM型FPGA的单位翻转和多位翻转进行分析,提出了布线资源软错误发生概率能够有效评估SEU软错误,并通过结合错误传播概率计算系统失效率,对FPGA的物理设计流程中的打包、布局布线算法进行了优化改进。实验结果表明,本文提出的方法能够减少SBU和MBU作用下的软错误,提高FPGA的抗辐射性能。

[1]Naumann R C. Radiation-induced soft errors in advanced semiconductor technologies[J].IEEE Tranactions on Device and Materials Reliability, 2005, 5(3): 305-316.

[2]Quinn H, Graham P, Krone J,et al.. Radiation-induced Multi-Bit Upsets in SRAM-based FPGAs[J].IEEE Transactions on Nuclear Science, 2005, 52(6): 2217-2223.

[3]Tipton A D, Pellish J A, Hutson J M,et al.. Deviceorientation effects on multiple-bit upset in 65 nm SRAMs[J].IEEE Transactions on Nuclear Science, 2008, 55(6):2880-2885.

[4]ITRS. The International Technology Roadmap for Semiconductors(2011Edition)[R]. http://www.itrs.net, 2011.

[5]谭宜涛, 杨海钢, 黄娟, 等. 基于关键路径的三模冗余表决器插入算法[J]. 电子与信息学报, 2012, 34(2): 487-492.

Tan Yi-tao, Yang Hai-gang, Huang Juan,et al.. Voter insertion algorithm based on critical path for triple module redundancy[J].Jounal of Electronics&Information Technology, 2012, 34(2): 487-492.

[6]Ruano O, Maestro J A, and Reviriego P. A fast and efficient technique to apply selective TMR through optimization[J].Microelectronics Reliability, 2011, 51(12): 2388-2401.

[7]Argyrides C A, Reviriego P, Pradhan D K,et al.. Matrixbased codes for adjacent error correction[J].IEEE Transactions on Nuclear Science, 2010, 57(4): 2106-2111.

[8]She Xiao-xuan, Li N, and Jensen D W. SEU tolerant memory using error correction code[J].IEEE Transactions on Nuclear Science, 2012, 59(1): 205-210.

[9]Asadi G and Tahoori M B. Soft error mitigation for SRAM-based FPGAs[C]. Proceedings of the IEEE VLSI Test Symposium, California, 2005: 207-212.

[10]Sari A and Psarakis M. Scrubbing-based SEU mitigation approach for systems-on-programmable-chips[C]. Proceedings of Field-Programmable Technology(FPT), New Delhi, 2011:1-8.

[11]Zarandi H R, Miremadi S G, Pradhan D K,et al.. SEU-mitigation placement and routing algorithms and their impact in SRAM-based FPGAs[C]. Proceedings of International Symposium on Quality Electronic Design, San Jose, 2007: 380-385.

[12]Golshan S and Bozorgzadeh E. Single-Event-Upset(SEU)awareness in FPGA routing[C]. Proceedings of the ACM/IEEE Design Automation Conference, San Diego, 2007:330-333.

[13]Abdul-Aziz M A and Tahoori M B. Soft error reliability aware placement and routing for FPGAs[C]. Proceedings of the IEEE International Test Conference(ITC), Austin, 2010:1-9.

[14]Bahramnejad S and Zarandi H R. Mitigation of soft errors in SRAM-based FPGAs using CAD tools[J].Computers and Electrical Engineering, 2011, 37(6): 1019-1031.

[15]Sterpone L and Battezzati N. A new placement algorithm for the mitigation of multiple cell upsets in SRAM-based FPGAs[C]. Proceedings of Design, Automation and Test in Europe Conference and Exhibition(DATE), Dresden, 2010:1231-1236.

[16]Zhang Q X, Hou M D, Liu J,et al.. The impact of incident angle on multiple-bit upset in SRAMs[J].Nuclear Instruments and Methods in Physics Research B, 2003, 209:367-370.

[17]Radaelli D, Puchner H, Wong S,et al.. Investigation of multi-bit upsets in a 150 nm technology SRAM device[J].IEEE Transactions on Nuclear Science, 2005, 52(6):2433-2437.

[18]Asadi H and Tahoori M B. An accurate SER estimation method based on propagation probability[C]. Proceedings of IEEE Design, Automation and Test in Europe, Munich, 2005:306-307.

[19]Luu J, Kuon I, Jamieson P,et al.. VPR 5.0: FPGA cad and architecture exploration tools with single-driver routing,heterogeneity and process scaling[C]. Proceedings of the International Symposium on Field Programmable Gate Arrays, New York, 2009: 133-142.

[20]Sterpone L and Violante M. A new partial reconfigurationbased fault-injection system to evaluate SEU effects in SRAM-based FPGAs[J].IEEE Transactions on Nuclear Science, 2007, 54(4): 965-970.

猜你喜欢

线网桥接开路
高效水泥磨开路系统的改造
Microchip推出首款车载以太网音视频桥接(AVB)全集成解决方案
替罗非班桥接常规抗血小板治疗早期PWI-DWI不匹配脑梗死的疗效评价
新型线网城轨乘客信息系统的研究与分析
轨道交通COCC线网信号系统设计
王旭鹏倾情献唱最新单曲《开路者》
自然生物挖角开路
延续了两百年的“开路日”
利用桥接技术防治苹果树腐烂病
苹果腐烂病树桥接复壮技术