基于FPGA 的軟硬件協(xié)同糾刪碼編碼加速方案

楊思捷，陳俊奇，王勇*，李樹林

（1.桂林電子科技大學(xué)計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué)廣西教育大數(shù)據(jù)與網(wǎng)絡(luò)安全協(xié)同創(chuàng)新中心，廣西 桂林 541004）

0 引言

近年來，隨著互聯(lián)網(wǎng)、云計(jì)算、云存儲(chǔ)等技術(shù)的快速發(fā)展，全球信息數(shù)據(jù)規(guī)模巨大并呈現(xiàn)爆炸式增長(zhǎng)，傳統(tǒng)存儲(chǔ)系統(tǒng)已無法滿足大數(shù)據(jù)存儲(chǔ)的功能和性能需求。在這樣的背景下，催生了對(duì)于高數(shù)據(jù)讀寫性能、可靠性、可拓展性的系統(tǒng)的需求。分布式存儲(chǔ)系統(tǒng)在大規(guī)模數(shù)據(jù)的存儲(chǔ)和管理中已被廣泛采用，例如Hadoop 分布式文件系統(tǒng)（HDFS）［1］、Swift 云存儲(chǔ)系統(tǒng)［2］以及Ceph 分布式文件系統(tǒng)［3］。

在分布式存儲(chǔ)系統(tǒng)中，由于存儲(chǔ)設(shè)備故障、系統(tǒng)崩潰、自然災(zāi)害、網(wǎng)絡(luò)故障等問題引起的節(jié)點(diǎn)失效進(jìn)一步導(dǎo)致了大量的數(shù)據(jù)丟失。為了避免數(shù)據(jù)丟失，提高存儲(chǔ)系統(tǒng)的可靠性，在分布式系統(tǒng)中一般采用兩種冗余機(jī)制的數(shù)據(jù)容錯(cuò)技術(shù)，分別是副本容錯(cuò)技術(shù)［4］和糾刪碼容錯(cuò)技術(shù)［5］。副本容錯(cuò)技術(shù)基于復(fù)制機(jī)制，系統(tǒng)將節(jié)點(diǎn)上原始數(shù)據(jù)塊復(fù)制到其他存儲(chǔ)節(jié)點(diǎn)上，提高了數(shù)據(jù)的可用性。糾刪碼容錯(cuò)技術(shù)基于編碼機(jī)制，通過將原始數(shù)據(jù)分割為k個(gè)數(shù)據(jù)塊，然后對(duì)這些數(shù)據(jù)塊編碼得到m個(gè)校驗(yàn)塊，當(dāng)數(shù)據(jù)塊丟失數(shù)量不超過m時(shí)，就可以從現(xiàn)有的數(shù)據(jù)塊和校驗(yàn)塊中恢復(fù)出原始數(shù)據(jù)。糾刪碼技術(shù)在提供與副本技術(shù)相同的容錯(cuò)能力的同時(shí)，能夠顯著降低存儲(chǔ)開銷。RS 類編碼［6］作為目前使用最為廣泛的糾刪碼算法，具有較好的空間利用率，與三副本技術(shù)相比，RS（14，10）在提高了1 倍容錯(cuò)能力的基礎(chǔ)上，降低了53%的存儲(chǔ)開銷［7］。隨著糾刪碼技術(shù)的發(fā)展，開源的糾刪碼庫(kù)為人們提供了多種解決方案。Jerasure開源糾刪碼庫(kù)［8］由C/C++語(yǔ)言編寫，能夠?qū)崿F(xiàn)多種糾刪碼，包括RS 碼、柯西RS 碼［9］、LRC 碼［10］等RS 類編碼，在最新的Jerasure 2.0 版本中，提供面向?qū)ο蟮慕涌冢黾恿?更多糾 刪碼的實(shí)現(xiàn)，例 如RDP 碼［11］、EVENODD 碼［12］、Blaum-Roth 碼［13］等陣列糾刪碼，支持多線程，在提高適用范圍的同時(shí)提升了計(jì)算效率。

