《如何選擇并實現(xiàn)高性能糾刪碼編碼引擎（下)》要點(diǎn)：
本文介紹了如何選擇并實現(xiàn)高性能糾刪碼編碼引擎（下)，希望對您有用。如果有疑問，可以聯(lián)系我們。

作者介紹：
徐祥曦,七牛云工程師,獨(dú)立開發(fā)了多套高性能糾刪碼/再生碼編碼引擎.柳青,華中科技大學(xué)博士,研究方向為基于糾刪碼的分布式存儲系統(tǒng).
前言：

在上篇《如何選擇糾刪碼編碼引擎》中,我們簡單了解了Reed-SolomonCodes(RS碼)的編／解碼過程,以及編碼引擎的評判標(biāo)準(zhǔn).但并沒有就具體實現(xiàn)進(jìn)行展開,本篇作為《糾刪碼技術(shù)詳解》的下篇,我們將主要探討工程實現(xiàn)的問題.

這里先簡單提煉一下實現(xiàn)高性能糾刪碼引擎的要點(diǎn)：首先,根據(jù)編碼理論將矩陣以及有限域的運(yùn)算工程化,接下來主要通過SIMD指令集以及緩存優(yōu)化工作來進(jìn)行加速運(yùn)算.也就是說,我們可以將RS的工程實現(xiàn)劃分成兩個基本步驟：

將數(shù)學(xué)理論工程化

進(jìn)一步的工程優(yōu)化

這需要相關(guān)研發(fā)工程師對以下內(nèi)容有所掌握：

有限域的基本概念,包括有限域的生成與運(yùn)算

矩陣的性質(zhì)以及乘法規(guī)則

計算機(jī)體系結(jié)構(gòu)中關(guān)于CPU指令以及緩存的理論

接下來,我們將根據(jù)這兩個步驟并結(jié)合相關(guān)基礎(chǔ)知識展開實現(xiàn)過程的闡述.

一理論工程化

以RS碼為例,糾刪碼實現(xiàn)于具體的存儲系統(tǒng)可以分為幾個部分：編碼、解碼和修復(fù)過程中的計算都是在有限域上進(jìn)行的；編碼過程即是計算生成矩陣(范德蒙德或柯西矩陣)和所有數(shù)據(jù)的乘積；解碼則是計算解碼矩陣(生成矩陣中某些行向量組成的方陣的逆矩陣)和重建數(shù)據(jù)的乘積.

1.1有限域運(yùn)算

有限域是糾刪碼中運(yùn)算的基礎(chǔ)域,所有的編解碼和重建運(yùn)算都是基于某個有限域的.不止是糾刪碼,一般的編碼方法都在有限域上進(jìn)行,比如常見的AES加密中也有有限域運(yùn)算.使用有限域的一個重要原因是計算機(jī)并不能精確執(zhí)行無限域的運(yùn)算,比如有理數(shù)域和虛數(shù)域.

此外,在有限域上運(yùn)算另一個重要的好處是運(yùn)算后的結(jié)果大小在一定范圍內(nèi),這是因為有限域的封閉性決定的,這也為程序設(shè)計提供了便利.比如在RS中,我們通常使用GF(2^8),即0～255這一有限域,這是因為其長度剛好為1字節(jié),便于我們對數(shù)據(jù)進(jìn)行存儲和計算.

在確定了有限域的大小之后,通過有限域上的生成多項式可以找到該域上的生成元[1],進(jìn)而通過生成元的冪次遍歷有限域上的元素,利用這一性質(zhì)我們可以生成相應(yīng)的指數(shù)表.通過指數(shù)表我們可以求出對數(shù)表,再利用指數(shù)表與對數(shù)表最終生成乘法表.關(guān)于本原多項式的生成以及相關(guān)運(yùn)算表的計算可以參考我在開源庫中的數(shù)學(xué)工具.[2]

有了乘法表,我們就可以在運(yùn)算過程中直接查表獲得結(jié)果,而不用進(jìn)行復(fù)雜的多項式運(yùn)算了.同時也不難發(fā)現(xiàn),查表優(yōu)化將會成為接下來工作的重點(diǎn)與難點(diǎn).

1.2選擇生成矩陣

