張 磊,彭 飛,曹子寧,莊 毅

(南京航空航天大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心,南京 211106)

1 引 言

宇宙高能粒子輻射引起的計算機硬件的瞬時故障會導(dǎo)致軟錯誤[1],如α粒子和高能中子.這種粒子的撞擊持續(xù)時間很短,但會造成P-N結(jié)翻轉(zhuǎn),從而引起存儲元件的位翻轉(zhuǎn)或中斷組合邏輯電路的異常操作,這種現(xiàn)象稱為單粒子翻轉(zhuǎn)(Single Event Upset,SEU).這可能會影響應(yīng)用程序的輸出,甚至使計算機系統(tǒng)崩潰.工作在輻射環(huán)境中的SRAM單元很容易發(fā)生這種錯誤.目前已有通過電路設(shè)計和錯誤檢查碼(ECC)等技術(shù)來提高其恢復(fù)能力.隨著處理器尺寸的減小和電源電壓的降低,技術(shù)的發(fā)展為處理器提供了更好的性能和能效,但是這又使得計算機系統(tǒng)更容易受到軟錯誤的影響,對可靠性提出了重大挑戰(zhàn).

目前已有不少針對軟錯誤的硬件和軟件檢測方法.例如高速緩存,大型SRAM陣列均有較高的軟錯誤率(Soft Error Rate,SER),這已經(jīng)通過電路技術(shù)和使用校驗驗碼來解決.已有的研究表明,SRAM的SER在幾代技術(shù)中大致保持不變,一般為10-4FIT/bit[2].組合邏輯電路更能抵抗由于錯誤掩蔽而引起的瞬時故障,即使存在軟錯誤,邏輯電路的輸出值也可能不會改變,在結(jié)果被鎖定之前,電路也可以自己從錯誤中“恢復(fù)”.鎖存器和組合邏輯電路的SER范圍從10-5～10-3,每個芯片每年大約有0.5次故障[3].盡管未來的處理器可能在所有鎖存器上都有奇偶校驗,但是這也引起較大的面積和功耗開銷,并且額外校驗位的引入也會提升錯誤率,因此這些錯誤很難檢測到,即使在硬件中可以檢測到也很難糾正[4].

基于硬件的解決方案在性能方面十分有效,通常開銷在5%～10%之間.然而對于目前市場的利潤是十分昂貴的,并且也不能做到萬無一失.為了克服這些缺點,可以通過軟件實現(xiàn)容錯(Software Implemented Hardware Fault Tolerance,SIHFT)來替換或加強硬件冗余.這種方法的另一個好處是可以有選擇地應(yīng)用,例如對于一個系統(tǒng)的所有執(zhí)行計算,中斷控制程序和多媒體應(yīng)用程序是較為重要的.通過使用SIHFT,可以忽略非重要應(yīng)用程序加固,并僅將其應(yīng)用于重要應(yīng)用程序.

軟錯誤會對計算機系統(tǒng)產(chǎn)生不同的影響,例如系統(tǒng)崩潰、超時、SDC(Silent Data Corruption)等,其中SDC問題是可靠性領(lǐng)域一直以來研究的重點之一.當SDC發(fā)生時,程序正常執(zhí)行,但是輸出結(jié)果不正確.已有方法主要是通過軟件方法對發(fā)生SDC概率高的指令保護,從而減少整個系統(tǒng)的SDC錯誤.

軟件實現(xiàn)的數(shù)據(jù)流錯誤檢測方法主要是通過冗余執(zhí)行來實現(xiàn)錯誤檢測,但這會帶來很大的開銷問題.在硬件迅速發(fā)展的時代,可以在軟件層利用多核并行、SIMD數(shù)據(jù)并行等能力來加速程序地執(zhí)行效率,這是已有方法所忽略的地方.本文運用SIMD指令將原計算和冗余計算向量化實現(xiàn)并行處理,必須解決如下兩個挑戰(zhàn):

1)難以將程序中不同數(shù)據(jù)類型向量化.通常一個程序中存在一些不同類型的數(shù)據(jù),例如整型、浮點型、數(shù)組、結(jié)構(gòu)體.如何將這些類型的原始數(shù)據(jù)和冗余數(shù)據(jù)向量化,并在訪問它們時以一個向量訪問操作完成讀取數(shù)據(jù)操作,是一個待解決的問題.