糾刪碼技術(shù)的高可靠性和相對(duì)較低的存儲(chǔ)成本使其已經(jīng)廣泛應(yīng)用于數(shù)據(jù)中心［14］，但也在存儲(chǔ)過程中帶來了更多的計(jì)算開銷和編碼時(shí)延，若編碼速率過低，則在編碼過程中會(huì)發(fā)生數(shù)據(jù)丟失，原始數(shù)據(jù)塊將面臨無法恢復(fù)的風(fēng)險(xiǎn)。因此，糾刪碼的編碼效率不僅影響存儲(chǔ)系統(tǒng)性能，還會(huì)影響存儲(chǔ)系統(tǒng)的可靠性?，F(xiàn)場(chǎng)可編程門陣列（FPGA）［15］具有邏輯結(jié)構(gòu)可定制、高速并行計(jì)算、片上緩沖大、調(diào)度靈活等特點(diǎn)，在加速糾刪碼［16-17］方面具有以下3 個(gè)優(yōu)點(diǎn)：1）片上邏輯資源豐富，具有動(dòng)態(tài)重構(gòu)特性，可重復(fù)配置以減少硬件開銷；2）通過流水線并行設(shè)計(jì)來提高計(jì)算編解碼吞吐量；3）存儲(chǔ)器訪問帶寬需求相對(duì)較低，有利于有效且充分地利用可用的存儲(chǔ)器帶寬。在高速網(wǎng)絡(luò)通信中，F(xiàn)PGA 常用于實(shí)現(xiàn)低時(shí)延的前向糾錯(cuò)碼編解碼器［18］，然而通過仿真實(shí)驗(yàn)驗(yàn)證了現(xiàn)有的基于FPGA 的糾刪碼存儲(chǔ)加速方案在實(shí)際分布式存儲(chǔ)系統(tǒng)中可能存在通信可靠性較低及難以處理較大數(shù)據(jù)塊的問題。為減少糾刪碼編碼時(shí)延、提升糾刪碼容錯(cuò)存儲(chǔ)的性能和可靠性，本文設(shè)計(jì)基于FPGA 的分布式存儲(chǔ)系統(tǒng)糾刪碼編碼加速方案，并在實(shí)際的存儲(chǔ)環(huán)境下進(jìn)行了實(shí)驗(yàn)驗(yàn)證。本文主要工作如下：

1）設(shè)計(jì)基于FPGA 的RS 碼編碼硬件加速架構(gòu)，通過硬件描述語(yǔ)言實(shí)現(xiàn)RS（8，2）、RS（8，3）、RS（8，4）、RS（8，5）4 種容錯(cuò)能力的16×8 bit 并行RS 碼編碼器，通過優(yōu)化糾刪碼算法模塊的時(shí)序?qū)崿F(xiàn)流水線處理，進(jìn)一步提升編碼速率。

2）拓展片外4 GB DDR3 存儲(chǔ)器接口，當(dāng)存儲(chǔ)系統(tǒng)中需要編碼的數(shù)據(jù)塊較大時(shí)，可以利用其隨機(jī)存取特性將數(shù)據(jù)塊切分為更小的操作單位，便于編碼器進(jìn)行具體的數(shù)據(jù)計(jì)算，并且實(shí)現(xiàn)在上位機(jī)和FPGA之間的數(shù)據(jù)緩存管理，避免數(shù)據(jù)溢出，提升了數(shù)據(jù)通信的可靠性。

3）實(shí)現(xiàn)FPGA 與上位機(jī)的數(shù)據(jù)通信，在實(shí)際環(huán)境下通過了FPGA 的板級(jí)驗(yàn)證，并在不同規(guī)模數(shù)據(jù)量下進(jìn)行實(shí)驗(yàn)測(cè)試。

1 相關(guān)工作

1.1 糾刪碼原理

本文主要關(guān)注RS 碼，通常被表示為RS（k，m），其中，k表示原始數(shù)據(jù)塊數(shù)量，m表示編碼后生成的校驗(yàn)塊數(shù)量，當(dāng)數(shù)據(jù)發(fā)生丟失時(shí)可以通過任意k個(gè)數(shù)據(jù)塊或校驗(yàn)塊進(jìn)行數(shù)據(jù)恢復(fù)，最大可以容忍m個(gè)數(shù)據(jù)塊的丟失。給定原始數(shù)據(jù)集合D=｛D1，D2，…，Dk｝，Di表示第i個(gè)數(shù)據(jù)塊（1≤i≤k），校驗(yàn)數(shù)據(jù)集合C=｛C1，C2，…，Cm｝，Cj表示第j個(gè)校驗(yàn)塊（1≤j≤m），編碼計(jì)算是一個(gè)定義在伽羅華域GF（2w）［19］上的矩陣點(diǎn)乘，如式（1）所示：

在一次編碼過程中生成的所有數(shù)據(jù)塊和校驗(yàn)塊記為［D|C］T，稱為條帶，（k+m）×k階的矩陣稱為生成矩陣G，由m×k階的編碼矩陣A和k×k階的單位矩陣E構(gòu)成，記為G=［E|A］T，在RS 碼中使用范德蒙德矩陣作為編碼矩陣。伽羅華域是一種有限域，域內(nèi)包含2w個(gè)元素，其中定義了一種不可約的特殊多項(xiàng)式，稱為本原多項(xiàng)式P（x），通過構(gòu)建對(duì)數(shù)/反對(duì)數(shù)索引表的方法簡(jiǎn)化有限域上的乘法運(yùn)算，如式（2）所示：

其中：gflog 和gfilog 分別表示伽羅華域上的對(duì)數(shù)函數(shù)和反對(duì)數(shù)函數(shù)。反對(duì)數(shù)表和對(duì)數(shù)表的構(gòu)建如式（3）和式（4）所示：

