王 輝 汪 蕓 馬駿馳

(東南大學(xué)計算機科學(xué)與工程學(xué)院，南京210096)

一種考慮防護措施的緩存可靠性評估方法

王 輝 汪 蕓 馬駿馳

(東南大學(xué)計算機科學(xué)與工程學(xué)院，南京210096)

為了提高緩存單元的可靠性,在軟錯誤防護代價和緩存可靠性之間進行均衡,提出一種基于馬爾科夫鏈的緩存可靠性模型.首先，改進了現(xiàn)有緩存架構(gòu)脆弱性因子AVF和生命周期分析方法；然后，將單粒子時空單比特和多比特翻轉(zhuǎn)的非等概率特性進行綜合分析,在緩存可靠性設(shè)計中加入諸如奇偶校驗、單位糾錯雙位檢錯和交錯布局等防護措施；最后，基于單粒子翻轉(zhuǎn)時空累積效應(yīng)和檢錯糾錯防護策略,使用SPEC2000標準測試程序在Sim-Alpha仿真處理器上對該評估方法進行實驗驗證.結(jié)果表明:所提方法可較好地預(yù)測特定應(yīng)用程序下的緩存可靠性;相比于傳統(tǒng)的基于蒙特卡洛錯誤注入的方法,該方法時間開銷更小,應(yīng)用針對性更強.

軟錯誤;時空多位翻轉(zhuǎn);AVF分析;馬爾科夫狀態(tài)

隨著半導(dǎo)體技術(shù)的飛速發(fā)展,集成電路制造工藝不斷向超深亞微米發(fā)展.處于太空環(huán)境下的衛(wèi)星系統(tǒng)易遭受高能帶電粒子的撞擊,發(fā)生存儲位的單位或多位翻轉(zhuǎn);并非所有翻轉(zhuǎn)都會在輸出結(jié)果中顯現(xiàn)出來[1-2],有可能在微架構(gòu)級、架構(gòu)級甚至應(yīng)用層級被屏蔽.Wang等[1]通過軟錯誤注入實驗發(fā)現(xiàn)，只有少于15%的處理器狀態(tài)位翻轉(zhuǎn)才會導(dǎo)致軟件層可視的錯誤.為了更好地均衡防護代價和系統(tǒng)可靠性,需要識別處理器中對軟錯誤最敏感的區(qū)域.Mukherjee等[2]利用架構(gòu)脆弱性因子(AVF)分析方法來評估系統(tǒng)部件在遭受單粒子翻轉(zhuǎn)后發(fā)生故障的概率.基于此,研究人員又提出了許多可靠性評估方法[3-5].微處理器中存儲單元對軟錯誤最為敏感;奇偶校驗等ECC防護措施的使用,則增強了存儲單元抗單粒子效應(yīng)的能力.如何評估采用了ECC防護措施以及遭遇時空單粒子累積效應(yīng)的緩存的可靠性成為目前研究的熱點.

本文首先對現(xiàn)有的AVF評估方法[5-7]加以改進,以更準確地反映緩存單粒子效應(yīng)模型;然后,對采用ECC防護措施的緩存發(fā)生軟錯誤后的可靠性進行分析;最后,通過仿真實驗得出預(yù)測結(jié)果.

1 改進的AVF評估方法

Mukherjee等[2]引入架構(gòu)脆弱性因子AVF、ACE和un-ACE等概念,以量化處理器中不同結(jié)構(gòu)對原生錯誤的屏蔽效應(yīng).其中,ACE是指發(fā)生單粒子翻轉(zhuǎn)后可能在程序最終輸出結(jié)果中表現(xiàn)出來的存儲位或區(qū)間;例如,程序計數(shù)器PC的翻轉(zhuǎn)極有可能導(dǎo)致程序執(zhí)行錯誤.un-ACE是指即使發(fā)生翻轉(zhuǎn)也不會在最終程序輸出結(jié)果中表現(xiàn)出來的存儲位或區(qū)間,如分支預(yù)測等性能增強指令.針對存儲單元,AVF是指在特定時鐘周期內(nèi)所包含ACE的百分數(shù);針對邏輯結(jié)構(gòu),AVF是指在特定時鐘周期內(nèi)處理ACE指令集的百分數(shù).具有Nbit系統(tǒng)的AVF是指各子系統(tǒng)AVF的綜合結(jié)果,即

(1)

式中,FAVF,FAVF，i分別為分析對象和比特i的脆弱性因子;BACE,i為比特i在程序執(zhí)行過程中處于ACE位的比例;N為測試對象的比特位數(shù);W為程序執(zhí)行所需要的總的時間周期數(shù).

AVF分析的目的是對模塊內(nèi)的元素進行軟錯誤敏感性排名,以此來選擇和保護最脆弱的單元.ACE分析的優(yōu)勢是可在處理器設(shè)計階段對其進行可靠性評價;劣勢是缺少微處理器結(jié)構(gòu)的細節(jié)信息,需要手工對ACE位和un-ACE位進行分類.

