存儲(chǔ)系統(tǒng)中兩級(jí)糾錯(cuò)編碼方案設(shè)計(jì)與驗(yàn)證

羅金飛，趙帥兵，覃落雨，王剛,*，劉曉光

1. 南開大學(xué) 計(jì)算機(jī)學(xué)院 天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300350 2. 中國(guó)空間技術(shù)研究院，北京 100086

在惡劣的空間環(huán)境(如地球輻射帶，相應(yīng)的宇宙線)中，存在著大量的高能粒子[1]。這些帶電粒子在穿過航天系統(tǒng)中的微電子器件時(shí)，在器件內(nèi)部敏感區(qū)可能會(huì)產(chǎn)生電子-空穴對(duì)，這些電荷被靈敏器件電極收集后，造成器件邏輯狀態(tài)的非正常改變或器件損壞。由于這種效應(yīng)是單個(gè)粒子作用的結(jié)果，因此稱為單粒子效應(yīng)或單粒子事件[2]。

單粒子效應(yīng)分為單粒子翻轉(zhuǎn)、單粒子閉鎖、單粒子燒毀等，其中單粒子翻轉(zhuǎn)最為普遍。所謂單粒子翻轉(zhuǎn)，是指星上存儲(chǔ)單元在惡劣的輻照環(huán)境下受到高能粒子攻擊時(shí)，可能會(huì)出現(xiàn)存儲(chǔ)信息發(fā)生錯(cuò)誤的情況，即原始寫入數(shù)據(jù)為“0”，而實(shí)際存儲(chǔ)器件中的內(nèi)容卻翻轉(zhuǎn)為“1”，或者從“1”翻轉(zhuǎn)到“0”，從而導(dǎo)致存儲(chǔ)系統(tǒng)功能紊亂。

為保證在軌航天系統(tǒng)正常運(yùn)行，必須設(shè)計(jì)相應(yīng)的冗余措施來最大幅度地預(yù)防和消除相關(guān)惡劣輻照環(huán)境的影響[3]。

航天系統(tǒng)現(xiàn)有的軟件防護(hù)措施中，有很多產(chǎn)品使用海明碼[4]來進(jìn)行錯(cuò)誤檢測(cè)與糾正[5]，海明碼糾一檢二的功能降低了航天存儲(chǔ)系統(tǒng)中不可修復(fù)的概率。但隨著空間環(huán)境越來越惡劣，靈敏器件特征尺寸越來越小，造成單粒子翻轉(zhuǎn)現(xiàn)象所需要的臨界電荷也越來越低，即字內(nèi)發(fā)生多個(gè)粒子翻轉(zhuǎn)錯(cuò)誤的現(xiàn)象越來越頻繁[6]，這時(shí)使用糾正一位錯(cuò)誤的海明碼就很難保證在軌航天系統(tǒng)的正常運(yùn)行。

針對(duì)上述編碼方案的不足，本文提出了一種兩級(jí)冗余編碼方案，來提高存儲(chǔ)系統(tǒng)中的可靠性。該方案主要從以下兩個(gè)方面進(jìn)行：在字內(nèi)選用糾錯(cuò)能力更高的編碼，如使用可以糾正兩位錯(cuò)誤的BCH編碼[7]；在字間布置另一級(jí)冗余編碼，例如可使用奇偶校驗(yàn)碼[8]，配合字內(nèi)編碼實(shí)現(xiàn)更強(qiáng)的檢錯(cuò)/糾錯(cuò)能力。

這樣在解碼時(shí)，即可分為兩種情況進(jìn)行：當(dāng)字內(nèi)出現(xiàn)的錯(cuò)誤位數(shù)在字內(nèi)編碼方案的糾錯(cuò)能力之內(nèi)時(shí)，直接利用字內(nèi)編碼進(jìn)行糾錯(cuò)；而當(dāng)字內(nèi)出現(xiàn)的錯(cuò)誤位數(shù)超出字內(nèi)編碼方案的糾錯(cuò)能力時(shí)，可以將錯(cuò)誤拋給上層編碼，利用字間編碼進(jìn)行糾錯(cuò)。其中由于利用字間進(jìn)行解碼的情況發(fā)生概率顯著低于字內(nèi)解碼，在所有故障事件中占較小比例，因此其帶來的開銷對(duì)系統(tǒng)整體平均性能影響較小。

這種編碼方案構(gòu)造思路有著顯著優(yōu)點(diǎn)：