當(dāng)條帶中丟失任意m個(gè)塊時(shí)，只需選取任意k個(gè)幸存的數(shù)據(jù)塊或校驗(yàn)塊組成一個(gè)新集合Ds，同時(shí)將集合Ds中元素所對(duì)應(yīng)的生成矩陣G中的行向量重組為一個(gè)k×k階的矩陣Gs，如式（5）所示：

對(duì)矩陣Gs求逆G-1s并代入式（5）即可恢復(fù)原始數(shù)據(jù)，如式（6）所示：

1.2 糾刪碼加速優(yōu)化研究

糾刪碼在實(shí)現(xiàn)數(shù)據(jù)冗余存儲(chǔ)的過程中，分布式存儲(chǔ)系統(tǒng)的性能主要面臨來自網(wǎng)絡(luò)資源消耗、編解碼計(jì)算效率、磁盤I/O 吞吐量3 個(gè)方面的挑戰(zhàn)。在存儲(chǔ)設(shè)備內(nèi)部，計(jì)算效率是影響存儲(chǔ)性能的主要因素，計(jì)算復(fù)雜性主要來源于編解碼過程中大量有限域上的矩陣乘法運(yùn)算。為提升計(jì)算效率，研究人員提出在CPU、GPU、FPGA 等不同架構(gòu)下的糾刪碼優(yōu)化加速方案。CHEN 等［20］設(shè)計(jì)一種基于多核CPU 的糾刪碼軟件（parEC），通過實(shí)現(xiàn)并行運(yùn)算，顯著提升了糾刪碼的計(jì)算吞吐量。孫黎等［21］通過優(yōu)化HRC 碼算法，提出了HRC 偏移重復(fù)碼，與三副本技術(shù)和S2-RAID 糾刪碼相比提升了容錯(cuò)性能，降低了修復(fù)開銷。LIU 等［22］利用GPU 的并行處理、矢量運(yùn)算等特性，提出一種基于GPU 的糾刪碼庫(kù)（GCRS），相比于Jerasure 開源糾刪碼庫(kù)編解碼速率提升了10 倍。許佳豪［23］設(shè)計(jì)一種基于GPU 的LRC 編碼優(yōu)化方案，采用異或編碼思想，直接對(duì)數(shù)據(jù)塊進(jìn)行移位變換和異或運(yùn)算，相比于GCRS 庫(kù)性能提升了3%～5%。CHEN等［24］分別在CPU、GPU、FPGA 和APU 架構(gòu)下實(shí)現(xiàn)了基于OpenCL 的伽羅華域GF（28）糾刪碼實(shí)現(xiàn)方案，針對(duì)每種架構(gòu)的特點(diǎn)提出不同的算法優(yōu)化策略，通過實(shí)驗(yàn)比較不同架構(gòu)下的加速效果，實(shí)驗(yàn)結(jié)果表明FPGA 性能優(yōu)越且相對(duì)成本較低。王先鵬［25］利用Xilinx HLS 工具實(shí)現(xiàn)對(duì)4 種RS 碼進(jìn)行編解碼加速，設(shè)計(jì)基于FPGA 的多速率RS 碼編解碼器，采用矩陣預(yù)處理的思想，將編解碼矩陣預(yù)先存儲(chǔ)在FPGA 的片上ROM 中，從而減少了糾刪碼編解碼過程中構(gòu)造矩陣所帶來的時(shí)延，并通過仿真驗(yàn)證其計(jì)算功能和效率，結(jié)果表明其能有效提高數(shù)據(jù)吞吐量。

在分布式存儲(chǔ)系統(tǒng)中，作為存儲(chǔ)單位的默認(rèn)數(shù)據(jù)塊一般比較大，比如在Hadoop 3.0［26］中默認(rèn)塊大小為128 MB，Ceph 的數(shù)據(jù)對(duì)象大小默認(rèn)為4 MB。當(dāng)這些數(shù)據(jù)對(duì)象被分為k個(gè)數(shù)據(jù)塊Di時(shí)，如果直接對(duì)其進(jìn)行RS（k，m）編碼，需要構(gòu)造一個(gè)大小為m×k×Dsize的 編碼矩 陣，Dsize表示每 個(gè)數(shù)據(jù) 塊Di的大小。Dsize越大，矩陣越大，用于運(yùn)算的對(duì)數(shù)/反對(duì)數(shù)索引表也越大，會(huì)占用更多的內(nèi)存，導(dǎo)致計(jì)算效率降低。因此，在實(shí)際的糾刪碼容錯(cuò)應(yīng)用中，通常不會(huì)直接對(duì)數(shù)據(jù)塊Di進(jìn)行編碼，而是將數(shù)據(jù)塊Di切分為更小的單位，稱為報(bào)文di，將報(bào)文作為數(shù)據(jù)編碼的基本單位［27］。文獻(xiàn)［24-25］分別使用FPGA 實(shí)現(xiàn)了細(xì)粒度為64 Byte 和1 Byte 的RS 碼編碼器，但忽略了對(duì)數(shù)據(jù)塊緩存和切片操作，導(dǎo)致上位機(jī)和FPGA 間通信可靠性較低，并且要求上位機(jī)將數(shù)據(jù)塊切分為更小的報(bào)文后再發(fā)送給FPGA，難以滿足分布式存儲(chǔ)系統(tǒng)的糾刪碼容錯(cuò)需求。本文的目標(biāo)是通過拓展FPGA片外存儲(chǔ)器接口，實(shí)現(xiàn)數(shù)據(jù)緩存和數(shù)據(jù)塊切片功能，利用FPGA 加速RS 碼編碼計(jì)算，從而提升數(shù)據(jù)寫入吞吐量。

