利用SIMD向量化的數(shù)據(jù)流軟錯(cuò)誤檢測(cè)算法

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

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

1 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

目前針對(duì)軟錯(cuò)誤檢測(cè)的方法主要分為兩類:基于硬件的錯(cuò)誤檢測(cè)方法和基于軟件的錯(cuò)誤檢測(cè)方法.

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

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

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

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

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

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

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

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

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

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

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

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

2)程序加固階段

程序加固階段分為如下4個(gè)階段:

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

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

b)指令向量化

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

c)添加檢查點(diǎn)

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

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

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

3.2 相關(guān)定義

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

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

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

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

3)數(shù)組Darr:{Db1,Db2,…,Dbn},n≥1,表示n個(gè)元素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種類型,并給出對(duì)應(yīng)格式:

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

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

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

4)跳轉(zhuǎn)指令I(lǐng)jmp:,該元組所表達(dá)的語(yǔ)義為當(dāng)cond條件為真時(shí),程序跳轉(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è)計(jì)

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

規(guī)則1.基本類型數(shù)據(jù)向量化轉(zhuǎn)換規(guī)則VEC_D_B(Db,K),定義見(jiàn)式(1).Db為應(yīng)用該規(guī)則的數(shù)據(jù),K為轉(zhuǎn)換后向量的長(zhǎng)度,下文表示相同.對(duì)于任意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),定義見(jiàn)式(2).Darr為應(yīng)用該規(guī)則的數(shù)組.對(duì)于任意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),定義見(jiàn)式(3).Dst為應(yīng)用該規(guī)則的結(jié)構(gòu)體.對(duì)于任意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ù),對(duì)其應(yīng)用向量化規(guī)則,需對(duì)它的所有基本類型數(shù)據(jù)Db應(yīng)用規(guī)則1,對(duì)所有數(shù)組數(shù)據(jù)應(yīng)用規(guī)則2.例如結(jié)構(gòu)體數(shù)據(jù)Dst={Db1,Db2,Darr},對(duì)Dst應(yīng)用規(guī)則3,需對(duì)Db1和Db2和分別應(yīng)用規(guī)則1,對(duì)Darr應(yīng)用規(guī)則2,因此對(duì)Dst向量化后的向量數(shù)據(jù)VDst={VDb1,VDb2,VDarr}.

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

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

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

VEC_I_ARITH(Iarith,K):

VIarith==
VEC_D_B(dest,K)>

(4)

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

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

VEC_I_LD(Ild,K):

VIld==

(5)

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

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

VEC_I_ST(Ist,K):

VIst==

(6)

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

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

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

DEVEC_VD_B(VDb,Idx):Db=

(7)

3.4 錯(cuò)誤檢測(cè)代碼生成規(guī)則

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

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

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

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

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

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

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

3.5 錯(cuò)誤檢測(cè)代碼生成規(guī)則

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

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

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)建指令依賴的有向無(wú)環(huán)圖,對(duì)此有向無(wú)環(huán)圖通過(guò)拓?fù)渑判蛏芍噶钜蕾図樞?

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)環(huán)境配置

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

測(cè)試程序本文選擇MiBench[27]中QSORT、CRC、RAD2DEG、FFT 4個(gè)測(cè)試程序和深度學(xué)習(xí)中CONV2D、MatMul兩個(gè)常見(jiàn)的算子,用這些程序來(lái)對(duì)比上述兩個(gè)算法的時(shí)空開(kāi)銷和錯(cuò)誤檢測(cè)率.

4.2 實(shí)驗(yàn)結(jié)果分析

1)時(shí)空開(kāi)銷對(duì)比

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

圖4 EDDI、VBSED、UP 3類程序時(shí)空開(kāi)銷對(duì)比Fig.4 Comparison of time and space cost

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

2)錯(cuò)誤檢測(cè)率對(duì)比

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

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

b)DETECTED:檢錯(cuò)算法檢測(cè)到錯(cuò)誤;

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

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

e)TimeOut:程序運(yùn)行超時(shí).

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

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

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

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

5 結(jié) 論

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