1) 考慮單粒子翻轉(zhuǎn)可能引起一個(gè)字內(nèi)多個(gè)位同時(shí)發(fā)生翻轉(zhuǎn)的情況。即不管一種編碼的糾錯(cuò)能力有多高，都有可能出現(xiàn)不可修復(fù)的情況，并且一味地去提高一種編碼方案的糾錯(cuò)能力需要付出很大時(shí)間與空間上的代價(jià)。本文提出的兩級(jí)編碼機(jī)制，用簡(jiǎn)單編碼組合即可達(dá)到與復(fù)雜單一編碼相當(dāng)?shù)目煽啃?，而在方案?shí)現(xiàn)方面簡(jiǎn)單得多。

2) 不同的存儲(chǔ)系統(tǒng)對(duì)可靠性和性能的要求有所不同。兩級(jí)冗余編碼可以針對(duì)不同存儲(chǔ)器件的特點(diǎn)，例如程序存儲(chǔ)器PROM，NOR_FLASH[9]本身屬于只讀型的存儲(chǔ)器，可靠性較高，故可以在字內(nèi)仍然采用低糾錯(cuò)的EDAC(39,32)編碼，字間采用奇偶校驗(yàn)編碼。而對(duì)于數(shù)據(jù)存儲(chǔ)器NAND_FLASH和運(yùn)行內(nèi)存SRAM[10]，這種自身可靠性較低、有較多寫操作的，可以在字內(nèi)采用高糾錯(cuò)碼如BCH編碼，字間采用奇偶校驗(yàn)編碼。這樣，就可以針對(duì)不同的存儲(chǔ)器件的自身特點(diǎn)，平衡可靠性和成本性能。

1 存儲(chǔ)編碼

本文主要使用高糾錯(cuò)編碼BCH或者錯(cuò)誤檢測(cè)和糾正(EDAC)技術(shù)中的海明碼(Hamming)作為字內(nèi)編碼，奇偶校驗(yàn)碼作為字間編碼。下面對(duì)上述編碼進(jìn)行簡(jiǎn)單的介紹。

1.1 奇偶校驗(yàn)碼

奇偶校驗(yàn)碼作為常用的檢錯(cuò)碼，常用來檢驗(yàn)傳送的信息是否出現(xiàn)了錯(cuò)誤。在事先知道碼字錯(cuò)誤位置的前提下，奇偶校驗(yàn)碼具有1位錯(cuò)誤恢復(fù)的能力。本文主要利用這一性質(zhì)來恢復(fù)超過字內(nèi)糾錯(cuò)能力的碼字單元。

1.2 海明碼

海明碼[11]是一種糾正1位錯(cuò)的編碼，星上系統(tǒng)CPU(BM383MG)采用一種Hamming(39,32)編碼方案(下文用EDAC(39,32)表示)。該編碼方案將32位信息位，編碼生成7位監(jiān)督校驗(yàn)位，碼長(zhǎng)為39位。

1.3 BCH碼

BCH碼是一種基于有限域的、可以糾正指定錯(cuò)誤位數(shù)的線性循環(huán)碼[12]。

本文采用的是BCH(44,32)。即32位信息位，編碼生成12位監(jiān)督校驗(yàn)位，碼長(zhǎng)為44位，具有糾2位錯(cuò)的能力。

1.4 糾錯(cuò)碼與CRC校驗(yàn)的區(qū)別

CRC[13]校驗(yàn)中如果得到的余數(shù)不為0，則證明信道傳輸過程中碼字發(fā)生了錯(cuò)誤，此時(shí)會(huì)要求發(fā)送方重發(fā)。本文使用的前向糾錯(cuò)碼利用碼字間的校驗(yàn)關(guān)系恢復(fù)出正確的數(shù)據(jù)，此時(shí)并不需要通知發(fā)送方，故也談不上重發(fā)，這也是與CRC校驗(yàn)最大的不同。

即CRC校驗(yàn)不具備糾錯(cuò)能力，當(dāng)發(fā)現(xiàn)了錯(cuò)誤之后并不能糾正出錯(cuò)誤，而本文所使用的糾錯(cuò)碼可以檢查出是否發(fā)生了錯(cuò)誤并且在糾錯(cuò)范圍內(nèi)糾正出來。

2 兩級(jí)糾錯(cuò)編碼方案設(shè)計(jì)

2.1 編碼方案設(shè)計(jì)思想

本文提出了一種兩級(jí)冗余編碼方案，具體實(shí)現(xiàn)為通過簡(jiǎn)單編碼的組合如字內(nèi)使用Hamming碼或者BCH碼，字間可使用簡(jiǎn)單的奇偶校驗(yàn)碼來組合高容錯(cuò)的編碼。