2 基于FPGA 的軟硬件協(xié)同RS 碼編碼加速

為了提升基于糾刪碼容錯(cuò)機(jī)制的分布式存儲(chǔ)系統(tǒng)性能，本文提出一種基于FPGA 的軟硬件協(xié)同RS碼編碼加速方案。首先，對(duì)FPGA 進(jìn)行模塊化設(shè)計(jì)，實(shí)現(xiàn)對(duì)數(shù)據(jù)的接收、緩存、處理和發(fā)送；然后，設(shè)計(jì)RS 碼編碼器，利用對(duì)數(shù)/反對(duì)數(shù)索引表簡(jiǎn)化矩陣乘法運(yùn)算；最后，通過對(duì)RS 編碼器的并行化處理和時(shí)序優(yōu)化提升數(shù)據(jù)吞吐量。

2.1 基于FPGA 的RS 碼編碼硬件加速架構(gòu)

基于FPGA 設(shè)計(jì)的RS 碼編碼硬件加速架構(gòu)如圖1 所示。在FPGA 中設(shè)計(jì)4 個(gè)主要模塊：1）數(shù)據(jù)通信模塊，該模塊包含物理層和鏈路層；2）數(shù)據(jù)接收/發(fā)送模塊；3）用戶模塊，該模塊包含數(shù)據(jù)解析、糾刪碼算法、數(shù)據(jù)封裝3 個(gè)子模塊；4）DDR3 接口模塊。

圖1 基于FPGA 的RS 碼編碼硬件加速架構(gòu)Fig.1 FPGA-based hardware acceleration architecture of RS code encoding

FPGA 外部提供SFP 接口，支 持10 Gb/s 速率 通信，上位機(jī)可以通過萬(wàn)兆以太網(wǎng)接口與FPGA 實(shí)現(xiàn)數(shù)據(jù)通信。在該架構(gòu)中，糾刪碼算法模塊用200 MHz 時(shí)鐘驅(qū)動(dòng)，DDR3 接口的時(shí)鐘為雙沿800 MHz 時(shí)鐘，DDR3 內(nèi)部存儲(chǔ)陣列系統(tǒng)時(shí)鐘為200 MHz，其余模塊的驅(qū)動(dòng)用戶時(shí)鐘為156.25 MHz。在數(shù)據(jù)通信模塊中，物理層包括PMD、PMA、PCS 三層結(jié)構(gòu)，PMD 層實(shí)現(xiàn)物理連接。PMA 層將PMD 層傳來的串行差分?jǐn)?shù)據(jù)進(jìn)行時(shí)鐘恢復(fù)，轉(zhuǎn)化為66 bit 的并行數(shù)據(jù)，如果數(shù)據(jù)來自PCS 層，則將66 bit 并行數(shù)據(jù)轉(zhuǎn)化為串行差分?jǐn)?shù)據(jù)。PCS 層主要功能為實(shí)現(xiàn)64/66 bit 信道編解碼，MAC 核與PCS 層之間通過XGMII 接口傳輸數(shù)據(jù)。MAC 核將下層數(shù)據(jù)去掉前導(dǎo)碼、起始符和幀校驗(yàn)序列，轉(zhuǎn)為MAC 幀后發(fā)送到更上層，對(duì)于來自上層的數(shù)據(jù)則增加前導(dǎo)碼、起始符，計(jì)算幀校驗(yàn)序列。在數(shù)據(jù)接收/發(fā)送模塊中，根據(jù)AXIS 總線時(shí)序，在數(shù)據(jù)接收時(shí)將來自數(shù)據(jù)通信模塊的兩個(gè)時(shí)鐘周期的64 bit 數(shù)據(jù)合并成128 bit 數(shù)據(jù)后，增加起始符、有效標(biāo)識(shí)符后發(fā)送到用戶模塊。用戶模塊首先解析數(shù)據(jù)包，去掉數(shù)據(jù)報(bào)文頭部后只保留數(shù)據(jù)部分，通過DDR3 接口存入DDR3 中。糾刪碼算法模塊從DDR3 通過地址索引獲取數(shù)據(jù)進(jìn)行RS 碼編碼。數(shù)據(jù)封裝模塊對(duì)編碼完成的數(shù)據(jù)添加數(shù)據(jù)報(bào)文頭部后發(fā)送給數(shù)據(jù)接收/發(fā)送模塊。