2)難以將標量與向量數(shù)據(jù)的指令向量化處理.對原數(shù)據(jù)和冗余數(shù)據(jù)進行向量化后,對其原始的標量操作需轉(zhuǎn)化為向量操作.因完全冗余帶來的巨大開銷,通常不會采取完全冗余的策略,如何兼容向量與非向量數(shù)據(jù)間操作是性能提升的一個關(guān)鍵問題.

針對已有的基于冗余復(fù)制的數(shù)據(jù)流軟錯誤檢測算法開銷大的問題,本文提出了一種基于SIMD(Single Instruction Multiple Data)向量化的數(shù)據(jù)流軟錯誤檢測算法(Vectorization-Based Soft Error Detection,VBSED),對原數(shù)據(jù)和冗余數(shù)據(jù)進行處理向量化處理,生成向量數(shù)據(jù);進一步,使用SIMD指令執(zhí)行向量數(shù)據(jù),從而提高加固后程序的性能.目前大多數(shù)主流商業(yè)處理器CPU都支持SIMD指令.例如Intel x86的SSE/AVX,ARM NEON.本文的主要貢獻有:1)定義程序數(shù)據(jù)在向量環(huán)境下的向量格式,設(shè)計了標量數(shù)據(jù)到向量數(shù)據(jù)的轉(zhuǎn)化規(guī)則;2)提出基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法,對源程序在中間代碼層自動進行向量化處理.在Mibench測試程序上的實驗結(jié)果表明,本文提出的算法比已有數(shù)據(jù)流冗余算法有更好的檢錯能力和更低的性能開銷.VBSED算法相較于已有的數(shù)據(jù)流軟錯誤檢測算法具有的下列優(yōu)點:

1)利用數(shù)據(jù)并行性的特性,可提高加固后程序的性能;

2)減少了加固后程序代碼空間開銷;

3)考慮了Cache和內(nèi)存發(fā)生錯誤,具有檢測緩存等部件軟錯誤的優(yōu)點,這是現(xiàn)有算法一般不具有的能力,提高了檢錯能力.

本文的其余部分組織如下.第2節(jié)介紹了相關(guān)研究工作;第3節(jié)詳細介紹了VBSED算法的設(shè)計,包括算法整體框架,數(shù)據(jù)與指令向量化規(guī)則,錯誤檢測代碼生成規(guī)則;第4節(jié)進行了相關(guān)對比實驗;第5節(jié)給出了本文結(jié)論.

2 相關(guān)工作

目前針對軟錯誤檢測的方法主要分為兩類:基于硬件的錯誤檢測方法和基于軟件的錯誤檢測方法.

基于硬件的錯誤檢測方法大多數(shù)是通過修改或擴展硬件模塊來達到檢測錯誤目的,而修改硬件模塊是一件困難的工作,因此主流的方法是通過添加額外的硬件電路.典型的雙模冗余和三模冗余是通過硬件冗余技術(shù),并驗證運行結(jié)果的一致性來判斷故障的發(fā)生.Diva等人使用一個不完全的有序檢查器[5],到達重排序緩存的指令,包括相關(guān)的輸入和推測的結(jié)果,將按程序順序被移動到檢查器進行檢測,但是這個方法的弊端是檢查器數(shù)量會隨著主內(nèi)核功能單元數(shù)量而增多.Nathan等人針對超標量、亂序執(zhí)行處理器核設(shè)計了一種低開銷的方法[6],它在每一條指令在解碼階段就預(yù)測當前指令所做的操作,隨后記錄指令執(zhí)行階段操作,驗證預(yù)測和實際運行結(jié)果是否一致,從而檢測每一條指令發(fā)生的錯誤.

盡管硬件的方法可以帶來很好的性能,但是成本和難度卻很大.基于軟件的錯誤檢測方法實現(xiàn)較為簡單且成本低,主要分為控制流檢測方法和數(shù)據(jù)流檢測方法兩類.CFCSS(Control Flow Checking by Software Signatures)[7]是經(jīng)典的控制流檢測方法,它將程序劃分為一系列基本塊,把基本塊和控制流跳轉(zhuǎn)關(guān)系抽象為控制流圖,通過在圖中各個基本塊頭添加驗證標簽來檢測控制流錯誤,該方法具有較高的控制流錯誤檢測率,且開銷很低,缺點是無法檢測到塊內(nèi)的控制流錯誤.Vankeirsbilck[8],Zheng[9]等人在CFCSS的基礎(chǔ)上進行了改進,在基本塊內(nèi)添加額外的標簽和利用多層分段標簽來檢測塊內(nèi)的控制流錯誤,從而提高檢測率.