這樣當(dāng)存儲(chǔ)系統(tǒng)中出現(xiàn)錯(cuò)誤但錯(cuò)誤個(gè)數(shù)不超過字內(nèi)編碼的糾錯(cuò)范圍時(shí)，可以直接利用字內(nèi)糾錯(cuò)來進(jìn)行糾正錯(cuò)誤，無需利用字間編碼進(jìn)行糾錯(cuò)，這種情況也是最為常見的[14]，這樣也使得糾錯(cuò)時(shí)運(yùn)算、訪存的次數(shù)接近于原始字內(nèi)編碼；如果超過了字內(nèi)本身編碼的糾錯(cuò)范圍，通過讀入同條紋中其他字，利用第二級(jí)字間解碼，利用字間運(yùn)算，從而修復(fù)該錯(cuò)誤條紋。

2.2 兩級(jí)冗余方案設(shè)計(jì)

下面詳細(xì)描述編碼解碼具體的過程：

編碼操作：每個(gè)字先做字內(nèi)編碼，即通過乘以相應(yīng)的編碼矩陣來生成校驗(yàn)位，隨后進(jìn)行字間校驗(yàn)，同條紋的字(包括字內(nèi)檢驗(yàn))按照第二級(jí)編碼的編碼規(guī)則做相關(guān)運(yùn)算產(chǎn)生結(jié)果，生成第二級(jí)編碼，得出最后的數(shù)據(jù)字和各自算出的校驗(yàn)位。

解碼操作：首先進(jìn)行字內(nèi)檢錯(cuò)，具體方式為將收到的碼字乘以根據(jù)編碼規(guī)則得到的校驗(yàn)矩陣，得到相應(yīng)的伴隨式。如果伴隨式為0，則說明碼字沒有錯(cuò)誤；如果不為0，需要查預(yù)先生成的伴隨式與錯(cuò)誤圖樣映射表，如果表中含有得到的伴隨式，即說明可以通過字內(nèi)修復(fù)，通過異或錯(cuò)誤圖樣來進(jìn)行糾正錯(cuò)誤；如果沒有，說明錯(cuò)誤位數(shù)超過字內(nèi)糾錯(cuò)能力，則讀取同組條紋內(nèi)其他字，同樣進(jìn)行檢錯(cuò)、糾錯(cuò)、字內(nèi)恢復(fù)的過程，進(jìn)行字間恢復(fù)該錯(cuò)誤條紋。

下面簡(jiǎn)單描述用第二級(jí)奇偶校驗(yàn)碼糾錯(cuò)的過程，如圖1所示，一組校驗(yàn)包含5行數(shù)據(jù)，分別為d0,d1,d2,d3,d4，字間校驗(yàn)為P0。假設(shè)d1發(fā)生了字內(nèi)編碼無法糾正的錯(cuò)誤，則根據(jù)式(1)用編碼時(shí)生成的異或條紋來進(jìn)行異或操作即可恢復(fù)錯(cuò)誤條紋。

d1=d0⊕d2⊕d3⊕d4⊕P0

(1)

式中：⊕為異或操作。

圖1 兩級(jí)糾錯(cuò)方案
Fig.1 Two-level decoding scheme

2.3 系統(tǒng)讀寫算法設(shè)計(jì)

2.2節(jié)描述的是數(shù)據(jù)字和校驗(yàn)之間的計(jì)算關(guān)系，而將兩級(jí)編碼引入實(shí)際的存儲(chǔ)系統(tǒng)勢(shì)必會(huì)帶來編碼讀寫性能的下降。本節(jié)主要是在此問題上，基于上述編碼/解碼的思想，提出相應(yīng)的解決方案，盡量減少由于兩級(jí)編碼帶來的對(duì)存儲(chǔ)系統(tǒng)性能的影響。

2.3.1 系統(tǒng)寫算法

本節(jié)主要討論單字寫產(chǎn)生的校驗(yàn)開銷問題(多字寫處理方法類似，整條紋寫無更新問題，簡(jiǎn)單采用2.2節(jié)描述的編碼方法即可)。

當(dāng)向系統(tǒng)寫入一個(gè)數(shù)據(jù)字時(shí)，一方面需要更新對(duì)應(yīng)的內(nèi)存字及其校驗(yàn)；另一方面，由于兩級(jí)編碼的引入，還需更新第二級(jí)校驗(yàn)的校驗(yàn)字，顯然，與只采用字內(nèi)校驗(yàn)的傳統(tǒng)系統(tǒng)相比，會(huì)顯著增大寫延遲。為此，提出一種字間校驗(yàn)延遲更新的策略來減少第二級(jí)編碼對(duì)存儲(chǔ)系統(tǒng)寫操作造成的影響，具體過程如下：

1) 系統(tǒng)初始化時(shí)生成一個(gè)專門負(fù)責(zé)整個(gè)系統(tǒng)的字間校驗(yàn)更新的隊(duì)列并啟動(dòng)一個(gè)子線程(硬件實(shí)現(xiàn)可以是一個(gè)硬件隊(duì)列和處理電路)專門負(fù)責(zé)字間校驗(yàn)更新。

