RTL級可擴展高性能數(shù)據(jù)壓縮方法實現(xiàn)

陳曉杰，李 斌，周清雷

（1.數(shù)學(xué)工程與先進計算國家重點實驗室，河南鄭州 450001；2.鄭州大學(xué)計算機與人工智能學(xué)院,河南鄭州 450001）

1 引言

隨著信息技術(shù)的迅速發(fā)展，5G網(wǎng)絡(luò)逐步普及，接入互聯(lián)網(wǎng)的設(shè)備將迅速增長，根據(jù)相關(guān)統(tǒng)計和預(yù)測，到2025 年，接入互聯(lián)網(wǎng)的設(shè)備將達到5 000 億［1］.通信設(shè)備的急劇增加導(dǎo)致數(shù)據(jù)量呈現(xiàn)爆炸式的增長，為了應(yīng)對海量數(shù)據(jù)的處理，逐步形成了在邊緣計算、內(nèi)存計算、智能計算等模式下，以數(shù)據(jù)為中心的新一代計算網(wǎng)絡(luò).但是，大量的網(wǎng)絡(luò)數(shù)據(jù)帶來的網(wǎng)絡(luò)負載和存儲問題仍然制約著網(wǎng)絡(luò)性能的進一步發(fā)展.

數(shù)據(jù)壓縮技術(shù)在滿足用戶獲取原信息的同時，通過有效的編碼，能夠減少數(shù)據(jù)量，在數(shù)據(jù)的存儲管理和網(wǎng)絡(luò)數(shù)據(jù)傳輸方面得到了有效的應(yīng)用［2，3］.數(shù)據(jù)壓縮分為有損壓縮和無損壓縮，前者主要應(yīng)用于視頻和圖像，即使某些數(shù)據(jù)的丟失對于用戶的感官也沒有太大的影響，代表的算法有基于離散余弦變換的數(shù)據(jù)壓縮、基于小波的數(shù)據(jù)壓縮和基于線性預(yù)測編碼的數(shù)據(jù)壓縮等.后者主要應(yīng)用于數(shù)據(jù)正確性要求較高的場景，代表的算法有LZ77、RLE（Run-Length Encoding）、Snappy 等.其中LZ77 算法較復(fù)雜，且需要消耗較大的內(nèi)存和計算資源［4］，RLE 主要應(yīng)用于位圖壓縮［5］，通用性較低，而Snappy 是Google 開源的壓縮/解壓縮庫，在滿足一定壓縮率的條件下，具有較高的壓縮速度，已經(jīng)被應(yīng)用到內(nèi)存數(shù)據(jù)庫和電子探測器的高容量數(shù)據(jù)壓縮方面［6，7］.

為了降低數(shù)據(jù)存儲和網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)南拗频葐栴}，同時滿足接收端獲取完整的數(shù)據(jù)，采用Snappy 無損壓縮算法對數(shù)據(jù)進行壓縮處理.傳統(tǒng)的數(shù)據(jù)壓縮算法主要以軟件的形式在CPU 上進行實現(xiàn)，壓縮速度較低，并且應(yīng)用場景有限，而GPU 主要應(yīng)用于密集型計算的任務(wù)，能耗較高.FPGA 具有低功耗、可重構(gòu)、能效低等特點，近幾年被廣泛應(yīng)用于邊緣神經(jīng)網(wǎng)絡(luò)的加速［8］、高速的數(shù)據(jù)加密［9］、并行數(shù)據(jù)壓縮［10］等，在FPGA 上實現(xiàn)數(shù)據(jù)壓縮算法能夠在有限帶寬的限制下，極大的提高數(shù)據(jù)傳輸速度［11］.因此，本文首先分析Snappy 數(shù)據(jù)壓縮算法的結(jié)構(gòu)特征和算法流程；然后針對Snappy 算法進行RTL 級實現(xiàn)，并采用多種有效方法進行深度優(yōu)化，例如專用并行數(shù)據(jù)匹配、訪存優(yōu)化、流水線技術(shù)等，同時，采用輪詢策略、流水線數(shù)據(jù)轉(zhuǎn)換等實現(xiàn)多通道的數(shù)據(jù)壓縮算法，使算法能夠動態(tài)擴展，進一步提高算法性能；最后通過算法實現(xiàn)、性能測試、性能對比等實驗，驗證本文實現(xiàn)方法的加速效果和性價比.