EDDI(Error Detection by Duplicated Instructions)是一個典型的數(shù)據(jù)流錯誤檢測方法[10],它復(fù)制程序基本塊中所有指令,并在存儲指令和分支指令之前插入比較指令,用于比較原指令和復(fù)制指令的值.然而這種方法開銷巨大.Reis[11],Eduardo[12],Thati[13],Ko[14]等人對EDDI提出了改進的方法,對全冗余復(fù)制方法帶來的開銷問題進行了改進,設(shè)計了可選擇指令復(fù)制和可選擇檢查指令插入機制.Chen提出利用SIMD指令提升冗余執(zhí)行效率的思想[15],將原數(shù)據(jù)復(fù)制一份并與原數(shù)據(jù)打包到向量寄存器,隨后用SIMD指令完成對向量寄存器運算,但是該方法只考慮寄存器上的錯誤,且數(shù)據(jù)打包操作會帶來很大的性能開銷.Zhang[16],Yang[17]等人提出了選擇性保護方法,允許在用戶指定的開銷范圍內(nèi)有選擇地保護程序中易發(fā)生SDC的指令,首先提取程序指令中靜態(tài)和動態(tài)特征,通過建立回歸樹和隨機森林預(yù)測模型來預(yù)測程序指令的SDC脆弱性,進而利用指令的SDC脆弱性選擇重要指令冗余,在保證高檢錯率的前提下減少冗余開銷.

3 基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法設(shè)計

3.1 基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法框架

本文設(shè)計的基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法框架由源碼編譯、預(yù)處理分析、向量化加固3個階段組成,框架如圖1所示.

提出的基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法框架(VBSED)是一個由源碼到最終加固代碼的自動化處理過程.首先源碼經(jīng)過編譯生成中間代碼[18,19],然后預(yù)處理分析對中間代碼中的指令構(gòu)建數(shù)據(jù)流依賴圖[20],通過拓撲排序?qū)?shù)據(jù)流依賴圖進行排序,得到指令依賴順序.向量化加固是本文算法的核心,通過使用SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法對目標程序進行加固,VBSED對預(yù)處理后程序進行數(shù)據(jù)向量化和指令向量化處理[21,22],并在檢查點位置比較向量數(shù)據(jù)中原數(shù)據(jù)和冗余數(shù)據(jù)進行錯誤檢測.為了讓本文算法具有更高的靈活性和可配置性,用戶可以制定重要數(shù)據(jù)和檢查點規(guī)則配置,在時間開銷與空間開銷之間作調(diào)整,得到不同粒度的加固結(jié)果.

圖1 基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法框架Fig.1 VBSED algorithm framework

本文的算法基于LLVM[23]開發(fā)的編譯器工具,實現(xiàn)完全編譯自動化,無需人工修改程序.基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法流程如圖2所示,分為兩個階段:

圖2 基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法流程Fig.2 VBSED algorithm process

1)程序預(yù)處理階段

給定一個目標源程序,首先由Clang編譯器將其編譯成LLVM中間代碼,并構(gòu)建控制流圖和數(shù)據(jù)流指令依賴關(guān)系分析,得到指令依賴順序,為加固階段做準備.

2)程序加固階段

程序加固階段分為如下4個階段:

a)數(shù)據(jù)向量化

此階段首先根據(jù)用戶指定的加固策略,對用戶指定的重要數(shù)據(jù)保護,對這些數(shù)據(jù)應(yīng)用相應(yīng)的數(shù)據(jù)向量化規(guī)則.

b)指令向量化

按指令依賴關(guān)系順序依次處理每條指令,對其應(yīng)用相應(yīng)的指令向量化規(guī)則.

c)添加檢查點

根據(jù)加固策略中的檢查點規(guī)則應(yīng)用相應(yīng)的檢查點規(guī)則,生成錯誤檢測代碼,將存在于向量中的原數(shù)據(jù)和冗余數(shù)據(jù)做比較以實現(xiàn)錯誤檢測功能.

d)生成可執(zhí)行程序

對完成前3個階段后的代碼編譯鏈接,最后生成具有數(shù)據(jù)流檢錯能力的目標程序.

3.2 相關(guān)定義

本文中,首先給出以下相關(guān)定義:

定義1.數(shù)據(jù)(Data,D):數(shù)據(jù)在程序中分為4類,有標量類型,向量類型,數(shù)組類型和結(jié)構(gòu)體類型.