2) 當(dāng)寫一個(gè)字時(shí)，首先計(jì)算字內(nèi)校驗(yàn)，得到新值新校驗(yàn)之后，讀取該字的舊值和舊校驗(yàn)，字間更新隊(duì)列存儲(chǔ)更新請(qǐng)求Δ=(新值與新校驗(yàn))⊕(舊值與舊校驗(yàn))，隨后可用來更新字間校驗(yàn)，最后寫入新值新校驗(yàn)，返回給用戶，此時(shí)用戶感知到的更新過程結(jié)束。

3) 后臺(tái)校驗(yàn)更新線程繼續(xù)更新字間的第二級(jí)編碼(以奇偶校驗(yàn)碼為例，其他編碼處理流程一致，校驗(yàn)更新計(jì)算不同)：線程從系統(tǒng)初始化得到的更新隊(duì)列中不斷地取出更新請(qǐng)求Δ，讀取舊字間校驗(yàn)XORold，計(jì)算Δ⊕XORold得出第二級(jí)編碼的更新結(jié)果并將其寫入，完成更新操作，一個(gè)寫操作完整過程結(jié)束。

2.3.2 延遲更新策略的優(yōu)點(diǎn)

1) 由于一級(jí)編碼更新完成到二級(jí)編碼更新完成這個(gè)時(shí)間間隔相對(duì)于故障/單粒子翻轉(zhuǎn)事件發(fā)生間隔是極小的，所以可以認(rèn)為對(duì)系統(tǒng)可靠性沒有影響。而用戶感知到的只是單一字內(nèi)編碼的延遲加上讀取舊值和計(jì)算更新請(qǐng)求的開銷，能夠盡量降低第二級(jí)編碼對(duì)整個(gè)的存儲(chǔ)系統(tǒng)所帶來的影響。

2) 可以靈活地根據(jù)存儲(chǔ)器的可靠性特點(diǎn)選取第二級(jí)的編碼，不必?fù)?dān)心第二級(jí)編碼的復(fù)雜度對(duì)整個(gè)存儲(chǔ)系統(tǒng)所造成的影響。

3) 同一組的數(shù)據(jù)，可以同時(shí)進(jìn)行更新而不必進(jìn)行復(fù)雜的一致性處理。由于第一步只需要將新值與舊值的異或結(jié)果產(chǎn)生的中間變量暫存在隊(duì)列里面，避免了同時(shí)讀第二級(jí)校驗(yàn)條紋，這樣就解決了同時(shí)更新同時(shí)讀字間校驗(yàn)的沖突問題。

4) 對(duì)校驗(yàn)更新隊(duì)列中的請(qǐng)求可實(shí)現(xiàn)更優(yōu)的調(diào)度，例如可將同組的更新請(qǐng)求一次性執(zhí)行，只需一次訪存和多次異或運(yùn)算，大幅度減少了訪存次數(shù)。

2.3.3 系統(tǒng)讀算法

系統(tǒng)讀主要基于2.2節(jié)描述的解碼操作的思想進(jìn)行，具體方案如下：

1) 用戶讀取某個(gè)地址上的數(shù)據(jù)字時(shí)，讀取該地址中的數(shù)據(jù)字和對(duì)應(yīng)校驗(yàn)。

2) 首先進(jìn)行字內(nèi)檢錯(cuò)，如果檢錯(cuò)后發(fā)現(xiàn)無錯(cuò)誤，直接返回用戶即可。

3) 如果發(fā)現(xiàn)了錯(cuò)誤但是不超過其字內(nèi)編碼的糾錯(cuò)范圍時(shí)，進(jìn)行字內(nèi)糾錯(cuò)，隨后將糾錯(cuò)得到的數(shù)據(jù)字返回給用戶即可。

4) 如果錯(cuò)誤個(gè)數(shù)超過了字內(nèi)編碼的糾錯(cuò)范圍則進(jìn)入第二級(jí)編碼進(jìn)行糾錯(cuò)。

3 編碼方案算法優(yōu)化

實(shí)驗(yàn)證明編碼速度與系統(tǒng)的性能息息相關(guān)。編碼速度越快，越有利于提高系統(tǒng)的吞吐率，提高系統(tǒng)的性能。糾錯(cuò)速度主要與系統(tǒng)的可靠性相關(guān)，也就是說修復(fù)時(shí)間越短，系統(tǒng)的可靠性越高[15]。基于此，本文還針對(duì)兩級(jí)冗余編碼方案提出幾方面的優(yōu)化方法，來提高系統(tǒng)的編解碼效率，從而保證系統(tǒng)的可靠性。