2 數(shù)據(jù)壓縮原理及算法分析

Snappy 壓縮算法是基于hash 值運算的字典匹配壓縮，如果兩組數(shù)據(jù)計算hash 值的結(jié)果相同，則兩組數(shù)據(jù)相等的概率較大.最初版本Snappy 算法流程首先將待壓縮數(shù)據(jù)分為32 KB 大小的塊分別進行壓縮，然后在32 KB 數(shù)據(jù)中對每字節(jié)數(shù)據(jù)與其相鄰的3 字節(jié)數(shù)據(jù)計算hash 值，并在字典中獲取有相同hash 值的數(shù)據(jù)，進行匹配、壓縮，最后對處理后的數(shù)據(jù)進行編碼輸出.但是，原始的算法壓縮及硬件實現(xiàn)效果較差.

Xilinx 在高端數(shù)據(jù)板卡Alveo U200 中對Snappy 算法進行了改進實現(xiàn)［12］，降低了壓縮率，壓縮速度達到了10 GB/s，但是Xilinx 是由高級編程語言實現(xiàn)壓縮算法，只能應(yīng)用在特定FPGA 芯片，可移植性較低，因此，本文對Xilinx改進后的Snappy算法進行RTL級實現(xiàn)，在不損失算法壓縮率的情況下，提高壓縮速度和算法可移植性.改進后的Snappy算法處理框架如圖1所示.

圖1 Snappy數(shù)據(jù)壓縮框架

首先對數(shù)據(jù)劃分為64 KB 大小的block 塊，然后對每個塊進行四個階段的處理，完成數(shù)據(jù)的壓縮和編碼，最后將每個塊的壓縮結(jié)果寫入Snappy 文件，四個處理階段是整個算法的核心，也是本文分析和實現(xiàn)的重點，詳細分析如下：

（1）索引字典建立和初匹配.

初匹配階段是數(shù)據(jù)擴充階段，用于獲得匹配的可能性，這一階段對輸入的字節(jié)數(shù)據(jù)進行處理，計算對應(yīng)的匹配偏移offset和匹配長度len.

首先初始化索引字典和滑動窗口，索引字典的內(nèi)容包含3 字節(jié)的索引值和6 字節(jié)的數(shù)據(jù)，存儲結(jié)構(gòu)如圖2所示，索引值是6字節(jié)數(shù)據(jù)中第一個字節(jié)數(shù)據(jù)在block塊的位置index.

圖2 索引字典存儲結(jié)構(gòu)

其次，依次讀取待壓縮內(nèi)容，并寫入滑動窗口，根據(jù)滑動窗口內(nèi)容計算哈希值，以哈希值為字典索引，讀取索引位置內(nèi)容，并將窗口內(nèi)容和索引值寫入哈希值對應(yīng)的字典中.

然后將讀取內(nèi)容與窗口內(nèi)容進行匹配，此時匹配的最大長度為6字節(jié).

最后，以當(dāng)前的數(shù)據(jù)Dn、匹配偏移offset 和匹配長度len 共同構(gòu)成Vn并輸出，其中offset 由索引值之差計算，處理結(jié)構(gòu)示意圖如圖3所示.

圖3 壓縮第一階段處理結(jié)構(gòu)圖

圖3 中索引字典的每行存儲6 組數(shù)據(jù)，每組數(shù)據(jù)的長度是54 字節(jié)，存儲在字典中同一行的6 組數(shù)據(jù)具有相同的hash 值，例如在字典中的hashNum 地址對應(yīng)的值包含6組數(shù)據(jù)，表示為Bh～Bh+5，每組數(shù)據(jù)的內(nèi)容如式（1）所示.

當(dāng)計算滑動窗口的值滿足hash（window）=hashNum時，則將匹配窗口的值和6 組數(shù)據(jù)進行匹配，同時更新hashNum 地址對應(yīng)的字典行，行內(nèi)數(shù)據(jù)變?yōu)锽h+1、Bh+2、Bh+3、Bh+4、Bh+5、index、window.以上即完成字典的更新，在這個階段每組數(shù)據(jù)的最大匹配長度為6，每個數(shù)據(jù)都有輸出，代表了其自身和之后的5個數(shù)據(jù)與具有相同哈希值組的最大匹配.

（2）匹配過濾.

