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

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

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

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

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

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

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

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

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

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

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

一理論工程化

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

1.1有限域運(yùn)算

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

此外,在有限域上運(yùn)算另一個(gè)重要的好處是運(yùn)算后的結(jié)果大小在一定范圍內(nèi),這是因?yàn)橛邢抻虻姆忾]性決定的,這也為程序設(shè)計(jì)提供了便利.比如在RS中,我們通常使用GF(2^8),即0～255這一有限域,這是因?yàn)槠溟L(zhǎng)度剛好為1字節(jié),便于我們對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和計(jì)算.

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

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

1.2選擇生成矩陣

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

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

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

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

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

在待求逆的矩陣右邊拼接一個(gè)單位矩陣

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

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

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

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

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

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

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

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

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

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

y(a)=y*a
我們將字節(jié)a拆分成高4位(al)與低4位(ar)兩個(gè)部分,即(其中⊕為異或運(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個(gè)可能的值了.這樣原先256字節(jié)的字節(jié)y的乘法表就可以被2張16字節(jié)的乘法表替換了.

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

16的完整乘法表為：

 

計(jì)算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

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

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

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

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

2.2寫緩存友好代碼

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

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

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

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

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

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

2.2.2減少緩存污染

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

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

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

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

3.1利用AVX2

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

vinserti128ymm0,ymm0,xmm0,1

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

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

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

程序分支指令的開(kāi)銷并不僅僅為指令執(zhí)行所需要的周期,因?yàn)樗鼈兛赡苡绊懬岸肆魉€和內(nèi)部緩存的內(nèi)容.我們可以通過(guò)如下技巧來(lái)減少分支指令對(duì)性能的影響,并且提高分支預(yù)測(cè)單元的準(zhǔn)確性：

盡量少的使用分支指令

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

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

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

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

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

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

四小結(jié)

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

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