優(yōu)化工作主要從減少存儲(chǔ)訪問和優(yōu)化編解碼計(jì)算兩個(gè)角度進(jìn)行，其中優(yōu)化訪存主要應(yīng)用讀修改寫來減少存儲(chǔ)器的訪問次數(shù)來進(jìn)行；優(yōu)化計(jì)算方面主要采用調(diào)度順序優(yōu)化和單指令流多數(shù)據(jù)流并行(SIMD)[16]。下面將詳細(xì)介紹幾種優(yōu)化方法。

3.1 讀修改寫更新優(yōu)化

在本文所提出的兩級(jí)編碼中，字間編碼主要采用奇偶校驗(yàn)編碼，即校驗(yàn)字為數(shù)據(jù)字的異或運(yùn)算結(jié)果(如圖1所示)，注意到組中任何數(shù)據(jù)字的更新都會(huì)影響生成的校驗(yàn)字。本文采用讀修改寫[15]的方式來進(jìn)行更新相應(yīng)的校驗(yàn)條紋。

(2)

這樣當(dāng)需要更新一個(gè)字時(shí)，平凡方法(重構(gòu)寫)是將同組的其他字讀出，然后進(jìn)行計(jì)算，最后寫入異或結(jié)果，需要訪問6次訪存才能完成該操作；而當(dāng)運(yùn)用了讀修改寫的方式，只需要讀取該字和校驗(yàn)的舊值來計(jì)算新校驗(yàn)，然后寫入新數(shù)據(jù)，新校驗(yàn)即可，只需要訪問4次存儲(chǔ)器即可，減少了大量的存儲(chǔ)器訪問次數(shù)。

這種方法的優(yōu)化在實(shí)際硬件實(shí)現(xiàn)中，更能體現(xiàn)其優(yōu)勢(shì)，能夠減少CPU訪問內(nèi)存的次數(shù)，大大降低CPU和內(nèi)存之間速度的不匹配所帶來的性能下降。4.3.1節(jié)描述的系統(tǒng)寫方法即采用了這種策略。

3.2 調(diào)度順序優(yōu)化

編解碼計(jì)算中存在一些重復(fù)運(yùn)算，即，一些中間計(jì)算結(jié)果可用于其他計(jì)算，合理利用這種重復(fù)性可優(yōu)化編解碼計(jì)算。Plank等[17]基于此提出一種尋找較優(yōu)計(jì)算順序來減少重復(fù)運(yùn)算的方法——調(diào)度順序優(yōu)化，從而降低總異或運(yùn)算次數(shù)達(dá)到編碼效率優(yōu)化的目的。

本文借鑒此思想優(yōu)化兩級(jí)編碼的計(jì)算。如圖2所示，一個(gè)編碼計(jì)算可表達(dá)為矩陣乘法運(yùn)算B=AX，其中陰影部分表示元素1、空白表示元素0，A為校驗(yàn)向量,X為數(shù)據(jù)向量，B為結(jié)果向量。為了得到結(jié)果B，可直接逐個(gè)計(jì)算P0～P2，但這種方法并不高效。

可以看出，對(duì)于P0、P1兩個(gè)元素的生成都包含中間異或結(jié)果x0+x3。若先計(jì)算出中間結(jié)果，再利用中間結(jié)果計(jì)算P0、P1，比直接計(jì)算可以節(jié)省1次異或運(yùn)算。

圖2的矩陣乘法，可利用圖3所示的調(diào)度順序進(jìn)行優(yōu)化，其中Si表示第i步運(yùn)算。

傳統(tǒng)尋找最優(yōu)調(diào)度的算法是通過枚舉所有調(diào)度次序來尋找最優(yōu)次序，但對(duì)于本文EDAC(39,32)和BCH(44,32)這樣的大規(guī)模編碼并不可行，借鑒文獻(xiàn)[17]中的Xsets啟發(fā)式算法，設(shè)計(jì)了求解EDAC(39,32)和BCH(44,32)近似最優(yōu)編解碼計(jì)算調(diào)度次序的算法，算法說明如下：

圖2 編碼操作的生成矩陣?yán)?br/>Fig.2 An example that describing encoding operation

圖3 一種優(yōu)化調(diào)度方案
Fig.3 One optimization schedul

1) 數(shù)據(jù)位和中間計(jì)算結(jié)果作為集合里的元素。

2) 每個(gè)校驗(yàn)位用一個(gè)集合(稱為Xset)表示。集合中元素異或得到這個(gè)校驗(yàn)位，初始時(shí)只由計(jì)算此校驗(yàn)位的數(shù)據(jù)位構(gòu)成，在計(jì)算過程中，可能還包含中間結(jié)果。

3) 用圖(稱為Subex圖)描述編碼計(jì)算過程。頂點(diǎn)代表元素，邊的權(quán)重代表兩個(gè)元素共同出現(xiàn)在集合中的次數(shù)。