采用生命周期方法對回寫式緩存中的數(shù)據(jù)訪問特性進行分析時,將讀操作分解為read和read*, 其中read表示讀取未被寫過的數(shù)據(jù),read*表示讀取已被寫過的數(shù)據(jù);將寫操作分解為write和write*,其中write表示動態(tài)死指令的寫操作,write*表示非動態(tài)死指令的寫操作.根據(jù)讀寫操作的定義及數(shù)據(jù)的訪問特性,將read-evict判定為un-ACE,將read*-evict判定為ACE.緩存生命周期分析如圖1所示.

圖1 緩存生命周期分類

針對不同緩存數(shù)據(jù)的讀寫類型,將回寫式緩存的生命周期進一步細化,得出更為準確的AVF值,為單粒子軟錯誤評估和防護措施選擇提供更為準確的依據(jù).改進后的回寫式緩存AVF生命周期分類方法見表1.

表1 回寫式緩存生命周期分類

2 馬爾科夫預(yù)測模型

AVF分析[1]和生命周期分析方法[5]未考慮使用軟錯誤防護措施后系統(tǒng)的可靠性.在這2種分析方法的基礎(chǔ)上,結(jié)合單位翻轉(zhuǎn)和時空多位翻轉(zhuǎn)的非等概率特性,提出了一種考慮ECC、刷新和交錯布局等防護措施的緩存可靠性評估方法.此處,并不簡單地認為所有載入緩存中的數(shù)據(jù)在退出之前都為敏感數(shù)據(jù),而是根據(jù)應(yīng)用程序中數(shù)據(jù)在緩存中的訪問特性,確定其是否為敏感數(shù)據(jù).這與文獻[4]有所不同,使該分析方法對特定應(yīng)用程序更有針對性.

2.1 軟錯誤效應(yīng)建模

定義1(脆弱性時鐘周期) 所有ACE時間段均為脆弱性時鐘周期VCC.

定義2(保護區(qū)域) 保護區(qū)域PD是指采用防護策略(如奇偶校驗等)所保護的存儲區(qū)域.本文考慮的保護區(qū)域為64 bit的8字節(jié)存儲單元.

定義3(刷新間隔) 刷新間隔L是指ECC防護策略執(zhí)行的時間間隔.

絕大多數(shù)的空間多位翻轉(zhuǎn)都具有聚集效應(yīng)[7-9],即軟錯誤的形式會限定在一個連續(xù)的矩陣范圍內(nèi).因此,空間多位翻轉(zhuǎn)可表示為

MMBU=Rbits×Cbits

式中,Rbits和Cbits分別表示翻轉(zhuǎn)在水平方向和垂直方向上的翻轉(zhuǎn)模式.

為簡化模型,本文只考慮2×4范圍內(nèi)的軟錯誤,這些單粒子翻轉(zhuǎn)形式數(shù)量占所有翻轉(zhuǎn)類型數(shù)量的99.668%[9]. 每個時鐘周期內(nèi),不同單粒子翻轉(zhuǎn)模式的發(fā)生概率為

(2)

式中,dx,y(x=1,2;y=1,2,3,4)表示發(fā)生x×y型空間多位翻轉(zhuǎn)的概率.

將保護單元PD在一個處理器時鐘周期內(nèi)發(fā)生單粒子翻轉(zhuǎn)的概率定義為PSEU_PD.所有時鐘周期內(nèi)發(fā)生的單粒子效應(yīng)是相互獨立的.根據(jù)文獻[9],時鐘頻率為3 GHz的處理器中保護區(qū)域發(fā)生軟錯誤的概率PSEU_PD=6.499 2×10-24.

空間多位翻轉(zhuǎn)的重疊效應(yīng)如圖2所示.如果存在單粒子翻轉(zhuǎn)重疊效應(yīng),則錯誤位會在偶數(shù)次翻轉(zhuǎn)后恢復(fù)為正確的狀態(tài).如果單粒子多位翻轉(zhuǎn)發(fā)生在垂直方向上的多個保護區(qū)域內(nèi),則會導(dǎo)致該方向上多個保護區(qū)域都發(fā)生軟錯誤.如果單粒子翻轉(zhuǎn)發(fā)生在水平方向上相鄰保護區(qū)域的交界處,則會導(dǎo)致這2個相鄰保護區(qū)域都發(fā)生單粒子翻轉(zhuǎn)效應(yīng).

(a) 第1次翻轉(zhuǎn)

(b) 第2次翻轉(zhuǎn)

(c) 重疊效應(yīng)

第1次翻轉(zhuǎn)位； 第2次翻轉(zhuǎn)位