首先填充比較窗口，每個窗口存放的值是第一階段輸出的三部分組成的值.然后，讀取窗口0 的值Vn，并將窗口左移，同時，讀入一組數(shù)據(jù)Vn+6，重新填滿比較窗口.最后，將Vn與窗口中的每個值進行條件過濾.如果滿足，原樣輸出，否則將匹配長度與匹配偏移賦值為0.其中，過濾條件為Vn的匹配長度與比較窗口位置相加大于比較窗口值的匹配長度.處理結(jié)構(gòu)如圖4所示.

圖4 壓縮第二階段處理結(jié)構(gòu)圖

這一階段是獲取最優(yōu)匹配的可能性，并將匹配效果較差的數(shù)據(jù)設(shè)置為0匹配.

（3）最大匹配和數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換.

這一階段是數(shù)據(jù)壓縮階段，通過前兩階段的篩選，此時可以將匹配數(shù)據(jù)進行壓縮，處理過程是逐個讀取Vn，獲取匹配偏移，然后通過偏移從匹配字典中讀取數(shù)據(jù)進行最大匹配，并將匹配數(shù)據(jù)丟棄，從而完成壓縮，匹配分為三種情況：

1）沒有匹配，則原樣輸出；

2）有匹配，且偏移offset≤16 K，則依次讀取數(shù)據(jù)，并丟棄，只記錄匹配長度，最大匹配長度為64；

3）有匹配，且偏移offset＞16 K，則根據(jù)匹配長度，讀取相應(yīng)數(shù)據(jù)進行丟棄；

此時，可得到數(shù)據(jù)Dn，改變后的匹配長度len，以及匹配偏移offset.

進一步將數(shù)據(jù)進行轉(zhuǎn)換，如果len 為0，則將數(shù)據(jù)Dn單獨輸出，此時offset 為0，同時，增加未壓縮字符計數(shù)litCount，共同作為匹配信息輸出.如果不為0，則將數(shù)據(jù)Dn丟棄，只輸出匹配數(shù)據(jù)len 和offset，且litCount 為0.轉(zhuǎn)換后的數(shù)據(jù)分為數(shù)據(jù)Dn和匹配信息match_info（len，offset，litCount）.

4）數(shù)據(jù)編碼階段.

根據(jù)litCount、len、offset 的值按照Snappy 規(guī)則進行編碼，編碼格式內(nèi)容如圖5所示.

圖5 編碼格式

圖5 中每個虛線框內(nèi)的上方表示編碼bit 位的索引，下方為編碼內(nèi)容，從上到下為三種編碼格式：

（1）數(shù)據(jù)未壓縮；

（2）len＜12，offset＜2048；

（3）211≤offset≤216并且len≤64，或者，11＜len≤64 并且offset＜211.

從算法流程可以看出Snappy 算法的計算量較小，但是包含了大量的數(shù)據(jù)比較和匹配，并且需要大容量字典存儲數(shù)據(jù)，因此，要實現(xiàn)高效的Snappy 算法需要對算法的關(guān)鍵路徑、存儲需求以及實現(xiàn)結(jié)構(gòu)進行優(yōu)化.

3 并行Snappy壓縮算法實現(xiàn)

為了滿足算法的計算、存儲、通信需求，實現(xiàn)高性能的Snappy 算法，本文結(jié)合FPGA 的芯片資源分布，布局布線的特點，以及頻率對時序的影響等，對算法的關(guān)鍵路徑、存儲需求以及實現(xiàn)結(jié)構(gòu)等多方面進行細粒度優(yōu)化.

3.1 定制化并行數(shù)據(jù)匹配

Snappy算法的前兩個階段都包含6次數(shù)據(jù)匹配，是整個算法的關(guān)鍵路徑，消耗較長時間，因此，需要對窗口的數(shù)據(jù)匹配進行優(yōu)化.

對于第一個階段的數(shù)據(jù)匹配，將滑動窗口數(shù)據(jù)與來自于索引字典中的6組數(shù)據(jù)分別進行匹配，匹配如算法1所示.

算法1 中主要的消耗時間為兩層循環(huán)，即6 個字節(jié)的匹配時間tbyte_match和6組數(shù)據(jù)的匹配時間tdata_match，總時間為6tbyte_match×6tdata_match.而每組數(shù)據(jù)匹配時相互獨立，因此，可進行并行匹配，并行匹配如算法2所示.