2.2 并行RS 碼編碼器設(shè)計(jì)

通過硬件描述語(yǔ)言Verilog HDL 實(shí)現(xiàn)對(duì)RS（8，2）、RS（8，3）、RS（8，4）、RS（8，5）4 種RS 碼的編碼計(jì)算進(jìn)行硬件加速。圖2 為RS 碼編碼器框架以及主要信號(hào)，編碼器中所有相關(guān)運(yùn)算定義在GF（28）內(nèi)，本原多項(xiàng)式P（x）=x8+x4+x3+x2+1，根據(jù)P（x）生成512 Byte的對(duì)數(shù)/反對(duì)數(shù)索引表，存儲(chǔ)一個(gè)大小為16～40 Byte的編碼矩陣，矩陣大小由RS（k，m）中的參數(shù)k和m決定，使用200 MHz 時(shí)鐘驅(qū)動(dòng)，數(shù)據(jù)報(bào)文位寬為8 bit。

圖2 RS 碼編碼器框架Fig.2 Framework of RS code encoder

在數(shù)據(jù)編碼過程中，8 bit 位寬的原始數(shù)據(jù)報(bào)文輸入RS 編碼器，同時(shí)拉高輸入有效信號(hào)，當(dāng)最后一個(gè)數(shù)據(jù)報(bào)文即第k個(gè)報(bào)文輸入時(shí)，拉高輸入數(shù)據(jù)尾部標(biāo)識(shí)信號(hào)。在輸入完成后，原始數(shù)據(jù)報(bào)文和編碼矩陣進(jìn)行有限域上的矩陣乘法運(yùn)算得到編碼數(shù)據(jù)報(bào)文，其中包括查表操作和異或運(yùn)算，需要3 個(gè)時(shí)鐘周期。在計(jì)算完成后，編碼器開始輸出編碼報(bào)文條帶，同時(shí)拉高輸出有效信號(hào)，當(dāng)最后一個(gè)編碼報(bào)文即第k+m個(gè)編碼報(bào)文輸出時(shí)，拉高輸出數(shù)據(jù)尾部標(biāo)識(shí)信號(hào)。整個(gè)編碼流程需要消耗k+m+3 個(gè)時(shí)鐘周期，即（k+m+3）×5 ns。

在該框架下，1 個(gè)時(shí)鐘周期內(nèi)只能處理1 Byte 數(shù)據(jù)，吞吐量較低，難以滿足分布式存儲(chǔ)系統(tǒng)對(duì)糾刪碼容錯(cuò)的高性能需求。因此，在本文設(shè)計(jì)的糾刪碼算法模塊中實(shí)例化了16 個(gè)這樣的RS 碼編碼器，通過并行化處理，使其在1 個(gè)時(shí)鐘周期內(nèi)的數(shù)據(jù)處理量達(dá)到16 Byte，并且優(yōu)化了接口時(shí)序，從而提升了數(shù)據(jù)吞吐量。圖3 為糾刪碼算法模塊實(shí)現(xiàn)RS（8，4）編碼的主要接口時(shí)序圖。模塊用2 個(gè)時(shí)鐘周期從DDR3 中讀取8個(gè)大小為16 Byte 的原始數(shù)據(jù)報(bào)文，記錄為di（1≤i≤8），對(duì)應(yīng)的接口信號(hào)為DDR2AL_data；數(shù)據(jù)報(bào)文di依次輸入RS 編碼器，對(duì)應(yīng)信號(hào)接口為RS_input_data，最后一個(gè)數(shù)據(jù)報(bào)文d8輸入編碼器后開始計(jì)算校驗(yàn)報(bào)文cj（1≤j≤4）；編碼器輸出接口RS_output_data 從數(shù)據(jù)報(bào)文輸入3 個(gè)時(shí)鐘周期后開始輸出報(bào)文條帶，既確保了每個(gè)校驗(yàn)報(bào)文計(jì)算所需的時(shí)延，又提升了編碼效率；AL2FIFO_data 表示糾刪碼算法模塊向數(shù)據(jù)封裝模塊發(fā)送數(shù)據(jù)的接口，模塊之間定義了一個(gè)異步FIFO 用于跨時(shí)鐘域數(shù)據(jù)傳輸，RS 編碼器輸出第1 個(gè)校驗(yàn)報(bào)文c1，經(jīng)過1 個(gè)時(shí)鐘周期后算法模塊向數(shù)據(jù)封裝模塊 發(fā)送數(shù) 據(jù)；RS_input_valid、RS_input_last、RS_output_valid 和RS_output_last 分別對(duì)應(yīng)編碼器輸入有效、編碼器輸入尾部標(biāo)識(shí)、編碼器輸出有效和編碼器輸出尾部標(biāo)識(shí)，均為高電平有效。總流程耗時(shí)18 個(gè)時(shí)鐘周期，編碼流程耗時(shí)15 個(gè)時(shí)鐘周期。