生成矩陣(GM,generatormatrix)定義了如何將原始數(shù)據(jù)塊編碼為冗余數(shù)據(jù)塊,RS碼的生成矩陣是一個n行k列矩陣,將k塊原始數(shù)據(jù)塊編碼為n塊冗余數(shù)據(jù)塊.如果對應(yīng)的編碼是系統(tǒng)碼(比如RAID),編碼后包含了原始數(shù)據(jù),則生成矩陣中包含一個k×k大小的單位矩陣和(n?k)×k的冗余矩陣,單位矩陣對應(yīng)的是原始數(shù)據(jù)塊,冗余矩陣對應(yīng)的是冗余數(shù)據(jù)塊.非系統(tǒng)碼沒有單位矩陣,整個生成矩陣都是冗余矩陣,因此編碼后只有冗余數(shù)據(jù)塊.通常我們會使用系統(tǒng)碼以提高數(shù)據(jù)提取時的效率,那么接下來我們需要找到合適的冗余矩陣.

在解碼過程中我們要對矩陣求逆,因此所采用的矩陣必須滿足子矩陣可逆的性質(zhì).目前業(yè)界應(yīng)用最多的兩種矩陣是Vandermondematrix(范德蒙矩陣)和Cauchymatrix(柯西矩陣).其中范德蒙矩陣歷史最為悠久,但需要注意的是我們并不能直接使用范德蒙矩陣作為生成矩陣,而需要通過高斯消元后才能使用,這是因為在編碼參數(shù)(k+m)比較大時會存在矩陣不可逆的風(fēng)險.

柯西矩陣運(yùn)算簡單,只不過需要計算乘法逆元,我們可以提前計算好乘法逆元表以供生成編碼矩陣時使用.創(chuàng)建以柯西矩陣為生成矩陣的編碼矩陣的偽代碼如下圖所示：

1.3矩陣求逆運(yùn)算

有限域上的求逆方法和我們學(xué)習(xí)的線性代數(shù)中求逆方法相同,常見的是高斯消元法,算法復(fù)雜度是O(n^3).過程如下：

在待求逆的矩陣右邊拼接一個單位矩陣

進(jìn)行高斯消元運(yùn)算

取得到的矩陣左邊非單位矩陣的部分作為求逆的結(jié)果,如果不可逆則報錯

我們在實際的測試環(huán)境中發(fā)現(xiàn),矩陣求逆的開銷還是比較大的(大約6000ns/op).考慮到在實際系統(tǒng)中,單盤數(shù)據(jù)重建往往需要幾個小時或者更長(磁盤I/O占據(jù)絕大部分時間),求逆計算時間可以忽略不計.

二進(jìn)一步的工程優(yōu)化

2.1利用SIMD加速有限域運(yùn)算

從上一篇文章可知,有限域上的乘法是通過查表得到的,每個字節(jié)和生成矩陣中元素的乘法結(jié)果通過查表得到,圖1給出了按字節(jié)對原始數(shù)據(jù)進(jìn)行編碼的過程(生成多項式為x^8+x^4+x^3+x^2+1).對于任意1字節(jié)來說,在GF(2^8)內(nèi)有256種可能的值,所以沒有元素對應(yīng)的乘法表大小為256字節(jié).每次查表可以進(jìn)行一個字節(jié)數(shù)據(jù)的乘法運(yùn)算,效率很低.

圖 1, 按字節(jié)對原始數(shù)據(jù)進(jìn)行編碼

目前主流的支持SIMD相關(guān)指令的寄存器有128bit(XMM指令)、256bit(YMM指令)這兩種容量,這意味著對于64位的機(jī)器來說,分別提供了2到4倍的處理能力,我們可以考慮采用SIMD指令并行地為更多數(shù)據(jù)進(jìn)行乘法運(yùn)算.

但每個元素的乘法表的大小為256Byte,這大大超出了寄存器容納能力.為了達(dá)到利用并行查表的目的,我們采用分治的思想將兩個字節(jié)的乘法運(yùn)算進(jìn)行拆分.

字節(jié)y與字節(jié)a的乘法運(yùn)算過程可表示為,其中y(a)表示從y的乘法表中查詢與x相乘結(jié)果的操作：

y(a)=y*a
我們將字節(jié)a拆分成高4位(al)與低4位(ar)兩個部分,即(其中⊕為異或運(yùn)算)：

a=(al<<4)⊕ar

這樣字節(jié)a就表示為0-15與(0-15<<4)異或運(yùn)算的結(jié)果了.