算法2 中步1～10 是通過generate 生成器并行化6個模塊，則6tdata_match可在1個tdata_match時間內(nèi)完成.步3～8 是并行字節(jié)匹配，消耗時間為1tbyte_match，由于是并行匹配，只能獲得每個字節(jié)是否匹配，因此，增加flag作為匹配標(biāo)記，并以flag為function_long函數(shù)的輸入，求得每組數(shù)據(jù)的匹配長度len，最后以len 為輸入，通過function_max 函數(shù)，求得最終匹配長度.在RTL 實現(xiàn)中，函數(shù)function_long 和function_max 通過組合邏輯進行實現(xiàn)，消耗時間較少，因此，通過并行匹配，關(guān)鍵路徑消耗的總時間為1tbyte_match，極大的減少了時間復(fù)雜度.

在并行匹配的過程成，包含兩步操作，賦值和匹配，布線路徑從compare 到flag，如果在一個時鐘內(nèi)進行實現(xiàn)，消耗大量的查找表資源，增加時序影響，因此，添加buff_com和buff_win寄存器用于中間緩存，減少FPGA布局布線的路由復(fù)雜度，同時，將字節(jié)匹配的過程分為數(shù)據(jù)賦值和匹配兩個模塊，RTL實現(xiàn)如算法3所示.

通過增加寄存器資源減少查找表資源，使并行匹配消耗的物理時間為2個時鐘周期，定制化并行匹配硬件實現(xiàn)結(jié)構(gòu)如圖6所示.時鐘clk貫穿6個并行模塊，在每個模塊內(nèi)，第一個時鐘完成寄存器賦值，第二個時鐘進行邏輯運算，實現(xiàn)匹配判斷，并通過時序邏輯在較短的時延內(nèi)計算匹配長度，從而兩個時鐘可完成并行匹配.

圖6 定制化并行匹配硬件實現(xiàn)結(jié)構(gòu)

3.2 細粒度串并混合結(jié)構(gòu)

Snappy 算法對每個字節(jié)數(shù)據(jù)進行多次處理，具有重復(fù)性，在數(shù)據(jù)壓縮過程中，數(shù)據(jù)具有單向流動性，F(xiàn)PGA 的各種邏輯計算單元具有獨立性，通過時鐘驅(qū)動可實現(xiàn)資源的并行，因此，Snappy 壓縮算法可在FPGA上采用流水線進行實現(xiàn).

數(shù)據(jù)壓縮的前三個階段在實現(xiàn)中共細分為15個子任務(wù)模塊，第一階段分別為讀數(shù)據(jù)、寫滑動窗口、哈希值計算、讀字典、數(shù)據(jù)匹配和輸出緩存，其中數(shù)據(jù)匹配經(jīng)過優(yōu)化后分為寄存器賦值和并行匹配，共7 個子任務(wù).第二階段分別為讀窗口數(shù)據(jù)、每個窗口的條件過濾匹配和最后的輸出緩存，同樣，過濾匹配也分為寄存器賦值和并行匹配，共4 個子任務(wù).第三階段分別為接收數(shù)據(jù)、讀字典、匹配、數(shù)據(jù)轉(zhuǎn)換，共4 個子任務(wù)，即處理1字節(jié)數(shù)據(jù)需要經(jīng)過15個子任務(wù).

在編碼階段，由于數(shù)據(jù)是經(jīng)過壓縮后的數(shù)據(jù)，數(shù)據(jù)量變小，并且在不同的條件下處理兩種數(shù)據(jù)，采用流水線實現(xiàn)會增加計算復(fù)雜度，消耗大量的計算資源，因此，在這一部分的實現(xiàn)上采用串行的狀態(tài)機進行實現(xiàn)，而在處于讀取明文的處理狀態(tài)中，最大需要64 次讀取數(shù)據(jù)，通過計數(shù)器控制可進行連續(xù)讀取，即使在沒有壓縮的極端情況下，仍然可滿足要求.Snappy 實現(xiàn)結(jié)構(gòu)如圖7所示.

圖7 Snappy算法實現(xiàn)結(jié)構(gòu)

圖7 中流水線數(shù)據(jù)壓縮部分表示壓縮過程中的15個子運行模塊，數(shù)據(jù)從輸入到輸出一共需要消耗15 個時鐘，并且15個子模塊并行計算，形成15級流水線.通過連續(xù)的讀取數(shù)據(jù)，15個時鐘之后，每個時鐘處理一組數(shù)據(jù)，相當(dāng)于每個字節(jié)數(shù)據(jù)只需要1 個時鐘，極大的提高了算法性能.