2.3 基于FPGA 的RS 碼編碼加速實(shí)現(xiàn)

FPGA 作為加速RS 碼編碼的外部硬件設(shè)備需要與上位機(jī)進(jìn)行數(shù)據(jù)通信，采用萬(wàn)兆以太網(wǎng)實(shí)現(xiàn)FPGA與上位機(jī)的通信，傳輸層協(xié)議為UDP 通信協(xié)議。為了能有效獲取上位機(jī)下發(fā)的數(shù)據(jù)塊信息并支持FPGA 計(jì)算，對(duì)數(shù)據(jù)信息格式進(jìn)行設(shè)計(jì)，其中主要包括MAC 幀首部、IP 首部、UDP 首部和數(shù)據(jù)字段大小。FPGA 接口對(duì)應(yīng)的MAC 地址為58∶69∶6C∶69∶6E∶78，IP 地址為192.168.1.101。數(shù)據(jù)字段大小規(guī)定為128～1 408 Byte，且為128 Byte（8 個(gè)原始數(shù)據(jù)報(bào)文）的整數(shù)倍。

在上節(jié)中實(shí)現(xiàn)了基于FPGA 的RS 碼硬件加速算法，每個(gè)用于編碼的數(shù)據(jù)報(bào)文大小為16 Byte。為了滿足分布式存儲(chǔ)系統(tǒng)中數(shù)據(jù)對(duì)象的編碼需求，需要在FPGA 和上位機(jī)之間增加一個(gè)緩存結(jié)構(gòu)，將接收到的數(shù)據(jù)塊Di進(jìn)一步劃分為大小為16 Byte 的數(shù)據(jù)報(bào)文di。拓展片外4 GB DDR3 接口用于實(shí)現(xiàn)數(shù)據(jù)緩存和數(shù)據(jù)塊分片，地址結(jié)構(gòu)如圖4 所示，其中高3 位［28∶26］被分配為列地址，每一列對(duì)應(yīng)一個(gè)數(shù)據(jù)塊Di，低26 位［25∶0］被分配為行地址，在這個(gè)存儲(chǔ)陣列中，每個(gè)存儲(chǔ)單元可以存儲(chǔ)8 Byte 數(shù)據(jù)。由于DDR3 接口模塊采用雙沿800 MHz 時(shí)鐘，因此在200 MHz 的時(shí)鐘下存取128 Byte 數(shù)據(jù)即8 個(gè)用于編碼的數(shù)據(jù)報(bào)文只需要2 個(gè)時(shí)鐘周期。

圖4 DDR3 地址結(jié)構(gòu)Fig.4 DDR3 address structure

圖5 為基于FPGA 的RS 碼編碼加速架構(gòu)下的RS（8，4）編碼過程，主要步驟如下：

圖5 RS（8，4）編碼過程Fig.5 RS（8，4）encoding process

步驟1上位機(jī)將數(shù)據(jù)對(duì)象劃分為8 個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊大小相等，為nByte，構(gòu)成的數(shù)據(jù)塊集合定義為D=｛D1，D2，…，D8｝，按順序通過萬(wàn)兆以太網(wǎng)接口并以上文規(guī)定的數(shù)據(jù)包格式發(fā)送給FPGA。

步驟2FPGA 通過光纖接收到數(shù)據(jù)信號(hào)后，經(jīng)過數(shù)據(jù)通信模塊和數(shù)據(jù)接收模塊的處理，串行差分?jǐn)?shù)據(jù)信號(hào)被轉(zhuǎn)化為128 bit 并行數(shù)據(jù)后傳入用戶模塊中的數(shù)據(jù)解析模塊。

步驟3數(shù)據(jù)解析模塊去掉UDP 數(shù)據(jù)包首部，只保留數(shù)據(jù)字段，通過DDR3 接口模塊存入DDR3，其中數(shù)據(jù)塊序號(hào)對(duì)應(yīng)列地址，例如D1對(duì)應(yīng)的列地址為000。

步驟4當(dāng)所有的數(shù)據(jù)塊都存入DDR3 后，糾刪碼算法模塊通過DDR3 接口模塊從DDR3 的存儲(chǔ)陣列中按行地址讀取數(shù)據(jù)，一次讀取128 Byte，分為8 個(gè)數(shù)據(jù)報(bào)文，每個(gè)報(bào)文大小為16 Byte，構(gòu)成的數(shù)據(jù)報(bào)文集合定義為d=｛d1，d2，…，d8｝。

步驟5算法對(duì)數(shù)據(jù)報(bào)文集合d進(jìn)行編碼運(yùn)算，計(jì)算出4 個(gè)校驗(yàn)報(bào)文，構(gòu)成校驗(yàn)報(bào)文的集合定義為c=｛c1，c2，c3，c4｝。