于是原先的y與a的乘法運(yùn)算可表示為：

y(a)=y(al<<4)⊕y(ar)

由于ar與al的范圍均為0-15(0-1111),字節(jié)y與它們相乘的結(jié)果也就只有16個可能的值了.這樣原先256字節(jié)的字節(jié)y的乘法表就可以被2張16字節(jié)的乘法表替換了.

下面以根據(jù)本原多項式x^8+x^4+x^3+x^2+1生成的GF(2^8)為例,分別通過查詢普通乘法表與使用拆分乘法表來演示16*100的計算過程.

16的完整乘法表為：

 

計算16*100可以直接查表得到：

table[100] = 14

16 的低 4 位乘法表,也就是 16 與 0-15 的乘法結(jié)果：

lowtable=[0163248648096112128144160176192208224240]

16的高4位乘法表,為16與0-15<<4的乘法結(jié)果：

hightable=[02958391161057883232245210207156129166187]

將100(01100100)拆分,則：

100 = 0110 << 4 ⊕ 0100

在低位表中查詢0100(4),得：

lowtable[4]=64
在高位表中查詢 0110(6),得：

hightable[6]=78

將兩個查詢結(jié)果異或：

result=64^78=1000000^1001110=1110=14

從上面的對比中,我們不難發(fā)現(xiàn)采用SIMD的新算法提高查表速度主要表現(xiàn)在兩個方面：
減少了乘法表大小；
提高查表并行度(從1個字節(jié)到16甚至32個字節(jié))
采用SIMD指令在大大降低了乘法表的規(guī)模的同時多了一次查表操作以及異或運(yùn)算.由于新的乘法表每一部分只有16字節(jié),我們可以順利的將其放置于XMM寄存器中,從而利用SIMD指令集提供的指令來進(jìn)行數(shù)據(jù)向量運(yùn)算,將原先的逐字節(jié)查表改進(jìn)為并行的對16字節(jié)進(jìn)行查表,同時異或操作也是16字節(jié)并行的.除此之外,由于乘法表的總體規(guī)模的下降,在編碼過程中的緩存污染也被大大減輕了,關(guān)于緩存的問題我們會在接下來的小節(jié)中進(jìn)行更細(xì)致的分析.
以上的計算過程以單個字節(jié)作為例子,下面我們一同來分析利用SIMD技術(shù)對多個字節(jié)進(jìn)行運(yùn)算的過程.基本步驟如下：
拆分保存原始數(shù)據(jù)的XMM寄存器中的數(shù)據(jù)向量,分別存儲于不同的XMM寄存器中
根據(jù)拆分后的數(shù)據(jù)向量對乘法表進(jìn)行重排,即得到查表結(jié)果.我們可以將乘法表理解為按順序排放的數(shù)組,數(shù)組長度為16,查表的過程可以理解為將拆分后的數(shù)據(jù)(數(shù)據(jù)范圍為0-15)作為索引對乘法表數(shù)組進(jìn)行重新排序.這樣我們就可以通過排序指令完成查表操作了
將重排后的結(jié)果進(jìn)行異或,得到最終的運(yùn)算結(jié)果
以下是偽代碼：

需要注意的是,要使用SIMD加速有限域運(yùn)算,對CPU的最低要求是支持SSSE3擴(kuò)展指令集.另外為了充分提高效率,我們應(yīng)該事先對數(shù)據(jù)進(jìn)行內(nèi)存對齊操作,在SSSE3下我們需要將數(shù)據(jù)對齊到16Bytes,否則我們只能使用非對齊指令進(jìn)行數(shù)據(jù)的讀取和寫入.在這一點(diǎn)上比較特殊的是Go語言,一方面Go支持直接調(diào)用匯編函數(shù)這為使用SIMD指令集提供了語言上的支持；但另外一方面Golang又隱藏了內(nèi)存申請的細(xì)節(jié),這使得指定內(nèi)存對齊操作不可控,雖然我們也可以通過cgo或者匯編來實現(xiàn),但這增加額外的負(fù)擔(dān).所幸,對于CPU來說一個Cacheline的大小為64byte,這在一定程度上可以幫助我們減少非對齊讀寫帶來的懲罰.另外,根據(jù)Golang的內(nèi)存對齊算法,對于較大的數(shù)據(jù)塊,Golang是會自動對齊到32byte的,因此對齊或非對齊指令的執(zhí)行效果是一致的.