圖2 空間多位翻轉(zhuǎn)的重疊效應(yīng)

考慮空間多位翻轉(zhuǎn)重疊效應(yīng)時,每個保護單元PD發(fā)生1～4 bit翻轉(zhuǎn)的概率為

(3)

式中,PiBU為發(fā)生ibit翻轉(zhuǎn)的概率.

空間多位翻轉(zhuǎn)具有聚集效應(yīng).在發(fā)生第1次單粒子效應(yīng)后,緩存保護區(qū)域內(nèi)所出現(xiàn)的kbit翻轉(zhuǎn)都是連續(xù)的.如果該保護區(qū)域出現(xiàn)第2次qbit單粒子效應(yīng),只可能存在以下3種情況:

1) 重疊位等于翻轉(zhuǎn)位. 如圖3(b)所示,0

(4)

式中,M為保護區(qū)域PD的位數(shù).保護區(qū)域內(nèi)軟錯誤位數(shù)減少qbit.

(a) 第1次翻轉(zhuǎn)

(b) 重疊位等于翻轉(zhuǎn)位

(c) 重疊位小于翻轉(zhuǎn)位

(d) 無重疊位

2) 重疊位小于翻轉(zhuǎn)位.如圖3(c)所示,0

(5)

3) 無重疊位.如圖3(d)所示,o=0.這種情況的發(fā)生概率為

(6)

2.2 馬爾科夫轉(zhuǎn)換模型

定義4(馬爾科夫狀態(tài)) 保護區(qū)域PD所發(fā)生翻轉(zhuǎn)的位數(shù)為馬爾科夫狀態(tài)(MS).

保護區(qū)域內(nèi)翻轉(zhuǎn)位數(shù)只與前一個時刻的狀態(tài)和當前時刻是否發(fā)生翻轉(zhuǎn)有關(guān).針對本文考慮的64 bit保護區(qū)域,共有65種馬爾科夫狀態(tài).根據(jù)軟錯誤空間多位翻轉(zhuǎn)的重疊效應(yīng),可建立不同馬氏狀態(tài)之間的轉(zhuǎn)移矩陣,具體方法見算法1.其中,m表示發(fā)生空間多位翻轉(zhuǎn)位數(shù)的最大值;tk,k+d表示翻轉(zhuǎn)后保護區(qū)域內(nèi)增加或減少dbit的概率.

算法1 馬爾科夫轉(zhuǎn)換矩陣生成算法

輸入:軟錯誤發(fā)生率piBU. 輸出:馬爾科夫轉(zhuǎn)換矩陣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轉(zhuǎn)變?yōu)镸S0的概率增加1/L,即增加刷新策略后,可得

(7)

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

(8)

根據(jù)算法1、式(7)和 (8)可以建立不同馬氏狀態(tài)之間的轉(zhuǎn)換矩陣,那么從MSk轉(zhuǎn)換到MSk+d所持續(xù)的時間等于這2個狀態(tài)之間的轉(zhuǎn)換次數(shù)乘以處理器時鐘周期數(shù),緩存固有平均無故障時間MTTFin=ZMS0→MSkY,其中，ZMS0→MSk表示從狀態(tài)MS0到狀態(tài)MSk的轉(zhuǎn)換次數(shù),Y表示處理器時鐘周期.整個應(yīng)用程序的平均無故障時間MTTF=MTTFin/FAVF.

轉(zhuǎn)換矩陣T為

(9)

式中,子矩陣S2u+1為帶狀矩陣;IN-2u為單位矩陣,其中的對角元素表示馬氏鏈的吸收狀態(tài).

由式(9)可以得出

(10)

使用SEC型ECC防護措施后的緩存,從無翻轉(zhuǎn)狀態(tài)MS0轉(zhuǎn)換為狀態(tài)MSk(k≥2),即說明緩存已處于失效狀態(tài).同理可以得出,針對DEC和TEC到達失效狀態(tài)MSk時,k分別滿足k≥3和k≥4.考慮ECC防護策略后的轉(zhuǎn)換矩陣為

(11)

在具有吸收狀態(tài)的馬爾科夫鏈中,存在基矩陣F=(I-T′)-1.對于具有標準形式T的轉(zhuǎn)移矩陣的吸收鏈有以下定理[10]:

定理1 吸收鏈的基矩陣F中的每個元素,表示從一個非吸收狀態(tài)出發(fā),經(jīng)過逐步變換后到達每個非吸收狀態(tài)的平均轉(zhuǎn)移次數(shù).

定理2 設(shè)W=FH,其中H={1，1，…，1}T,則W中每個元素表示從非吸收狀態(tài)出發(fā),到達某個吸收狀態(tài)被吸收之前的平均轉(zhuǎn)移次數(shù).