通過細粒度的串-并混合的結(jié)構(gòu)設(shè)計，實現(xiàn)Snappy算法，能夠最大的提高算法性能，同時，編碼階段采用了串行實現(xiàn)，在滿足條件的情況下，可減少資源的利用和電路的負載，從而降低功耗.

3.3 面向硬件的多級緩存優(yōu)化

隨機存取存儲器（Random Access Memory，RAM）包含地址線和數(shù)據(jù)線，將指定的數(shù)據(jù)寫入指定的地址內(nèi)，且讀取數(shù)據(jù)后不會造成數(shù)據(jù)丟失.先進先出存儲器（First In First Out，F(xiàn)IFO）沒有地址的約束，實現(xiàn)較簡單，主要用于數(shù)據(jù)緩存.因此，利用RAM 和FIFO 分別對字典實現(xiàn)和訪存進行存儲優(yōu)化.

（1）字典實現(xiàn)

Snappy 壓縮算法中第一、三階段中都包含對字典的操作，通過計算索引并從索引位置存取數(shù)據(jù)，字典的空間較大，在FPGA 中實現(xiàn)字典可采用寄存器和Block RAM 進行實現(xiàn)，而前者消耗了有限的寄存器資源和查找表資源，對于較大的字典使得資源利用不充分.Block RAM 是FPGA 上專用存儲單元，分布在邏輯計算資源的邊界上，因此，采用Block RAM 實現(xiàn)字典，操作結(jié)構(gòu)如圖8所示.

圖8 字典實現(xiàn)及操作結(jié)構(gòu)

Block RAM 實現(xiàn)的字典操作結(jié)構(gòu)中，當(dāng)有存儲請求時，通過時鐘inclk 觸發(fā)執(zhí)行，在控制總線作用下，將數(shù)據(jù)indata存儲到地址inaddr；當(dāng)有讀取請求時，通過時鐘outclk 觸發(fā)執(zhí)行，從地址outaddr 讀取相應(yīng)數(shù)據(jù)outdata，存儲器中索引地址與hash 值一一對應(yīng).進行流水線計算過程中，讀寫操作分別只需要一個時鐘即可完成，滿足高性能的數(shù)據(jù)操作要求，具有較大的存儲和通信效率.

（2）訪存優(yōu)化

由于FPGA 內(nèi)沒有足夠的存儲單元，而數(shù)據(jù)壓縮需要數(shù)據(jù)存儲到本地或者實時的傳輸?shù)紽PGA 中，并且壓縮的數(shù)據(jù)是連續(xù)的，因此，利用內(nèi)存DDR 與FPGA 的連接，將待壓縮的數(shù)據(jù)存儲到DDR 中，進行壓縮時，直接從內(nèi)存存取數(shù)據(jù).FPGA 與DDR 之間通過IP 核MIG（Memory Interface Generator）進行連接，采用AXI4 通信協(xié)議實現(xiàn)物理層面數(shù)據(jù)傳輸，為了滿足Snappy 算法高速的數(shù)據(jù)輸入，需要對訪存進行優(yōu)化，實現(xiàn)FPGA 與DDR的高效數(shù)據(jù)傳輸，實現(xiàn)結(jié)構(gòu)如圖9所示.

圖9 訪存優(yōu)化結(jié)構(gòu)

FPGA與DDR之間設(shè)計多級緩存機制進行優(yōu)化，首先，添加讀內(nèi)存緩存模塊，在該模塊中預(yù)先計算待壓縮數(shù)據(jù)的地址并存儲在fifo_addr_rd 中，通過讀控制狀態(tài)機讀取地址，再利用AXI4 協(xié)議從DDR 中讀取數(shù)據(jù).其次，將讀取的數(shù)據(jù)寫入fifo_data_rd 中，Snappy 算法根據(jù)FIFO 的空滿信號讀取數(shù)據(jù).然后，添加寫內(nèi)存控制模塊，并將壓縮后的數(shù)據(jù)存入fifo_data_wr 中，最后，預(yù)先計算寫內(nèi)存地址，并存入fifo_addr_wr，寫控制狀態(tài)機通過AXI4協(xié)議根據(jù)地址將相應(yīng)數(shù)據(jù)寫入DDR中.