4) 啟發(fā)式策略。權(quán)重最高的邊的兩個(gè)頂點(diǎn)生成新的元素，其異或結(jié)果作為新的元素插入到集合里。

算法流程圖如圖4所示。

通過使用Xsets算法尋找最優(yōu)調(diào)度，平凡算法與優(yōu)化后計(jì)算時(shí)異或次數(shù)相關(guān)對(duì)比如表1所示。由表1可見，通過使用相應(yīng)的調(diào)度，優(yōu)化后的異或操作可明顯減少，其中BCH(44,32)編碼異或次數(shù)減少了45.7%。

3.3 SIMD并行

當(dāng)軟件實(shí)現(xiàn)內(nèi)存編碼運(yùn)算時(shí)，數(shù)據(jù)位提取和相應(yīng)計(jì)算非常耗時(shí)，本項(xiàng)目針對(duì)此問題擬借助SIMD指令優(yōu)化位運(yùn)算[18]以提高數(shù)據(jù)并行性，來提高軟件實(shí)現(xiàn)編解碼的效率。

SIMD指令優(yōu)化位運(yùn)算具體過程為：

圖4 Xsets算法流程圖
Fig.4 Flowchart of Xsets algorithm

表1 異或運(yùn)算次數(shù)對(duì)比Table 1 Comparison of XOR times

1) 基于編碼的生成矩陣構(gòu)造每個(gè)校驗(yàn)的掩碼(校驗(yàn)位包含哪些數(shù)據(jù)位)。

2) 生成的掩碼與需要編碼的數(shù)據(jù)進(jìn)行與(&)操作，得到校驗(yàn)包含的數(shù)據(jù)位的值。

3) 使用SIMD中popcnt指令[19]可一次得出數(shù)據(jù)位含有“1”的數(shù)目，數(shù)目的末位即生成的校驗(yàn)值。

4) 通過移位和或運(yùn)算逐步生成所有校驗(yàn)碼。

4 兩級(jí)冗余編碼方案分析

4.1 編碼方案特點(diǎn)對(duì)比分析

表2主要列舉了本文實(shí)現(xiàn)的編碼相關(guān)特點(diǎn)。

表2 編碼特點(diǎn)分析Table 2 Analysis of coding characteristics

本文主要對(duì)比的是高糾錯(cuò)編碼BCH(44,32)和兩級(jí)編碼EDAC(39,32)+XOR(8,7)的優(yōu)劣。由表2可知，存儲(chǔ)開銷方面，兩級(jí)編碼EDAC(39,32)+XOR(8,7)的存儲(chǔ)開銷為(39×8)/(32×7)=1.39X(X為相應(yīng)倍數(shù)，下同)，與高糾錯(cuò)能力BCH(44,32)的存儲(chǔ)開銷(1.375X)相比幾乎一致，但是在糾錯(cuò)能力上兩級(jí)編碼EDAC(39,32)+XOR(8,7)能夠糾正同一編碼條紋中的任意3位錯(cuò)，并且可以糾正單字內(nèi)發(fā)生多個(gè)錯(cuò)誤，而單一的BCH(44,32)只具備糾2位錯(cuò)的能力，即在存儲(chǔ)開銷相近的情況下實(shí)現(xiàn)了更高的糾錯(cuò)能力，并且編解碼復(fù)雜度也比單一的BCH(44,32)低。

如果用兩級(jí)冗余編碼EDAC(39,32)+XOR(8,7)對(duì)比原始的EDAC(39,32)，由于需要存儲(chǔ)第二級(jí)的編碼條紋，存儲(chǔ)代價(jià)由原來的1.219X增加到了1.39X，這是兩級(jí)編碼的劣勢(shì)，但對(duì)應(yīng)的是糾錯(cuò)能力的大幅度提升，由原來的只能實(shí)現(xiàn)1位錯(cuò)到可以糾正同組的任意3位錯(cuò)誤。

4.2 可靠性對(duì)比

本文采用二項(xiàng)分布計(jì)算不同編碼方案下存儲(chǔ)系統(tǒng)數(shù)據(jù)丟失的概率。假定空間單粒子翻轉(zhuǎn)的概率ε=5.3×10-8upsets/(bit·day)[20](單位為每位每天翻轉(zhuǎn)的概率),并且每個(gè)條紋里bit的翻轉(zhuǎn)是獨(dú)立分布的，利用二項(xiàng)分布式進(jìn)行計(jì)算，得出航天存儲(chǔ)系統(tǒng)采用單一的字內(nèi)編碼EDAC(39,32)方案，整個(gè)系統(tǒng)的不可修復(fù)概率為2.08×10-12；高糾錯(cuò)編碼BCH(44,32)不可修復(fù)概率為2.43×10-15；當(dāng)存儲(chǔ)系統(tǒng)采用文章提出的兩級(jí)冗余編碼EDAC(39,32)+XOR(8,7)方案時(shí)，整個(gè)系統(tǒng)的不可修復(fù)性僅為1.21×10-22。