根據(jù)定理1和定理2, 基于算法1所建立的轉(zhuǎn)換矩陣T,可以利用非吸收狀態(tài)保持時間來計算保護區(qū)域PD的固有平均無故障時間MTTFin.結(jié)合不同應(yīng)用程序的FAVF,即可得出不同應(yīng)用程序在ECC防護及刷新策略下的系統(tǒng)平均無故障時間MTTF.

2.3 交錯布局下的時空多位翻轉(zhuǎn)

高可靠存儲單元采用交錯布局技術(shù),將邏輯上相鄰的存儲位在物理布局上進行分隔.具有交錯布局防護措施的軟錯誤發(fā)生示例如圖4所示.

翻轉(zhuǎn)位； 分隔位

圖4 交錯布局下的空間多位翻轉(zhuǎn)

假設(shè)隨機變量w為保護區(qū)域內(nèi)可防護軟錯誤的位數(shù);mac為系統(tǒng)失效時保護區(qū)域內(nèi)發(fā)生軟錯誤的位數(shù);g為系統(tǒng)失效時保護區(qū)域內(nèi)發(fā)生單粒子翻轉(zhuǎn)的次數(shù).則mac的數(shù)學(xué)期望為

(12)

式中,qv為第v次翻轉(zhuǎn)產(chǎn)生的軟錯誤位數(shù);E(qv)為時空多位翻轉(zhuǎn)產(chǎn)生軟錯誤位數(shù)的平均數(shù).

在泊松分布下,MTTF與METF之間存在如下關(guān)系:

(13)

式中,METF=E(g);λ為軟錯誤發(fā)生率.

由此可得

(14)

在交錯布局的防護措施下,緩存平均無故障時間在單位翻轉(zhuǎn)和多位翻轉(zhuǎn)之間存在如下關(guān)系:

(15)

綜上所述,當存儲單元采用交錯布局防護技術(shù)時,通過改變軟錯誤發(fā)生率λ,可以利用單位翻轉(zhuǎn)來預(yù)估時空多位翻轉(zhuǎn)的平均無故障時間.

3 仿真實驗及結(jié)果分析

3.1 實驗環(huán)境

本文將改進的AVF評估方法應(yīng)用到通用的Sim-Alpha處理器模擬環(huán)境中,并采用標準的SPEC2000測試程序?qū)彺娴目煽啃赃M行評估,采用參考輸入集并使用SimPoints工具[11]每間隔50 Mbit進行取樣.

3.2 L2級緩存精確分析

圖5為根據(jù)本文方法與開源軟件Sim-SODA所得的AVF對比.由圖可知,采用本文方法進行AVF分析時,read*-evict使AVF平均增加1.46%,read*-end-evict使AVF平均增加1.45%.考慮到動態(tài)死指令對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%時的結(jié)果見表2．分析了不同防護策略(SECDED, DECTED,TECQED)的有效性,并將所得數(shù)據(jù)與文獻[5,12]進行對比,以驗證模型的正確性.采用ECC檢錯糾錯碼可有效提高緩存的可靠性(至少提高5個數(shù)量級);刷新能夠顯著提高緩存的可靠性,但是刷新頻率過高則對可靠性的提高并不明顯.因此,可以在刷新代價和可靠性目標之間進行均衡,選擇較為合適的刷新頻率.采用交錯布局技術(shù)可以顯著提高緩存的可靠性,相對于DECTED和TECQED兩種防護策略,交錯布局策略可以獲得更高的系統(tǒng)可靠性.

表2 防護策略下程序平均無故障時間

4 結(jié)語

本文在現(xiàn)有緩存可靠性分析方法的基礎(chǔ)上,利用改進的AVF評估方法,對緩存AVF進行定性的生命周期分析和定量的脆弱性分析. 根據(jù)緩存所使用的ECC和交錯布局等防護措施,對真實場景下的軟錯誤發(fā)生概率和模式進行合理假設(shè),并提出了一種基于馬爾科夫狀態(tài)轉(zhuǎn)換的可靠性評估方法.該方法不僅可以對目前占軟錯誤比率最多的單位翻轉(zhuǎn)的緩存可靠性進行評估,也能對非等概率條件下具有單位翻轉(zhuǎn)、時空多位翻轉(zhuǎn)累積效應(yīng)的緩存可靠性進行評估,具有一定的通用性.最后,利用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]陳東彥, 李冬梅, 王樹忠. 數(shù)學(xué)建模[M]. 北京：科學(xué)出版社, 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—),男,博士生;汪蕓(聯(lián)系人),女,博士,教授,博士生導(dǎo)師，yunwang@seu.edu.cn

王輝，汪蕓，馬駿馳.一種考慮防護措施的緩存可靠性評估方法[J].東南大學(xué)學(xué)報:自然科學(xué)版,2015,45(1):17-22.

10.3969/j.issn.1001-0505.2015.01.004

TP302.8

A

1001-0505(2015)01-0017-06