DDR 與Snappy算法之間增加了兩個緩存控制模塊和多級緩存，使算法的實現(xiàn)與地址之間進行解耦和，數(shù)據(jù)之間只存在FIFO操作，并且操作的端口相互獨立，最大化的減少各模塊之間的相關(guān)性，從而降低布線路由的復(fù)雜度.

Snappy 壓縮算法在FPGA 上僅占用較小部分的計算與存儲資源，并且隨著工藝的提升，芯片資源也在不斷增加，因此，采用多通道并行方法，當(dāng)有大量的數(shù)據(jù)需要壓縮處理時，對數(shù)據(jù)進行劃分，通過邏輯控制將多個Snappy 算法并行處理，實現(xiàn)最優(yōu)性能.同時也可提高算法在不同芯片上的可擴展性.

內(nèi)存具有地址映射的功能，包含控制總線、數(shù)據(jù)總線和地址總線，數(shù)據(jù)存儲內(nèi)存的位置和大小可預(yù)先計算，因此，設(shè)計的第一步是不同通道的數(shù)據(jù)劃分，Snappy 算法將待壓縮的數(shù)據(jù)按照64 KB 大小進行block劃分，數(shù)據(jù)是連續(xù)的，對于不同的通道，通過地址偏移將處理通道與待壓縮數(shù)據(jù)進行一一對應(yīng)，多通道實現(xiàn)如圖10所示.

圖10 多通道并行結(jié)構(gòu)

在整個結(jié)構(gòu)中，F(xiàn)PGA 內(nèi)包含一個主控制模塊，用于將內(nèi)存的數(shù)據(jù)進行劃分，并計算不同block 的大小和偏移地址，然后按照Snappy 返回的偏移地址從內(nèi)存中獲取數(shù)據(jù)，順序存入到不同通道對應(yīng)的FIFO中，并啟動相應(yīng)的Sanppy 算法進行壓縮.壓縮結(jié)束后，主控制模塊將壓縮后的數(shù)據(jù)順序?qū)懭雰?nèi)存指定位置.

主控制模塊與DDR 的交互只有一個通道，而與算法之間具有N個并行通道，因此，從內(nèi)存取數(shù)據(jù)的速度speedDDR與Snappy的壓縮速度speed應(yīng)該滿足式（4）.

FPGA 與DDR 之間通過AXI4通信協(xié)議實現(xiàn)物理層面的高速數(shù)據(jù)傳輸，支持突發(fā)式數(shù)據(jù)傳輸，即一次請求響應(yīng)的交互中，可以傳輸多組數(shù)據(jù)，每組數(shù)據(jù)為256位，突發(fā)長度（Burst length）在1 和255 之間.因此，采用順序輪詢策略進行訪存操作的數(shù)據(jù)存儲，結(jié)構(gòu)如圖11所示.

圖11 中starti_addr_offsetj表示第i個通道、第j組數(shù)據(jù)的偏移地址，首先，主控制模塊順序從地址FIFO中讀取地址，然后AXI4協(xié)議順序從DDR 讀取數(shù)據(jù)并存入數(shù)據(jù)FIFO 中，最后主控制模塊通過輪詢狀態(tài)機將數(shù)據(jù)傳輸?shù)较鄳?yīng)Snappy 算法中.假設(shè)整個FPGA 實現(xiàn)的頻率為100 MHz，則單位時間內(nèi)壓縮數(shù)據(jù)量如式（5）：

圖11 訪存數(shù)據(jù)輪詢存儲結(jié)構(gòu)

內(nèi)存數(shù)據(jù)傳輸量如式（6）：

其中l(wèi)en 表示突發(fā)傳輸長度，timedelay表示從內(nèi)存?zhèn)鬏斠淮螖?shù)據(jù)的總消耗時間，只需滿足式（7）：

也即式（8）所示：

由于采用的是輪詢策略，則單個壓縮通道在單輪數(shù)據(jù)輸入滿足式（9）：

前者表示輪詢一周需要的時間，len+2 表示輪詢單個通道需要的時間，狀態(tài)轉(zhuǎn)換和FIFO 啟動需要消耗兩個時鐘，后者表示輪詢一次傳輸?shù)臄?shù)據(jù)量，只有滿足公式才能保證單通道內(nèi)連續(xù)的數(shù)據(jù)輸入.最大通道數(shù)和突發(fā)長度根據(jù)實際板卡性能進行可變的擴展，滿足上述要求，從而實現(xiàn)FPGA最大數(shù)據(jù)壓縮性能.