步驟6糾刪碼算法模塊將校驗(yàn)報(bào)文集合c放入糾刪碼算法模塊與數(shù)據(jù)封裝模塊之間的FIFO 暫存，每當(dāng)FIFO 中存儲(chǔ)的校驗(yàn)報(bào)文集合達(dá)到11 個(gè)即704 Byte 時(shí)，將數(shù)據(jù)封裝為UDP 數(shù)據(jù)包傳輸給數(shù)據(jù)發(fā)送模塊。

步驟7判斷編碼算法是否已經(jīng)執(zhí)行次，若是則進(jìn)入步驟8，否則回到步驟4。

步驟8判斷FIFO 是否為空，若是則直接進(jìn)入步驟9，否則將FIFO 中的數(shù)據(jù)封裝后傳輸?shù)綌?shù)據(jù)發(fā)送模塊，進(jìn)入步驟9。

步驟9數(shù)據(jù)發(fā)送模塊和數(shù)據(jù)通信模塊將UDP數(shù)據(jù)包恢復(fù)為串行差分?jǐn)?shù)據(jù)信號(hào)后通過光纖發(fā)送給上位機(jī)，整個(gè)編碼過程結(jié)束。

3 實(shí)驗(yàn)測(cè)試與分析

本節(jié)測(cè)試FPGA 對(duì)4 種容錯(cuò)能力不同的RS 碼在不同數(shù)據(jù)量下的加速效果，主要關(guān)注編碼速率vencoding和數(shù)據(jù)寫入吞吐量vtotal2 個(gè)性能指標(biāo)，計(jì)算公式分別如式（7）、式（8）所示：

其中：k表示原始數(shù)據(jù)塊個(gè)數(shù)；n表示每個(gè)數(shù)據(jù)塊的大?。籺encoding表示數(shù)據(jù)編碼時(shí)延，即原始?jí)K輸入RS 編碼器到最后一個(gè)校驗(yàn)塊輸出的耗時(shí)；tdownload為編碼數(shù)據(jù)下載時(shí)延；twr為數(shù)據(jù)寫入DDR3 的時(shí)延；trd為FPGA的算法模塊從DDR3 讀取數(shù)據(jù)的時(shí)延；tupload為數(shù)據(jù)上傳時(shí)延。為了驗(yàn)證本次實(shí)驗(yàn)結(jié)果，將所提方案與Jerasure 2.0 開源糾刪碼庫(kù)（記為Jerasure 2.0 方案）進(jìn)行結(jié)果對(duì)比，實(shí)驗(yàn)結(jié)果顯示所提方案表現(xiàn)更優(yōu)，并且編碼數(shù)據(jù)量越小，性能越好。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)硬件加速平臺(tái)為Xilinx VC709 評(píng)估板，屬于Xilinx 公司的Virtex-7 系列FPGA 開發(fā)板，該系列的芯片具有高集成度、強(qiáng)大的數(shù)據(jù)處理能力以及高可拓展性。表1 為實(shí)驗(yàn)硬件環(huán)境主要參數(shù)。

表1 實(shí)驗(yàn)硬件環(huán)境 Table 1 Experiment hardware environment

表2 為用于對(duì)照實(shí)驗(yàn)的Jerasure 2.0 開源糾刪碼庫(kù)的軟件實(shí)驗(yàn)環(huán)境主要參數(shù)。

表2 軟件實(shí)驗(yàn)環(huán)境 Table 2 Software experiment environment

3.2 編碼性能測(cè)試

選用編碼速率vencoding和數(shù)據(jù)寫入吞吐量vtotal作為比較糾刪碼編碼性能是否優(yōu)良的指標(biāo)，作為對(duì)照實(shí)驗(yàn)的Jerasure 2.0 開源庫(kù)的源碼給出了這兩個(gè)速率的計(jì)算方案，在對(duì)文件進(jìn)行數(shù)據(jù)編碼后可以直接得到。

所提方案通過Xilinx VC709 上的200 MHz 系統(tǒng)時(shí)鐘來記錄FPGA 執(zhí)行數(shù)據(jù)下載、DDR3 讀寫、數(shù)據(jù)編碼和數(shù)據(jù)上傳消耗的時(shí)鐘周期數(shù)，在編碼完成后FPGA 向上位機(jī)發(fā)送1 個(gè)時(shí)鐘周期數(shù)記錄數(shù)據(jù)包，包結(jié)構(gòu)如圖6 所示，可以看出：數(shù)據(jù)下載和上傳的時(shí)延最大，用32 bit 記 錄；DDR 讀寫較 快，用16 bit 記錄；編碼算法用24 bit 記錄；最后8 bit 暫作保留。

圖6 時(shí)鐘周期數(shù)記錄數(shù)據(jù)包Fig.6 Clock cycle number recording data packet

通過式（9）可得到FPGA 執(zhí)行每個(gè)操作的時(shí)延，其中，頻率f=200 MHz，Tn表示時(shí)鐘周期數(shù)，結(jié)合式（7）、式（8）計(jì)算編碼速率和數(shù)據(jù)寫入吞吐量。