1)標量類型數(shù)據(jù)Db:,該元組表示數(shù)據(jù)類型為type,數(shù)據(jù)的值是value.基本標量數(shù)據(jù)類型有byte,char,short,int,long,float,double.

2)向量類型數(shù)據(jù)VD:<(value1,…,valueM),type>,該向量表示包含M個類型為type的元素.

3)數(shù)組Darr:{Db1,Db2,…,Dbn},n≥1,表示n個元素Db的集合,且其中Dbi的type都相同.

4)結(jié)構(gòu)體Dst:{Db1,…,Dbi,…,Dbn,Darr1,…,Darrj,…,Darrm},n×m>0,n≥0,m≥0,表示由Db和Darr組成的復(fù)合數(shù)據(jù),其中Dbi與Darrj的type不作限制.如Dbi的type為int,Darrj的type為float,其中0

定義2.指令(Instruction,I):將指令I(lǐng)分成如下5種類型,并給出對應(yīng)格式:

1)運算指令I(lǐng)arith:,該元組所表達的語義為dest=od1opod2,其中od1,od2為指令I(lǐng)arith的操作數(shù),dest為結(jié)果數(shù).

2)加載指令I(lǐng)ld:,該元組所表達的語義為將內(nèi)存地址為addr處的值存放到變量val中.

3)存儲指令I(lǐng)st:,該元組所表達的語義為將val的值存儲到地址為addr內(nèi)存處.

4)跳轉(zhuǎn)指令I(lǐng)jmp:,該元組所表達的語義為當cond條件為真時,程序跳轉(zhuǎn)到tgt處執(zhí)行.

5)其他指令I(lǐng)ot:,op,為操作數(shù),odi為指令的操作數(shù).

定義3.數(shù)據(jù)流指令依賴關(guān)系:程序中指令序列I={I1,I2,…,In},若存在Ij操作數(shù)odt為指令I(lǐng)i結(jié)果數(shù),則稱指令I(lǐng)j依賴指令I(lǐng)i,表示為Dep(Ii,Ij).

3.3 數(shù)據(jù)與指令向量化規(guī)則設(shè)計

本文設(shè)計的標量數(shù)據(jù)轉(zhuǎn)換為向量數(shù)據(jù)的規(guī)則如下:

規(guī)則1.基本類型數(shù)據(jù)向量化轉(zhuǎn)換規(guī)則VEC_D_B(Db,K),定義見式(1).Db為應(yīng)用該規(guī)則的數(shù)據(jù),K為轉(zhuǎn)換后向量的長度,下文表示相同.對于任意Db=,有:

VEC_D_B(Db,K):

VDb=<(value1,…,valueK),type>

(1)

其中valuei=value,1≤i≤K.

規(guī)則2.數(shù)組向量化轉(zhuǎn)換規(guī)則VEC_D_ARR(Darr,K),定義見式(2).Darr為應(yīng)用該規(guī)則的數(shù)組.對于任意Darr={Db1,Db2,…,Dbn},有:

VEC_D_ARR(Darr,K):

VDarr={VDbj|VDbj=VEC_D_B(Dbi,K),Dbi∈Darr}

(2)

規(guī)則3.結(jié)構(gòu)體向量化轉(zhuǎn)化規(guī)則VEC_D_ST(Dst,K),定義見式(3).Dst為應(yīng)用該規(guī)則的結(jié)構(gòu)體.對于任意Dst:{Dbi,…,Dbn,Darrj,…,Darrm},n×m>0,n≥0,m≥0,0≤i≤n,0≤j≤m,有:

VEC_D_ST(Dst,K):

VDst={VDbi|VEC_D_B(Dbi,K),Dbi∈Dst}∪
{VDarrj|Darrj=VEC_D_ARR(Darrj,K),Darri∈Dst}

(3)

結(jié)構(gòu)體是由基本類型數(shù)據(jù)和數(shù)組組合成的復(fù)合類型數(shù)據(jù),對其應(yīng)用向量化規(guī)則,需對它的所有基本類型數(shù)據(jù)Db應(yīng)用規(guī)則1,對所有數(shù)組數(shù)據(jù)應(yīng)用規(guī)則2.例如結(jié)構(gòu)體數(shù)據(jù)Dst={Db1,Db2,Darr},對Dst應(yīng)用規(guī)則3,需對Db1和Db2和分別應(yīng)用規(guī)則1,對Darr應(yīng)用規(guī)則2,因此對Dst向量化后的向量數(shù)據(jù)VDst={VDb1,VDb2,VDarr}.