2.2寫緩存友好代碼

緩存優(yōu)化通過兩方面進(jìn)行,其一是減少緩存污染；其二是提高緩存命中率.在嘗試做到這兩點(diǎn)之前,我們先來分析緩存的基本工作原理.

CPU緩存的默認(rèn)工作模式是Write-Back,即每一次讀寫內(nèi)存數(shù)據(jù)都需要先寫入緩存.上文提到的Cacheline即為緩存工作的基本單位,其大小為固定的64byte,也就說哪怕從內(nèi)存中讀取1字節(jié)的數(shù)據(jù),CPU也會將其余的63字節(jié)帶入緩存.這樣設(shè)計的原因主要是為了提高緩存的時間局域性,因為所要執(zhí)行的數(shù)據(jù)大小通常遠(yuǎn)遠(yuǎn)超過這個數(shù)字,提前將數(shù)據(jù)讀取至緩存有利于接下來的數(shù)據(jù)在緩存中被命中.

2.2.1矩陣運(yùn)算分塊

矩陣運(yùn)算的循環(huán)迭代中都用到了行與列,因此原始數(shù)據(jù)矩陣與編碼矩陣的訪問總有一方是非連續(xù)的,通過簡單的循環(huán)交換并不能改善運(yùn)算的空間局域性.因此我們通過分塊的方法來提高時間局域性來減少緩存缺失.

分塊算法不是對一個數(shù)組的整行或整列進(jìn)行操作,而是對其子矩陣進(jìn)行操作,目的是在緩存中的數(shù)據(jù)被替換之前,最大限度的利用它.

分塊的尺寸不宜過大,太大的分塊無法被裝進(jìn)緩存；另外也不能過小,太小的分塊導(dǎo)致外部邏輯的調(diào)用次數(shù)大大上升,產(chǎn)生了不必要的函數(shù)調(diào)用開銷,而且也不能充分利用緩存空間.

2.2.2減少緩存污染

不難發(fā)現(xiàn)的是,編碼矩陣中的系數(shù)并不會完全覆蓋整個GF(2^8),例如10+4的編碼方案中,編碼矩陣中校驗矩陣大小為4×10,編碼系數(shù)至多(可能會有重復(fù))有10×4=40個.因此我們可以事先進(jìn)行一個乘法表初始化的過程,比如生成一個新的二維數(shù)組來存儲編碼系數(shù)的乘法表.縮小表的范圍可以在讀取表的過程中對緩存的污染.

另外在定義方法集時需要注意的是避免結(jié)構(gòu)體中的元素浪費(fèi).避免將不必要的參數(shù)扔進(jìn)結(jié)構(gòu)體中,如果每一個方法僅使用其中若干個元素,則其他元素白白侵占了緩存空間.

三指令級并行與數(shù)據(jù)級并行的深入優(yōu)化

本節(jié)主要介紹如何利用AVX/AVX2指令集以及指令級并行優(yōu)化來進(jìn)一步提高性能表現(xiàn).除此之外,我們還可以對匯編代碼進(jìn)行微調(diào)以取得微小的提升.比如,盡量避免使用R8-R15這8個寄存器,因為指令解碼會比其他通用寄存器多一個字節(jié).但很多匯編優(yōu)化細(xì)節(jié)是和CPU架構(gòu)設(shè)計相關(guān)的,書本上甚至Intel提供的手冊也并不能提供最準(zhǔn)確的指導(dǎo)(因為有滯后性),而且這些操作帶來的效益并不顯著,在這里就不做重點(diǎn)說明了.

3.1利用AVX2

在上文中我們已經(jīng)知道如何將乘法表拆分成128bits的大小以適應(yīng)XMM寄存器,那么對于AVX指令集來說,要充分發(fā)揮其作用,需要將乘法表復(fù)制到256bit的YMM寄存器.為了做到這一點(diǎn),我們可以利用XMM寄存器為YMM寄存器的低位這一特性,僅使用一條指令來完成表的復(fù)制(Intel風(fēng)格)：

vinserti128ymm0,ymm0,xmm0,1