(3)

兩級(jí)編碼方案與原始的EDAC(39,32)編碼、高糾錯(cuò)編碼方案BCH(44,32)相比，兩級(jí)冗余編碼方案使條紋內(nèi)出現(xiàn)不可修復(fù)的概率下降了十幾個(gè)數(shù)量級(jí)，能夠較好地保護(hù)星上存儲(chǔ)系統(tǒng)的正常運(yùn)行。

5 實(shí)驗(yàn)驗(yàn)證

本文為了仿真兩級(jí)冗余編碼方案在實(shí)際的星上系統(tǒng)中運(yùn)行情況，通過軟件模擬星上系統(tǒng)的方式來進(jìn)行相關(guān)實(shí)驗(yàn)，基本運(yùn)行環(huán)境如表3所示。

表3 實(shí)驗(yàn)環(huán)境Table 3 Environment experiment

5.1 內(nèi)部存儲(chǔ)器編解碼計(jì)算效率

這部分實(shí)驗(yàn)主要針對(duì)兩種字內(nèi)編碼方案EDAC(39,32)和BCH(44,32)及新提出的兩級(jí)冗余方案，其中二級(jí)編碼選用XOR(8,7)來進(jìn)行內(nèi)存系統(tǒng)中編碼、檢錯(cuò)、糾錯(cuò)測(cè)試分析。實(shí)驗(yàn)結(jié)果體現(xiàn)為相關(guān)計(jì)算性能，其輸入分別為不同編碼所需的生成矩陣、解碼所需的校驗(yàn)矩陣和伴隨式與錯(cuò)誤圖樣映射表、隨機(jī)生成的相應(yīng)信息和每個(gè)條紋中隨機(jī)生成的錯(cuò)誤位置。

以編解碼1 GB數(shù)據(jù)為例，測(cè)試結(jié)果如圖5所示。由圖中結(jié)果可得如下結(jié)論：

1) 字內(nèi)編碼方案與本文新提出的兩級(jí)冗余方案相比，編碼操作時(shí)間大致一樣。

2) 檢錯(cuò)方面，無故障讀也大致相同；故障讀時(shí)間，兩級(jí)編碼略高于簡(jiǎn)單一級(jí)編碼，原因?yàn)楫?dāng)發(fā)生了字內(nèi)編碼不可修復(fù)的錯(cuò)誤時(shí)，需要從內(nèi)存中讀同組的相關(guān)條紋，然后進(jìn)行相關(guān)運(yùn)算，其中讀取內(nèi)存和異或運(yùn)算的過程消耗了一定的時(shí)間。

圖5 內(nèi)存編碼和解碼計(jì)算效率
Fig.5 Memory encoding and decoding calculation efficiency

5.2 內(nèi)部存儲(chǔ)器編碼計(jì)算SIMD優(yōu)化效果

測(cè)試了內(nèi)存系統(tǒng)中SIMD對(duì)編碼性能的優(yōu)化效果，圖6給出了對(duì)1 GB數(shù)據(jù)進(jìn)行編碼平凡算法(BIT_XOR)和SIMD算法所需時(shí)間。從圖6可以看出，在內(nèi)存系統(tǒng)中采用SIMD算法優(yōu)化編碼計(jì)算，較之平凡算法即按位異或算法顯著提升了性能，最高達(dá)到了13倍加速比。

圖6 SIMD和BIT_XOR優(yōu)化算法對(duì)比
Fig.6 Comparison of SIMD and BIT_XOR optimization algorithms

5.3 外部存儲(chǔ)器編解碼計(jì)算效率

兩級(jí)編碼方案既可用于內(nèi)存系統(tǒng)，也可用于外部存儲(chǔ)器，此時(shí)編解碼的基本單元由比特變?yōu)镵B級(jí)的塊。本節(jié)測(cè)試外部存儲(chǔ)系統(tǒng)編碼塊大小為32 KB，二級(jí)編碼仍采用XOR(8,7)，編解碼1 GB數(shù)據(jù)，其計(jì)算性能實(shí)驗(yàn)結(jié)果如圖7所示。

從圖7可以看出，類似于內(nèi)存編解碼計(jì)算性能，外部存儲(chǔ)器兩級(jí)編碼計(jì)算耗時(shí)較一級(jí)來說有所增加；解碼計(jì)算中多故障讀時(shí)，由于要讀同組的條紋進(jìn)行檢錯(cuò)、糾錯(cuò)，要比單一的字內(nèi)糾錯(cuò)多耗費(fèi)時(shí)間。