上述定義的3種規(guī)則是將原數(shù)據(jù)和冗余數(shù)據(jù)用向量表示,例如對于基本類型數(shù)據(jù)Db=向量化后的數(shù)據(jù)VDb=<(value1,…,valueK),type>,VDb中value1與Db中原數(shù)據(jù)value對應(yīng),value2,…,valueK為冗余數(shù)據(jù),其中K-1為冗余數(shù)量,由用戶決定.規(guī)則2對數(shù)組的基本類型數(shù)據(jù)向量化,規(guī)則3對結(jié)構(gòu)體中基本類型數(shù)據(jù)和數(shù)組分別應(yīng)用規(guī)則1和規(guī)則2,這樣做是為了把原數(shù)據(jù)和冗余數(shù)據(jù)相鄰排列,在實現(xiàn)中根據(jù)排列將向量數(shù)據(jù)在內(nèi)存中排列,提高數(shù)據(jù)訪問效率.

SISD(Single Instruction Single Data)指令中的寄存器是標量類型的,其中數(shù)據(jù)為基本類型數(shù)據(jù)Db,將SISD指令向量化需要將指令中的數(shù)據(jù)也向量化,根據(jù)上一節(jié)定義的指令類型,本文定義的算術(shù)指令、加載指令、存儲指令向量化規(guī)則如下:

規(guī)則4.算術(shù)指令向量化規(guī)則VEC_I_ARITH(Iarith,K),定義見式(4).Iarith為應(yīng)用該規(guī)則的算術(shù)指令.對于任意Iarith:,有:

VEC_I_ARITH(Iarith,K):

VIarith==
VEC_D_B(dest,K)>

(4)

其中vop是op的向量運算,od1,od2,dest是Db數(shù)據(jù),vod1,vod2,vdest分別為對應(yīng)的VDb數(shù)據(jù).K表示對此指令中數(shù)據(jù)向量化的長度.運用該規(guī)則,可將運算op向量化為vop,在執(zhí)行對向量數(shù)據(jù)vod1和vod2運算,可并行對向量中每一個運算.

規(guī)則5.加載指令向量化規(guī)則VEC_I_LD(Ild,K),定義見式(5).Ild為應(yīng)用該規(guī)則的加載指令.對于任意Ild:,有:

VEC_I_LD(Ild,K):

VIld==

(5)

其中vload是向量加載操作,從內(nèi)存地址addr處讀取一個向量.val是Db數(shù)據(jù),vval為對應(yīng)向量類型VDb數(shù)據(jù).K表示對此指令中數(shù)據(jù)向量化的長度.運用該規(guī)則,可將加載指令load向量化為vload,在執(zhí)行加載地址addr處向量數(shù)據(jù),可并行加載向量數(shù)據(jù)中每一個元素.

規(guī)則6.存儲指令向量化規(guī)則VEC_I_ST(Ist,K),定義見式(6).Ist為應(yīng)用該規(guī)則的加載指令.對于任意Ist:,有:

VEC_I_ST(Ist,K):

VIst==

(6)

其中vstore向量加載操作,將一個向量存儲到內(nèi)存地址addr處.val是Db數(shù)據(jù),vval為對應(yīng)向量類型VDb數(shù)據(jù).K表示對此指令中數(shù)據(jù)向量化的長度.運用該規(guī)則,可將存儲指令store向量化為vstore,在執(zhí)行將向量數(shù)據(jù)存儲到addr處,可并行存儲向量數(shù)據(jù)中每一個元素.

在標量計算、函數(shù)返回、函數(shù)調(diào)用處依然使用標量數(shù)據(jù),這些地方需將原向量數(shù)據(jù)VDb轉(zhuǎn)換成標量數(shù)據(jù),下面定義向量數(shù)據(jù)轉(zhuǎn)換為標量規(guī)則.

規(guī)則7.向量數(shù)據(jù)轉(zhuǎn)換為標量數(shù)據(jù)規(guī)則DEVEC_VD_B(VDb,Idx),定義見式(7).VDb為應(yīng)用該規(guī)則的向量數(shù)據(jù),Idx是該規(guī)則返回向量數(shù)中的基本類型數(shù)據(jù)的索引.對于任意VDb=<{value1,…,valueK},type>,有:

DEVEC_VD_B(VDb,Idx):Db=

(7)

3.4 錯誤檢測代碼生成規(guī)則