實(shí)驗(yàn)測(cè) 試兩種 方案對(duì)RS（8，2）、RS（8，3）、RS（8，4）、RS（8，5）4 種RS 編碼模式在14 KB、140 KB、1 400 KB、14 MB、42 MB 5 種不同大小的測(cè)試文件上的加速效果，RS 碼的各項(xiàng)參數(shù)設(shè)置如表3所示。

表3 RS 碼參數(shù)設(shè)置 Table 3 RS code parameter setting

3.3 結(jié)果分析

Jerasure 2.0方案和所提方案在4種RS碼的不同測(cè)試文件大小下的編碼算法平均速率對(duì)比曲線圖如圖7所示，具體數(shù)據(jù)如表4 所示。由于所提方案的編碼速率不隨文件大小而改變，因此只用一條曲線表示。

表4 平均編碼速率對(duì)比數(shù)據(jù)Table 4 Comparison data of average encoding rate 單位：（MB·s-1）

圖7 平均編碼速率對(duì)比曲線Fig.7 Comparison curve of average encoding rate

從測(cè)試結(jié)果可以發(fā)現(xiàn)，所提方案的編碼速率相對(duì)恒定，文件的測(cè)試大小不會(huì)成為影響算法速率的因素，對(duì)于較小文件的編碼有顯著優(yōu)勢(shì)。與Jerasure 2.0方案相比，在橫向上所提方案的算法速率隨著RS 碼校驗(yàn)塊數(shù)量的增加而緩慢降低，在縱向上所提方案在大多數(shù)情況下為最優(yōu)或與其相當(dāng)，僅在編碼模式為RS（8，2）時(shí)比Jerasure 2.0 方案（42 MB）略差。所提方案和Jerasure 2.0 方案（42 MB）在編碼模式為RS（8，3）時(shí)產(chǎn)生了交叉節(jié)點(diǎn)，這是因?yàn)镴erasure 2.0 方案對(duì)大文件的編碼能力較強(qiáng)，但是隨著校驗(yàn)塊數(shù)量的增加，計(jì)算生成矩陣和編碼運(yùn)算的復(fù)雜度隨之增加，導(dǎo)致Jerasure 2.0 方案（42 MB）的編碼性能曲線下降段的斜率較大，而所提方案在編碼器中預(yù)存了生成矩陣，并且將編碼運(yùn)算的查表操作和異或運(yùn)算均勻分配到每個(gè)用于計(jì)算的時(shí)鐘周期，使得編碼性能曲線下降段的斜率較小。

對(duì)于糾刪碼存儲(chǔ)而言，除了編碼算法層面的時(shí)間開銷外，系統(tǒng)的I/O、矩陣生成、對(duì)文件劃分操作等同樣存在大量時(shí)間開銷，對(duì)系統(tǒng)性能產(chǎn)生重要影響。圖8為Jerasure 2.0 方案和所提方案對(duì)4 種RS 碼在不同測(cè)試文件大小下的平均數(shù)據(jù)寫入吞吐量對(duì)比。由圖8可以看出，使用所提方案的糾刪碼編碼的數(shù)據(jù)寫入吞吐量提升了2.7～93.0 倍，并且Jerasure 2.0 方案在處理不同數(shù)據(jù)量時(shí)，數(shù)據(jù)寫入吞吐量波動(dòng)較大，當(dāng)數(shù)據(jù)量較小時(shí)由于此時(shí)的系統(tǒng)I/O、矩陣生成和數(shù)據(jù)劃分時(shí)間開銷很大，導(dǎo)致系統(tǒng)運(yùn)行速率明顯降低，而所提方案在處理不同數(shù)據(jù)量時(shí)由于編碼矩陣已經(jīng)預(yù)先寫入FPGA 的RAM 中，因此能夠以較恒定的速率運(yùn)行。

4 結(jié)束語(yǔ)

針對(duì)糾刪碼容錯(cuò)機(jī)制在分布式存儲(chǔ)系統(tǒng)中存在編碼時(shí)延高、數(shù)據(jù)吞吐量小的問題，本文提出一種基于FPGA 的RS 碼編碼加速方案。利用FPGA 實(shí)現(xiàn)高效的并行RS 碼編碼器，同時(shí)擴(kuò)展DDR3 接口用于緩存管理和數(shù)據(jù)切片，并且在由上位機(jī)和FPGA 組成的糾刪碼編碼硬件加速架構(gòu)中進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，在不同規(guī)模的數(shù)據(jù)量下，所提方案相比Jerasure 2.0 開源糾刪碼庫(kù)能夠大幅度提升RS 碼的編碼速率與數(shù)據(jù)寫入吞吐量，并且對(duì)于較小的文件具有更顯著的性能提升。下一步將針對(duì)柯西RS 碼的編解碼優(yōu)化展開研究，提升糾刪碼容錯(cuò)機(jī)制在數(shù)據(jù)寫入和數(shù)據(jù)修復(fù)方面的綜合性能。