3.4 基于移位器的流水線數(shù)據(jù)轉(zhuǎn)換

FPGA 與DDR 通信數(shù)據(jù)位寬是多字節(jié)，而Snappy算法是單字節(jié)處理，因此，需要對Snappy 算法接收到的數(shù)據(jù)快速轉(zhuǎn)化為單字節(jié)進行處理，壓縮后的數(shù)據(jù)同樣需要將單字節(jié)數(shù)據(jù)快速拼接為多字節(jié)數(shù)據(jù)輸出.

多字節(jié)轉(zhuǎn)換單字節(jié)的原理是將多字節(jié)數(shù)據(jù)經(jīng)過移位器處理，從而獲得單字節(jié)數(shù)據(jù)，硬件實現(xiàn)如圖12所示.

圖12 單字節(jié)轉(zhuǎn)換硬件實現(xiàn)原理

各處理模塊以時鐘clk 為觸發(fā)條件并行計算，移位計數(shù)器是在一定時間內(nèi)請求數(shù)據(jù)；移位器將多字節(jié)數(shù)據(jù)每次向右移動8 位，輸出單字節(jié)數(shù)據(jù)和移位后的數(shù)據(jù)；多字節(jié)數(shù)據(jù)處理中，通過輸入數(shù)據(jù)是否有效，從而判斷接收的數(shù)據(jù)是移位后的數(shù)據(jù)或者是輸入數(shù)據(jù)；數(shù)據(jù)有效標(biāo)記是與輸出的單子節(jié)數(shù)據(jù)一一對應(yīng)，表示輸出數(shù)據(jù)有效.當(dāng)有大量的數(shù)據(jù)需要處理時，每個時鐘都有數(shù)據(jù)輸出.

本文中，處理的數(shù)據(jù)為32字節(jié)，RTL 實現(xiàn)的并行處理如算法4 所示，其中valid 表示數(shù)據(jù)有效，算法分為兩個部分，第一部分添加計數(shù)器，32 個周期獲取一組輸入，第二部分則是輸出賦值，由于FPGA 是并行計算，只要有輸入時鐘，各模塊運算不會終止，因此，增加flag標(biāo)記，表明數(shù)據(jù)的有效.兩部分并行處理，通過算法4 的實現(xiàn)，使數(shù)據(jù)轉(zhuǎn)換能夠流水線的連續(xù)輸出.

單字節(jié)轉(zhuǎn)換為多字節(jié)可通過對算法4進行修改，首先輸入單字節(jié)數(shù)據(jù)，然后對數(shù)據(jù)進行移位拼接，最后依據(jù)計數(shù)器輸出.通過對數(shù)據(jù)轉(zhuǎn)換的高速實現(xiàn)，使Snappy算法從輸入到輸出形成連續(xù)的數(shù)據(jù)處理鏈，在流水線的處理中，滿足各個部件的滿負載運行.

4 實驗結(jié)果與分析

本文采用的硬件為Zynq-7035，搭載的FPGA芯片包含邏輯單元（Logic Cells）270 K、查找表（LUT）171900、500（17.6 Mb）存儲大小的Block RAM以及343 800個觸發(fā)器（Flip-flops）等，與FPGA連接的內(nèi)存DDR存儲為1 GB，并且內(nèi)存數(shù)據(jù)的數(shù)據(jù)通信帶寬最高為50 Gb/s，硬件板卡有PCIE通道，可將PC機數(shù)據(jù)傳輸?shù)桨遢d內(nèi)存中.

FPGA與DDR之間支持突發(fā)式數(shù)據(jù)傳輸，而不同突發(fā)長度影響請求響應(yīng)信號，從而導(dǎo)致實際的數(shù)據(jù)帶寬存在差異.為了滿足Snappy 算法的性能最優(yōu)，需要保證數(shù)據(jù)能夠滿足Snappy 的輸入，因此，對FPGA 與DDR之間的數(shù)據(jù)通信，設(shè)計不同突發(fā)傳輸大小并進行測試，在不同時鐘頻率下，結(jié)果如圖13所示.

圖13 在不同頻率下FPGA與DDR通信帶寬

從圖13 中可以看出隨著突發(fā)長度的增長，通信帶寬成正比增長，當(dāng)突發(fā)長度大于32時，通信帶寬在測試板卡中趨于平穩(wěn)，即使在100 MHz 的時鐘頻率下，帶寬達到3 057 MB/s，因此，將DDR 與FPGA 的突發(fā)傳輸長度設(shè)計為32，可滿足數(shù)據(jù)壓縮的通信傳輸要求.

