王 辉 汪 芸 马骏驰

(东南大学计算机科学与工程学院，南京210096)

一种考虑防护措施的缓存可靠性评估方法

王 辉 汪 芸 马骏驰

(东南大学计算机科学与工程学院，南京210096)

为了提高缓存单元的可靠性,在软错误防护代价和缓存可靠性之间进行均衡,提出一种基于马尔科夫链的缓存可靠性模型.首先，改进了现有缓存架构脆弱性因子AVF和生命周期分析方法；然后，将单粒子时空单比特和多比特翻转的非等概率特性进行综合分析,在缓存可靠性设计中加入诸如奇偶校验、单位纠错双位检错和交错布局等防护措施；最后，基于单粒子翻转时空累积效应和检错纠错防护策略,使用SPEC2000标准测试程序在Sim-Alpha仿真处理器上对该评估方法进行实验验证.结果表明:所提方法可较好地预测特定应用程序下的缓存可靠性;相比于传统的基于蒙特卡洛错误注入的方法,该方法时间开销更小,应用针对性更强.

软错误;时空多位翻转;AVF分析;马尔科夫状态

随着半导体技术的飞速发展,集成电路制造工艺不断向超深亚微米发展.处于太空环境下的卫星系统易遭受高能带电粒子的撞击,发生存储位的单位或多位翻转;并非所有翻转都会在输出结果中显现出来[1-2],有可能在微架构级、架构级甚至应用层级被屏蔽.Wang等[1]通过软错误注入实验发现，只有少于15%的处理器状态位翻转才会导致软件层可视的错误.为了更好地均衡防护代价和系统可靠性,需要识别处理器中对软错误最敏感的区域.Mukherjee等[2]利用架构脆弱性因子(AVF)分析方法来评估系统部件在遭受单粒子翻转后发生故障的概率.基于此,研究人员又提出了许多可靠性评估方法[3-5].微处理器中存储单元对软错误最为敏感;奇偶校验等ECC防护措施的使用,则增强了存储单元抗单粒子效应的能力.如何评估采用了ECC防护措施以及遭遇时空单粒子累积效应的缓存的可靠性成为目前研究的热点.

本文首先对现有的AVF评估方法[5-7]加以改进,以更准确地反映缓存单粒子效应模型;然后,对采用ECC防护措施的缓存发生软错误后的可靠性进行分析;最后,通过仿真实验得出预测结果.

1 改进的AVF评估方法

Mukherjee等[2]引入架构脆弱性因子AVF、ACE和un-ACE等概念,以量化处理器中不同结构对原生错误的屏蔽效应.其中,ACE是指发生单粒子翻转后可能在程序最终输出结果中表现出来的存储位或区间;例如,程序计数器PC的翻转极有可能导致程序执行错误.un-ACE是指即使发生翻转也不会在最终程序输出结果中表现出来的存储位或区间,如分支预测等性能增强指令.针对存储单元,AVF是指在特定时钟周期内所包含ACE的百分数;针对逻辑结构,AVF是指在特定时钟周期内处理ACE指令集的百分数.具有Nbit系统的AVF是指各子系统AVF的综合结果,即

(1)

式中,FAVF,FAVF，i分别为分析对象和比特i的脆弱性因子;BACE,i为比特i在程序执行过程中处于ACE位的比例;N为测试对象的比特位数;W为程序执行所需要的总的时间周期数.

AVF分析的目的是对模块内的元素进行软错误敏感性排名,以此来选择和保护最脆弱的单元.ACE分析的优势是可在处理器设计阶段对其进行可靠性评价;劣势是缺少微处理器结构的细节信息,需要手工对ACE位和un-ACE位进行分类.

采用生命周期方法对回写式缓存中的数据访问特性进行分析时,将读操作分解为read和read*, 其中read表示读取未被写过的数据,read*表示读取已被写过的数据;将写操作分解为write和write*,其中write表示动态死指令的写操作,write*表示非动态死指令的写操作.根据读写操作的定义及数据的访问特性,将read-evict判定为un-ACE,将read*-evict判定为ACE.缓存生命周期分析如图1所示.

图1 缓存生命周期分类

针对不同缓存数据的读写类型,将回写式缓存的生命周期进一步细化,得出更为准确的AVF值,为单粒子软错误评估和防护措施选择提供更为准确的依据.改进后的回写式缓存AVF生命周期分类方法见表1.

表1 回写式缓存生命周期分类

2 马尔科夫预测模型