這條指令作用是將xmm0寄存器中的數(shù)據(jù)拷貝到y(tǒng)mm0中,而剩余128位數(shù)據(jù)通過ymm0得到,其中立即數(shù)1表明xmm0拷貝的目的地是ymm0的高位.這條指令提供了兩個sourceoperand(源操作數(shù))以及一個destinationoperand(目標(biāo)操作數(shù)),我們在這里使用ymm0寄存器同時作為源操作數(shù)和目標(biāo)操作數(shù)來實現(xiàn)了表的復(fù)制操作.接下來我們便可以使用與SSSE3下同樣的方式來進(jìn)行單指令32byte的編碼運(yùn)算過程了.

由于使用了SSE與AVX這兩種擴(kuò)展指令集,我們需要避免AVX-SSETransitionPenalties[3].之所以會有這種性能懲罰主要是由于SSE指令對YMM寄存器的高位一無所知,SSE指令與AVX指令的混用會導(dǎo)致機(jī)器不斷的執(zhí)行YMM寄存器的高位保存與恢復(fù),這大大影響了性能表現(xiàn).如果對指令不熟悉,難以避免指令混用,那么可以在RET前使用VZEROUPPER指令來清空YMM寄存器的高位.

3.2指令級并行(ILP)優(yōu)化

程序分支指令的開銷并不僅僅為指令執(zhí)行所需要的周期,因為它們可能影響前端流水線和內(nèi)部緩存的內(nèi)容.我們可以通過如下技巧來減少分支指令對性能的影響,并且提高分支預(yù)測單元的準(zhǔn)確性：

盡量少的使用分支指令

當(dāng)貫穿(fall-through)更可能被執(zhí)行時,使用向前條件跳轉(zhuǎn)

當(dāng)貫穿代碼不太可能被執(zhí)行時,使用向后條件跳轉(zhuǎn)

向前跳轉(zhuǎn)經(jīng)常用在檢查函數(shù)參數(shù)的代碼塊中,如果我們避免了傳入長度為0的數(shù)據(jù)切片,這樣可以在匯編中去掉相關(guān)的分支判斷.在我的代碼中僅有一條向后條件跳轉(zhuǎn)指令,用在循環(huán)代碼塊的底部.需要注意的是,以上2、3點(diǎn)中的優(yōu)化方法是為了符合靜態(tài)分支預(yù)測算法的要求,然而在市場上基于硬件動態(tài)預(yù)測方法等處理器占主導(dǎo)地位,因此這兩點(diǎn)優(yōu)化可能并不會起到提高分支預(yù)測準(zhǔn)確度的作用,更多的是良好的編程習(xí)慣的問題.

對于CPU的執(zhí)行引擎來說,其往往包含多個執(zhí)行單元實例,這是執(zhí)行引擎并發(fā)執(zhí)行多個微操做的基本原理.另外CPU內(nèi)核的調(diào)度器下會掛有多個端口,這意味著每個周期調(diào)度器可以給執(zhí)行引擎分發(fā)多個微操作.因此我們可以利用循環(huán)展開來提高指令級并行的可能性.

循環(huán)展開就是將循環(huán)體復(fù)制多次,同時調(diào)整循環(huán)的終止代碼.由于它減少了分支判斷的次數(shù),因此可以將來自不同迭代的指令放在一起調(diào)度.

當(dāng)然,如果循環(huán)展開知識簡單地進(jìn)行指令復(fù)制,最后使用的都是同一組寄存器,可能會妨礙對循環(huán)的有效調(diào)度.因此我們應(yīng)當(dāng)合理分配寄存器的使用.另外,如果循環(huán)規(guī)模較大,會導(dǎo)致指令緩存的缺失率上升.Intel的優(yōu)化手冊中指出,循環(huán)體不應(yīng)當(dāng)超過500條指令.[4]

四小結(jié)

以上內(nèi)容較為完整的還原了糾刪碼引擎的實現(xiàn)過程,涉及到了較多的數(shù)學(xué)和硬件層面的知識,對于大部分工程師來說可能相對陌生,我們希望通過本系列文章的介紹能夠為大家的工程實踐提供些許幫助.但受限于篇幅,很多內(nèi)容無法全面展開.比如,部分?jǐn)?shù)學(xué)工具的理論與證明并沒有得到詳細(xì)的解釋,還需要讀者通過其他專業(yè)資料的來進(jìn)行更深入的學(xué)習(xí).

轉(zhuǎn)載請注明本頁網(wǎng)址：
http://www.fzlkiss.com/jiaocheng/4081.html