在單通道下，對Snappy 算法的RTL 實現(xiàn)進行綜合布線，實現(xiàn)頻率為148 MHz，各主要模塊所占資源結(jié)果如表1 所示.從表1 的資源占用可以計算出Snappy 核心算法模塊占總資源的1.1%，資源占用量較小.

表1 主要模塊資源占用

在單通道計算模式下對不同數(shù)據(jù)進行壓縮，壓縮速度如表2 所示.從表2 可以看出在FPGA 上優(yōu)化實現(xiàn)的算法在性能上基本達到了實際的頻率，即采用串-并混合的優(yōu)化結(jié)構(gòu)達到了與全流水線相同的性能.

表2 不同數(shù)據(jù)壓縮速度

以單通道算法的資源使用量為參考，可以計算出FPGA 芯片的總資源滿足四通道并行的Snappy算法，實現(xiàn)結(jié)果的資源占用如表3所示.

表3 四通道下Snappy算法資源占用

由于核心算法增加了3倍，使軟件自動化布線的復(fù)雜度增加，需要增加資源的占用從而增加布線的成功率，因此，在四通道下資源比單通道下占用較多，但是，與整片芯片相比仍然具有較小的資源占用率，最后實現(xiàn)的頻率為139 MHz，壓縮性能與不同CPU 進行對比，結(jié)果如圖14所示.

圖14 不同芯片性能對比

從圖14中可以看出本文實現(xiàn)的結(jié)果與CPU相比具有較高的性能優(yōu)勢.

加速比（Speed up）是衡量加速效果的指標(biāo)之一，指的是程序串行運行的時間與并行運行的時間的比值［13］，計算如式（10）：

其中data 為待壓縮數(shù)據(jù)的數(shù)據(jù)量，通過計算可得FPGA與CPU（i5-8500）的加速比為1.634，具有較高的加速效果.

研究者對于RTL 級的Snappy 算法研究較少，而LZ4 算法與Snappy 算法具有類似的壓縮方法，因此，將Snappy算法與LZ4算法進行對比，如圖15所示.

圖15 性能對比

圖15中不同文獻采用的芯片為28 nm，與同類型算法相比，在相同工藝的硬件上，本文實現(xiàn)的壓縮算法在性能上具有較大的優(yōu)勢.

Xilinx 公司給出了在FPGA 上實現(xiàn)Snappy 單個執(zhí)行核的資源結(jié)果，與本文實現(xiàn)的單通道結(jié)果對比如表4所示.

表4 不同板卡單核算法對比

表4 中PRR 是性能資源比（Performance Resource Ratio），表示單個LUT 資源的性能，數(shù)值越大，資源利用率越高.由于所使用的芯片工藝差別較大，本文實現(xiàn)的性能頻率略低，使得PRR 略低于Xilinx 的結(jié)果，但是在資源占用方面，LUT 資源與Xilinx 給出的結(jié)果下降了36.7%，具有較大的資源優(yōu)勢.

Xilinx 在Alveo U200 上通過多通道并行實現(xiàn)了高性能的Snappy 壓縮算法，與本文的結(jié)果進行對比，如表5所示.

表5 不同板卡對比

從表5中可以看出本文的實現(xiàn)性能略低，但是綜合的性價比要高于U200，表明本文所提方案具有較大的可行性和實際應(yīng)用價值.

5 結(jié)束語

隨著信息技術(shù)的迅速發(fā)展，網(wǎng)絡(luò)上的數(shù)據(jù)量呈爆炸式增長，同時，F(xiàn)PGA 作為計算設(shè)備、網(wǎng)絡(luò)設(shè)備、存儲設(shè)備得到了廣泛應(yīng)用，為了解決網(wǎng)絡(luò)負載和數(shù)據(jù)存儲問題，在有限帶寬下提高數(shù)據(jù)發(fā)送量，同時增加數(shù)據(jù)存儲量.提出了在FPGA 上實現(xiàn)Snappy 算法，通過多種FPGA 優(yōu)化方法進行RTL 編碼，實現(xiàn)的結(jié)果占用面積較少、性能較高.通過對算法的擴展，可將算法應(yīng)用到邊緣設(shè)備、數(shù)據(jù)中心等要求性能更高的數(shù)據(jù)處理領(lǐng)域.