AVF分析[1]和生命周期分析方法[5]未考虑使用软错误防护措施后系统的可靠性.在这2种分析方法的基础上,结合单位翻转和时空多位翻转的非等概率特性,提出了一种考虑ECC、刷新和交错布局等防护措施的缓存可靠性评估方法.此处,并不简单地认为所有载入缓存中的数据在退出之前都为敏感数据,而是根据应用程序中数据在缓存中的访问特性,确定其是否为敏感数据.这与文献[4]有所不同,使该分析方法对特定应用程序更有针对性.

2.1 软错误效应建模

定义1(脆弱性时钟周期) 所有ACE时间段均为脆弱性时钟周期VCC.

定义2(保护区域) 保护区域PD是指采用防护策略(如奇偶校验等)所保护的存储区域.本文考虑的保护区域为64 bit的8字节存储单元.

定义3(刷新间隔) 刷新间隔L是指ECC防护策略执行的时间间隔.

绝大多数的空间多位翻转都具有聚集效应[7-9],即软错误的形式会限定在一个连续的矩阵范围内.因此,空间多位翻转可表示为

MMBU=Rbits×Cbits

式中,Rbits和Cbits分别表示翻转在水平方向和垂直方向上的翻转模式.

为简化模型,本文只考虑2×4范围内的软错误,这些单粒子翻转形式数量占所有翻转类型数量的99.668%[9]. 每个时钟周期内,不同单粒子翻转模式的发生概率为

(2)

式中,dx,y(x=1,2;y=1,2,3,4)表示发生x×y型空间多位翻转的概率.

将保护单元PD在一个处理器时钟周期内发生单粒子翻转的概率定义为PSEU_PD.所有时钟周期内发生的单粒子效应是相互独立的.根据文献[9],时钟频率为3 GHz的处理器中保护区域发生软错误的概率PSEU_PD=6.499 2×10-24.

空间多位翻转的重叠效应如图2所示.如果存在单粒子翻转重叠效应,则错误位会在偶数次翻转后恢复为正确的状态.如果单粒子多位翻转发生在垂直方向上的多个保护区域内,则会导致该方向上多个保护区域都发生软错误.如果单粒子翻转发生在水平方向上相邻保护区域的交界处,则会导致这2个相邻保护区域都发生单粒子翻转效应.

(a) 第1次翻转

(b) 第2次翻转

(c) 重叠效应

第1次翻转位； 第2次翻转位

图2 空间多位翻转的重叠效应

考虑空间多位翻转重叠效应时,每个保护单元PD发生1～4 bit翻转的概率为

(3)

式中,PiBU为发生ibit翻转的概率.

空间多位翻转具有聚集效应.在发生第1次单粒子效应后,缓存保护区域内所出现的kbit翻转都是连续的.如果该保护区域出现第2次qbit单粒子效应,只可能存在以下3种情况:

1) 重叠位等于翻转位. 如图3(b)所示,0

(4)

式中,M为保护区域PD的位数.保护区域内软错误位数减少qbit.

(a) 第1次翻转

(b) 重叠位等于翻转位

(c) 重叠位小于翻转位

(d) 无重叠位

2) 重叠位小于翻转位.如图3(c)所示,0

(5)

3) 无重叠位.如图3(d)所示,o=0.这种情况的发生概率为

(6)

2.2 马尔科夫转换模型

定义4(马尔科夫状态) 保护区域PD所发生翻转的位数为马尔科夫状态(MS).

保护区域内翻转位数只与前一个时刻的状态和当前时刻是否发生翻转有关.针对本文考虑的64 bit保护区域,共有65种马尔科夫状态.根据软错误空间多位翻转的重叠效应,可建立不同马氏状态之间的转移矩阵,具体方法见算法1.其中,m表示发生空间多位翻转位数的最大值;tk,k+d表示翻转后保护区域内增加或减少dbit的概率.

算法1 马尔科夫转换矩阵生成算法

输入:软错误发生率piBU. 输出:马尔科夫转换矩阵T. forq←0 tomdot0,q=PiBU;

end

fors1←0 tomdo

fors2←0 to 2mdo

if (d%2≠0)

else if (d%2==0)

end

fork←0 to 2m+1 do

end

当缓存的保护策略包含刷新功能时,针对不同的刷新间隔L,MSk转变为MS0的概率增加1/L,即增加刷新策略后,可得

(7)

同时,需更新所有tφ,φ,可得

(8)

根据算法1、式(7)和 (8)可以建立不同马氏状态之间的转换矩阵,那么从MSk转换到MSk+d所持续的时间等于这2个状态之间的转换次数乘以处理器时钟周期数,缓存固有平均无故障时间MTTFin=ZMS0→MSkY,其中，ZMS0→MSk表示从状态MS0到状态MSk的转换次数,Y表示处理器时钟周期.整个应用程序的平均无故障时间MTTF=MTTFin/FAVF.