圖7 外部存儲(chǔ)器編碼和解碼計(jì)算效率
Fig.7 Disk encoding and decoding calculation efficiency

5.4 延遲更新優(yōu)化效果

5.1節(jié)和5.3節(jié)的實(shí)驗(yàn)都是測(cè)試大量數(shù)據(jù)讀寫的吞吐率，花費(fèi)的時(shí)間主要包括編解碼計(jì)算時(shí)間和整條紋數(shù)據(jù)和校驗(yàn)的讀寫。在實(shí)際存儲(chǔ)系統(tǒng)中，很多情況下是進(jìn)行小數(shù)據(jù)量的讀寫，如內(nèi)存系統(tǒng)中一個(gè)字的讀寫以及外存系統(tǒng)中一個(gè)塊的讀寫，本節(jié)測(cè)試外存儲(chǔ)系統(tǒng)中兩級(jí)編碼方案小數(shù)據(jù)寫(更新)的性能，并測(cè)試延遲更新方法的優(yōu)化效果。兩級(jí)編碼采用BCH(44,32)+XOR(8,7)，對(duì)比一級(jí)編碼采用BCH(44,32)。圖8給出了實(shí)驗(yàn)結(jié)果，橫坐標(biāo)表示系統(tǒng)的編碼塊大小，縱坐標(biāo)表示完成請(qǐng)求的響應(yīng)時(shí)間。

通過圖8可知延遲更新策略相比于同步更新策略對(duì)小寫請(qǐng)求響應(yīng)時(shí)間優(yōu)化效果顯著。BCH(44,32)+XOR(8,7)兩級(jí)編碼采用延遲更新策略后，即采取異步寫模式后，較之同步寫方式響應(yīng)時(shí)間降低了30%～70%左右，即盡可能地降低了引入第二級(jí)編碼條紋對(duì)存儲(chǔ)系統(tǒng)的影響。

圖8 延遲更新/正常更新機(jī)制性能對(duì)比
Fig.8 Comparison of delay update/normal update

5.5 調(diào)度次序優(yōu)化效果

通過優(yōu)化調(diào)度順序，可以減少數(shù)據(jù)的運(yùn)算量，從而提高處理器編解碼的能力。圖9給出了外存儲(chǔ)系統(tǒng)中BCH(44,32)+XOR(8,7)兩級(jí)編碼方案編碼1 GB數(shù)據(jù)平凡算法和調(diào)度優(yōu)化的性能對(duì)比。橫坐標(biāo)為編碼塊大小，縱坐標(biāo)為完成時(shí)間。

圖9 平凡算法/調(diào)度優(yōu)化性能對(duì)比
Fig.9 Comparison of original coding and scheduling order optimization

通過圖9可知，在外部存儲(chǔ)器中，與平凡算法相比，采用優(yōu)化調(diào)度次序的效果明顯，當(dāng)編碼的條紋單元大小為1 MB時(shí)，效率提升了39%。調(diào)度次序優(yōu)化次序?qū)獯a性能的優(yōu)化效果類似，限于篇幅未在本文中列出相應(yīng)實(shí)驗(yàn)結(jié)果。

6 結(jié) 論

本文針對(duì)航天系統(tǒng)存儲(chǔ)子系統(tǒng)提出了一種新的兩級(jí)編碼方案并提出了優(yōu)化策略。

1) 通過簡(jiǎn)單編碼的組合來提高編碼糾錯(cuò)的能力，較之傳統(tǒng)的以海明碼為糾錯(cuò)碼的系統(tǒng)，新設(shè)計(jì)的編碼算法使存儲(chǔ)系統(tǒng)中出現(xiàn)不可修復(fù)的概率大大降低，從而保障在軌衛(wèi)星在惡劣輻照環(huán)境下的正常運(yùn)行。

2) 采用延遲更新的方式，盡量減少由于兩級(jí)編碼帶來的對(duì)存儲(chǔ)系統(tǒng)性能的影響，即達(dá)到了在保證存儲(chǔ)可靠性的同時(shí)盡量降低引入二級(jí)編碼對(duì)系統(tǒng)更新性能造成影響的目的。

3) 針對(duì)提出的兩級(jí)編碼算法設(shè)計(jì)了一些優(yōu)化算法，其中使用讀修改寫方法優(yōu)化訪存次數(shù)；采用Xsets啟發(fā)式算法，利用圖的相關(guān)性質(zhì)尋找最優(yōu)調(diào)度從而減少相關(guān)計(jì)算；使用SIMD并行優(yōu)化位運(yùn)算以提高編解碼吞吐率等。