RTL級可擴展高性能數據壓縮方法實現

陳曉杰，李 斌，周清雷

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

1 引言

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

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

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

2 數據壓縮原理及算法分析

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

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

圖1 Snappy數據壓縮框架

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

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

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

首先初始化索引字典和滑動窗口，索引字典的內容包含3 字節的索引值和6 字節的數據，存儲結構如圖2所示，索引值是6字節數據中第一個字節數據在block塊的位置index.

圖2 索引字典存儲結構

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

然后將讀取內容與窗口內容進行匹配，此時匹配的最大長度為6字節.

最后，以當前的數據Dn、匹配偏移offset 和匹配長度len 共同構成Vn并輸出，其中offset 由索引值之差計算，處理結構示意圖如圖3所示.

圖3 壓縮第一階段處理結構圖

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

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

（2）匹配過濾.

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

圖4 壓縮第二階段處理結構圖

這一階段是獲取最優匹配的可能性，并將匹配效果較差的數據設置為0匹配.

（3）最大匹配和數據結構轉換.

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

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

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

3）有匹配，且偏移offset＞16 K，則根據匹配長度，讀取相應數據進行丟棄；

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

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

4）數據編碼階段.

根據litCount、len、offset 的值按照Snappy 規則進行編碼，編碼格式內容如圖5所示.

圖5 編碼格式

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

（1）數據未壓縮；

（2）len＜12，offset＜2048；

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

從算法流程可以看出Snappy 算法的計算量較小，但是包含了大量的數據比較和匹配，并且需要大容量字典存儲數據，因此，要實現高效的Snappy 算法需要對算法的關鍵路徑、存儲需求以及實現結構進行優化.

3 并行Snappy壓縮算法實現

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

3.1 定制化并行數據匹配

Snappy算法的前兩個階段都包含6次數據匹配，是整個算法的關鍵路徑，消耗較長時間，因此，需要對窗口的數據匹配進行優化.

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

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

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

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

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

圖6 定制化并行匹配硬件實現結構

3.2 細粒度串并混合結構

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

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

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

圖7 Snappy算法實現結構

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

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

3.3 面向硬件的多級緩存優化

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

（1）字典實現

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

圖8 字典實現及操作結構

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

（2）訪存優化

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

圖9 訪存優化結構

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

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

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

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

圖10 多通道并行結構

在整個結構中，FPGA 內包含一個主控制模塊，用于將內存的數據進行劃分，并計算不同block 的大小和偏移地址，然后按照Snappy 返回的偏移地址從內存中獲取數據，順序存入到不同通道對應的FIFO中，并啟動相應的Sanppy 算法進行壓縮.壓縮結束后，主控制模塊將壓縮后的數據順序寫入內存指定位置.

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

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

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

圖11 訪存數據輪詢存儲結構

內存數據傳輸量如式（6）：

其中len 表示突發傳輸長度，timedelay表示從內存傳輸一次數據的總消耗時間，只需滿足式（7）：

也即式（8）所示：

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

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

3.4 基于移位器的流水線數據轉換

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

多字節轉換單字節的原理是將多字節數據經過移位器處理，從而獲得單字節數據，硬件實現如圖12所示.

圖12 單字節轉換硬件實現原理

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

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

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

4 實驗結果與分析

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

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

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

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

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

表1 主要模塊資源占用

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

表2 不同數據壓縮速度

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

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

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

圖14 不同芯片性能對比

從圖14中可以看出本文實現的結果與CPU相比具有較高的性能優勢.

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

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

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

圖15 性能對比

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

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

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

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

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

表5 不同板卡對比

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

5 結束語

隨著信息技術的迅速發展，網絡上的數據量呈爆炸式增長，同時，FPGA 作為計算設備、網絡設備、存儲設備得到了廣泛應用，為了解決網絡負載和數據存儲問題，在有限帶寬下提高數據發送量，同時增加數據存儲量.提出了在FPGA 上實現Snappy 算法，通過多種FPGA 優化方法進行RTL 編碼，實現的結果占用面積較少、性能較高.通過對算法的擴展，可將算法應用到邊緣設備、數據中心等要求性能更高的數據處理領域.