應(yīng)用上一小節(jié)規(guī)則1～規(guī)則7后,可實現(xiàn)原數(shù)據(jù)運算與冗余運算轉(zhuǎn)換為向量運算的并行計算,但是此程序不具有錯誤檢測能力.本節(jié)給出VBSED算法中錯誤檢測代碼生成規(guī)則,用于在一些檢查點位置生成錯誤檢測代碼,比較向量數(shù)據(jù)中原數(shù)據(jù)與冗余數(shù)據(jù)來檢查錯誤,本文算法可以在四種情況下生成錯誤檢測代碼.本文還設(shè)計了可配置的檢查點生成規(guī)則,用戶可指定檢查點位置,可選擇性地在以下四種位置處生成錯誤檢測代碼.

1)條件分支:若條件判斷數(shù)據(jù)是一個向量數(shù)據(jù),從向量中提取數(shù)原數(shù)據(jù)前,檢查向量中數(shù)據(jù)是否一致.

2)加載操作:當從內(nèi)存中讀取一個向量數(shù)據(jù)后,檢查向量數(shù)據(jù)是否在內(nèi)存或Cache中發(fā)生錯誤.

3)存儲操作:將一個向量數(shù)據(jù)存儲到內(nèi)存前,檢查向量中數(shù)據(jù)是否一致.

4)函數(shù)調(diào)用:在調(diào)用另一個函數(shù)前檢查所有的參數(shù),若函數(shù)形參存在向量化數(shù)據(jù),則對向量化的形參數(shù)據(jù)生成錯誤檢查代碼.

根據(jù)上述4種情況,本文設(shè)計了4個檢查點規(guī)則,如表1所示.

表1 檢查點規(guī)則Table 1 CheckPoint

3.5 錯誤檢測代碼生成規(guī)則

本文提出的基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法主要思想是針對冗余執(zhí)行的數(shù)據(jù)流算法效率低下問題,通過利用硬件SIMD數(shù)據(jù)并行性提升程序性能,設(shè)計了數(shù)據(jù)和指令化規(guī)則,對程序完成向量化處理,最后根據(jù)檢查點規(guī)則在相應(yīng)位置生成錯誤檢測代碼,實現(xiàn)錯誤檢測功能.本文提到的向量化數(shù)據(jù)為程序中變量,用戶可以有選擇性的對重要變量進行向量化保護,從而避免因?qū)λ凶兞繑?shù)據(jù)向量化帶來較大的空間開銷問題.在對變量數(shù)據(jù)向量化處理后,程序中存在向量數(shù)據(jù)和標量數(shù)據(jù),指令向量化規(guī)則會生成對這些數(shù)據(jù)操作的指令,以完成對數(shù)據(jù)正確操作.

該算法的輸入是C語言源程序,由編譯器將源程序轉(zhuǎn)換生成LLVM中間代碼,再根據(jù)3.3節(jié)中的規(guī)則對程序中的變量數(shù)據(jù)和指令進行向量化,然后在檢查點位置生成錯誤檢測代碼,最終生成具有錯誤檢測能力高效的加固程序,具體的步驟如下:

Step 1.將源程序編譯成中間代碼;

Step 2.根據(jù)用戶給定的重要數(shù)據(jù)選擇需向量化的數(shù)據(jù),即程序中的變量,判斷變量數(shù)據(jù)的類型,應(yīng)用數(shù)據(jù)向量化規(guī)則1～規(guī)則3得到向量化數(shù)據(jù);

Step 3.將程序按基本塊劃分,構(gòu)建基本塊控制流圖;

Step 4.將基本塊內(nèi)的內(nèi)指令根據(jù)指令依賴關(guān)系構(gòu)建指令依賴的有向無環(huán)圖,對此有向無環(huán)圖通過拓撲排序生成指令依賴順序;

Step 5.按指令依賴關(guān)系依次處理每條指令,使用指令向量化規(guī)則得到向量化指令.若該指令為算術(shù)指令,指令中操作數(shù)均為已向量化數(shù)據(jù),對該指令應(yīng)用規(guī)則4.若該指令為加載指令,加載地址處的數(shù)據(jù)為已向量化數(shù)據(jù),對該指令應(yīng)用規(guī)則5.若該指令為存儲指令,所存儲的數(shù)據(jù)為向量數(shù)據(jù),對該指令應(yīng)用規(guī)則6;

