陳曉杰，李 斌，周清雷

（1.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南鄭州 450001；2.鄭州大學(xué)計(jì)算機(jī)與人工智能學(xué)院,河南鄭州 450001）

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）匹配過(guò)濾.

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

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

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

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

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

1）沒(méi)有匹配，則原樣輸出；

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

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

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

進(jìn)一步將數(shù)據(jù)進(jìn)行轉(zhuǎn)換，如果len 為0，則將數(shù)據(jù)Dn單獨(dú)輸出，此時(shí)offset 為0，同時(shí)，增加未壓縮字符計(jì)數(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ī)則進(jìn)行編碼，編碼格式內(nèi)容如圖5所示.

圖5 編碼格式

圖5 中每個(gè)虛線框內(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 算法的計(jì)算量較小，但是包含了大量的數(shù)據(jù)比較和匹配，并且需要大容量字典存儲(chǔ)數(shù)據(jù)，因此，要實(shí)現(xiàn)高效的Snappy 算法需要對(duì)算法的關(guān)鍵路徑、存儲(chǔ)需求以及實(shí)現(xiàn)結(jié)構(gòu)進(jìn)行優(yōu)化.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

也即式（8）所示：

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

表1 主要模塊資源占用

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

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

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

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

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

圖14 不同芯片性能對(duì)比

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

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

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

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

圖15 性能對(duì)比

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

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

表4 不同板卡單核算法對(duì)比

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

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

表5 不同板卡對(duì)比

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

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

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