转换矩阵T为

(9)

式中,子矩阵S2u+1为带状矩阵;IN-2u为单位矩阵,其中的对角元素表示马氏链的吸收状态.

由式(9)可以得出

(10)

使用SEC型ECC防护措施后的缓存,从无翻转状态MS0转换为状态MSk(k≥2),即说明缓存已处于失效状态.同理可以得出,针对DEC和TEC到达失效状态MSk时,k分别满足k≥3和k≥4.考虑ECC防护策略后的转换矩阵为

(11)

在具有吸收状态的马尔科夫链中,存在基矩阵F=(I-T′)-1.对于具有标准形式T的转移矩阵的吸收链有以下定理[10]:

定理1 吸收链的基矩阵F中的每个元素,表示从一个非吸收状态出发,经过逐步变换后到达每个非吸收状态的平均转移次数.

定理2 设W=FH,其中H={1，1，…，1}T,则W中每个元素表示从非吸收状态出发,到达某个吸收状态被吸收之前的平均转移次数.

根据定理1和定理2, 基于算法1所建立的转换矩阵T,可以利用非吸收状态保持时间来计算保护区域PD的固有平均无故障时间MTTFin.结合不同应用程序的FAVF,即可得出不同应用程序在ECC防护及刷新策略下的系统平均无故障时间MTTF.

2.3 交错布局下的时空多位翻转

高可靠存储单元采用交错布局技术,将逻辑上相邻的存储位在物理布局上进行分隔.具有交错布局防护措施的软错误发生示例如图4所示.

翻转位； 分隔位

图4 交错布局下的空间多位翻转

假设随机变量w为保护区域内可防护软错误的位数;mac为系统失效时保护区域内发生软错误的位数;g为系统失效时保护区域内发生单粒子翻转的次数.则mac的数学期望为

(12)

式中,qv为第v次翻转产生的软错误位数;E(qv)为时空多位翻转产生软错误位数的平均数.

在泊松分布下,MTTF与METF之间存在如下关系:

(13)

式中,METF=E(g);λ为软错误发生率.

由此可得

(14)

在交错布局的防护措施下,缓存平均无故障时间在单位翻转和多位翻转之间存在如下关系:

(15)

综上所述,当存储单元采用交错布局防护技术时,通过改变软错误发生率λ,可以利用单位翻转来预估时空多位翻转的平均无故障时间.

3 仿真实验及结果分析

3.1 实验环境

本文将改进的AVF评估方法应用到通用的Sim-Alpha处理器模拟环境中,并采用标准的SPEC2000测试程序对缓存的可靠性进行评估,采用参考输入集并使用SimPoints工具[11]每间隔50 Mbit进行取样.

3.2 L2级缓存精确分析

图5为根据本文方法与开源软件Sim-SODA所得的AVF对比.由图可知,采用本文方法进行AVF分析时,read*-evict使AVF平均增加1.46%,read*-end-evict使AVF平均增加1.45%.考虑到动态死指令对write-evict阶段判定的影响,该阶段分为write*-evict和write-evict. write-evict使得AVF平均降低6.21%.采用Sim-SODA软件[7]进行AVF分析时,45.6%的write/write*-evict被误判为ACE.

3.3 可靠性分析

对标准测试程序Twolf在防护策略下的程序平均无故障时间进行仿真,FAVF=18.479 8%时的结果见表2．分析了不同防护策略(SECDED, DECTED,TECQED)的有效性,并将所得数据与文献[5,12]进行对比,以验证模型的正确性.采用ECC检错纠错码可有效提高缓存的可靠性(至少提高5个数量级);刷新能够显著提高缓存的可靠性,但是刷新频率过高则对可靠性的提高并不明显.因此,可以在刷新代价和可靠性目标之间进行均衡,选择较为合适的刷新频率.采用交错布局技术可以显著提高缓存的可靠性,相对于DECTED和TECQED两种防护策略,交错布局策略可以获得更高的系统可靠性.

表2 防护策略下程序平均无故障时间

4 结语

本文在现有缓存可靠性分析方法的基础上,利用改进的AVF评估方法,对缓存AVF进行定性的生命周期分析和定量的脆弱性分析. 根据缓存所使用的ECC和交错布局等防护措施,对真实场景下的软错误发生概率和模式进行合理假设,并提出了一种基于马尔科夫状态转换的可靠性评估方法.该方法不仅可以对目前占软错误比率最多的单位翻转的缓存可靠性进行评估,也能对非等概率条件下具有单位翻转、时空多位翻转累积效应的缓存可靠性进行评估,具有一定的通用性.最后,利用SPEC2000标准测试程序进行仿真实验,验证了该方法的可行性.