Step 6.根據(jù)用戶指定的檢查點規(guī)則和3.4小節(jié)中錯誤檢測代碼生成規(guī)則,在條件分支、加載操作、存儲操作和函數(shù)調(diào)用位置處生成錯誤檢測代碼.

提出的基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法無法完成對程序中所有指令向量化,本文算法針對數(shù)據(jù)訪問指令和常見運算指令作向量化,例如加法、減法、乘法等指令.下面用一個快速排序程序的例子來應(yīng)用本文提出的基于向量化的數(shù)據(jù)流軟錯誤檢測算法,詳細解釋原始程序的中間代碼在應(yīng)用本文提出的向量化規(guī)則后,生成向量化代碼,本文實例中向量化長度K=2,即冗余一份原數(shù)據(jù).

圖3 應(yīng)用規(guī)則和生成錯誤檢測代碼示例Fig.3 Example of rule and error detecion

如圖3所示,將程序中數(shù)組數(shù)據(jù)向量化,實例中數(shù)組是包含8000個整數(shù)標量的一維數(shù)組,根據(jù)3.4節(jié)中規(guī)則2,經(jīng)過轉(zhuǎn)換后生成一個包含8000個長度為2的整數(shù)向量的數(shù)組.圖3中規(guī)則1將5個整數(shù)標量數(shù)據(jù)轉(zhuǎn)換為5個長度為2的整數(shù)向量.圖3中展示了應(yīng)用規(guī)則5的示例,因為變量數(shù)據(jù)i,j已經(jīng)被轉(zhuǎn)換為向量數(shù)據(jù),所以此處load轉(zhuǎn)換為對應(yīng)的向量操作.圖3中還展示了應(yīng)用規(guī)則4、規(guī)則6和生成錯誤檢查代碼的示例,規(guī)則4和規(guī)則6與規(guī)則5應(yīng)用類似,add,store對向量數(shù)據(jù)的操作需轉(zhuǎn)換為對應(yīng)向量操作.根據(jù)3.4小節(jié)規(guī)則在存儲指令之前生成錯誤檢測代碼,將向量中第1個元素(原數(shù)據(jù))和第2個元素(冗余數(shù)據(jù))比較,實現(xiàn)錯誤檢測功能.

4 實驗結(jié)果與分析

4.1 實驗環(huán)境配置

本文構(gòu)建了故障注入仿真實驗平臺[24].課題組基于Gem5[25]仿真工具進行了二次開發(fā),該平臺具有模擬寄存器、存儲器、緩存故障等功能,在此平臺上對EDDI與VBSED算法的錯誤檢測率等方面進行對比實驗.在PC機上對VBSED算法生成的程序進行時空開銷實驗評估.使用的實驗環(huán)境配置如下:CPU為Intel(R)Core(TM)i7-6700HQ,支持SSE3/AVX[26],2.6GHz.內(nèi)存16G.操作系統(tǒng)Ubuntu16.04,基于LLVM7.1開發(fā)了基于SIMD向量化錯誤檢測的程序轉(zhuǎn)換工具.此外本文還基于同版本LLVM復(fù)現(xiàn)了EDDI算法,用于在同樣環(huán)境作為與本文算法比較的對象.

測試程序本文選擇MiBench[27]中QSORT、CRC、RAD2DEG、FFT 4個測試程序和深度學(xué)習(xí)中CONV2D、MatMul兩個常見的算子,用這些程序來對比上述兩個算法的時空開銷和錯誤檢測率.

4.2 實驗結(jié)果分析

1)時空開銷對比

首先將上述6個測試程序分別經(jīng)EDDI算法和本文的VBSED算法處理后生成具有錯誤檢測功能的程序,此外生成一個未使用任何加固算法的程序(UnProtected,UP)作為對比基準程序.空間開銷對比這些程序在硬盤上所占空間大小,時間開銷對比這些程序平均運行時間.EDDI、VBSED、UP 3類程序的時空開銷如圖4所示.從實驗結(jié)果中可以看出,現(xiàn)有的

圖4 EDDI、VBSED、UP 3類程序時空開銷對比Fig.4 Comparison of time and space cost