References)

[1]Wang N J, Quek J, Rafacz T M, et al. Characterizing the effects of transient faults on a high-performance processor pipeline[C]//2004IEEEInternationalConferenceonDependableSystemsandNetworks. Florence, Italy, 2004: 61-70.

[2]Mukherjee S S, Weaver C, Emer J, et al. A systematic methodology to compute the architectural vulnerability factors for a high-performance microprocessor[C]//Proceedingsofthe36thAnnualIEEE/ACMInternationalSymposiumonMicroarchitecture. Washington DC, USA, 2003: 29-40.

[3]Li X, Adve S V, Bose P, et al. SoftArch: an architecture-level tool for modeling and analyzing soft errors[C]//2005IEEEInternationalConferenceonDependableSystemsandNetworks.Yokohama, Japan, 2005: 496-505.

[4]Suh J, Annavaram M, Dubois M. MACAU: a Markov model for reliability evaluations of caches under single-bit and multi-bit upsets[C]//2012IEEEInternationalSymposiumonHighPerformanceComputerArchitecture. New Orleans, LA, USA,2012: 1-12.

[5]Reviriego P, Maestro J A. Study of the effects of multibit error correction codes on the reliability of memories in the presence of MBUs[J].IEEETransactionsonDeviceandMaterialsReliability, 2009, 9(1): 31-39.

[6]Biswas A, Racunas P, Cheveresan R, et al. Computing architectural vulnerability factors for address-based structures[C]//2005IEEEInternationalSymposiumonComputerArchitecture. Madison, WI, USA, 2005: 532-543.

[7]Fu X, Li T, Fortes J. Sim-SODA: a unified framework for architectural level software reliability analysis[EB/OL]. (2006)[2014-03-07]. http://www.ittc.ku.edu/～xinfu/publications/simsoda-mobs06.pdf.

[8]Georgakos G, Huber P, Ostermayr M, et al. Investigation of increased multi-bit failure rate due to neutron induced SEU in advanced embedded SRAMs[C]//2007IEEESymposiumonVLSICircuits. Kyoto, Japan, 2007: 80-81.

[9]Tipton A D, Pellish J A, Hutson J M, et al. Device-orientation effects on multiple-bit upset in 65 nm SRAMs[J].IEEETransactionsonNuclearScience, 2008, 55(6): 2880-2885.

[10]陈东彦, 李冬梅, 王树忠. 数学建模[M]. 北京：科学出版社, 2007:110-112.

[11]Hamerly G, Perelman E, Lau J, et al. Simpoint 3.0: faster and more flexible program phase analysis[J].JournalofInstructionLevelParallelism, 2005, 7(4): 1-28.

[12]Saleh A M, Serrano J J, Patel J H. Reliability of scrubbing recovery-techniques for memory systems[J].IEEETransactionsonReliability, 1990, 39(1): 114-122.

Cache reliability evaluation method considering protective strategies

Wang Hui Wang Yun Ma Junchi

(School of Computer Science and Engineering, Southeast University, Nanjing 210096, China)

In order to improve the reliability of cache, the balance between the price of soft error protection and reliability of cache is achieved, and a model based on Morkov chain is proposed. First, the existing architectural vulnerability factor (AVF) and the life cycle analysis method are improved. Then, the non-equiprobable time-space characteristics of single-bit and multi-bit upsets are comprehensively analyzed. Various protective measures, such as parity checking, single error correction double error detection (SECDED) and staggered layout, are applied to the reliability designs. Finally, based on the cumulative effect of temporal single event upset (SEU) and error detection/correction protective measures, the proposed method is verified by using standard benchmarks of SPEC2000 on a Sim-Alpha processor. The simulation results show that under the specific application, the proposed method can predict the reliability of cache. Compared with the traditional method based on the Monte Carlo of error injection, this method spends less time and is more application-specific.

soft error; temporal/spatial multiple bit upset; architectural vulnerability factor(AVF) analysis; Markov states

2014-07-14. 作者简介: 王辉(1988—),男,博士生;汪芸(联系人),女,博士,教授,博士生导师，yunwang@seu.edu.cn

王辉，汪芸，马骏驰.一种考虑防护措施的缓存可靠性评估方法[J].东南大学学报:自然科学版,2015,45(1):17-22.

10.3969/j.issn.1001-0505.2015.01.004

TP302.8

A

1001-0505(2015)01-0017-06