EDDI算法在時間開銷方面是UP程序的2.2～5.1倍,這一大部分原因是因為EDDI完全復(fù)制指令帶來寄存器壓力,從而產(chǎn)生大量的訪存操作,導(dǎo)致時間開銷增加.而本文提出的VBSED主要的時間開銷來源于錯誤檢查代碼,這是一些比較指令和跳轉(zhuǎn)指令,而跳轉(zhuǎn)指令在x86體系結(jié)構(gòu)中會影響指令流水線執(zhí)行,不可避免地降低性能.其中QSORT是訪存密集型程序,EDDI算法產(chǎn)生寄存器壓力的弊端在此程序體現(xiàn)更加明顯,從圖4中可以看出EDDI算法在QSORT測試程序上時間開銷是UP程序的5倍多,而本文算法通過向量化并行計算,有效的減少了時間開銷.在空間開銷方面,VBSED算法相較少于EDDI算法生成的程序空間大小,這是因為EDDI算法是復(fù)制原始程序指令產(chǎn)生冗余執(zhí)行指令,而本文算法相較于EDDI算法是把原指令和冗余指令向量化成一條指令,減少了大量冗余指令.雖然VBSED會產(chǎn)生少量的向量與標量轉(zhuǎn)換指令,但這些并不會帶來顯著的空間開銷.

2)錯誤檢測率對比

VBSED算法不僅降低了時空開銷,還具有較高錯誤檢測率.本文對Gem5仿真工具進行二次開發(fā),實現(xiàn)仿真故障注入平臺,具有對寄存器、緩存、內(nèi)存等故障注入功能,對每一組對比實驗進行3000次故障注入.本文將故障注入結(jié)果分為5類:

a)CORRECT:程序運行結(jié)果正確;

b)DETECTED:檢錯算法檢測到錯誤;

c)ERROR:操作系統(tǒng)檢測到錯誤;

d)SDC:未檢測到的錯誤,程序正常運行結(jié)束,但結(jié)果輸出錯誤;

e)TimeOut:程序運行超時.

圖5 寄存器故障注入實驗結(jié)果Fig.5 Results of register fault injection

圖5展示了EDDI算法和VBSED算法轉(zhuǎn)換的程序?qū)拇嫫鞴收献⑷雽嶒灲Y(jié)果對比,包括通用寄存器和向量寄存器.由于EDDI算法無法檢測在緩存和主存上發(fā)生的錯誤,這里不對其作實驗評估.本文對VBSED算法轉(zhuǎn)換的程序在緩存和主存上進行了故障注入實驗,結(jié)果如圖6所示.

圖6 緩存和主存故障注入實驗結(jié)果Fig.6 Results of cache and memory fault injection

EDDI算法和VBSED算法都是在中間代碼層次對進行程序轉(zhuǎn)換,處于匯編代碼的上層,因此無法細粒度地對所有機器指令進行轉(zhuǎn)換處理.EDDI算法會添加大量冗余指令,這會帶來寄存器分配壓力問題,導(dǎo)致編譯器在寄存器分配階段引入較多的寄存器溢出代碼,EDDI算法無法檢測溢出代碼地方發(fā)生的錯誤.而VBSED算法將原計算指令和冗余計算指令轉(zhuǎn)換為向量指令,不會帶來這樣的問題.由圖5中可以看出,VBSED算法的檢測到的錯誤比EDDI算法平均高15.8%.VBSED算法的另一個優(yōu)勢是考慮了緩存和主存上錯誤.緩存存放了主存中一部分數(shù)據(jù),是程序運行過程中某一時段用到的數(shù)據(jù),對緩存中數(shù)據(jù)進行故障注入會比對主存故障注入更容易導(dǎo)致程序錯誤.實驗結(jié)果中VBSED算法緩存錯誤檢測率平均為98.39%,主存錯誤檢測率平均為98.57%.綜合以上實驗結(jié)果,本文提出的算法對寄存器、緩存和主存上錯誤具有較高的檢錯率.

5 結(jié) 論

本文提出了一個基于SIMD向量化的數(shù)據(jù)流軟錯誤檢測算法,利用現(xiàn)代處理器SIMD能力來提高軟錯誤檢測的性能.本文還設(shè)計了數(shù)據(jù)和指令向量化規(guī)則,在中間代碼層應(yīng)用相應(yīng)的向量化規(guī)則生成轉(zhuǎn)換后的代碼.最終生成的程序在時間開銷方面相較于EDDI算法平均提升了1.8倍,在空間開銷方面代碼大小平均降低了1.25倍.最后通過仿真故障注入實驗?zāi)M寄存器、緩存、主存故障,驗證了VBSED算法的有效性和錯誤檢測能力.實驗結(jié)果表明本文算法針對寄存器軟錯誤檢測率比EDDI算法平均提升了15.8%,緩存和主存錯誤檢錯率分別為98.39%和98.57%.