朱 嘉，劉紅俠

(西安電子科技大學(xué) 微電子學(xué)院，陜西 西安 710071)

隨著世界進入數(shù)字時代，每分鐘都有成百上千的視頻、照片上傳和下載，移動處理終端和服務(wù)器的數(shù)據(jù)帶寬需求越來越高，導(dǎo)致多核片上系統(tǒng)設(shè)計的復(fù)雜度逐年升高，數(shù)據(jù)業(yè)務(wù)量以指數(shù)級增長。無損數(shù)據(jù)壓縮技術(shù)在實時系統(tǒng)中對于存儲空間的節(jié)省和系統(tǒng)運行的速度起到關(guān)鍵作用。無損壓縮有很多算法，如游程編碼，哈夫曼編碼[1-2]，LZ77編碼等[3-5]。基于不同應(yīng)用要求，無損壓縮實現(xiàn)的方法各有不同。

Deflate算法[1]是一種基于歷史數(shù)據(jù)的字典查找，并且在編碼過程按照熵原理是[6]不會丟失任何信息的壓縮方式。該技術(shù)常以軟件方式實現(xiàn)，方式配置靈活，但存在處理速度慢、資源消耗大等瓶頸，無法滿足實時壓縮處理需求。Deflate壓縮算法的硬件實現(xiàn)，可以充分減少硬件數(shù)據(jù)通路數(shù)據(jù)量，增大數(shù)據(jù)實際傳輸帶寬，以較小的芯片面積和壓縮率損失為代價獲得較高的壓縮運算速度。因此該技術(shù)被國內(nèi)外研究機構(gòu)關(guān)注，并且無損壓縮已經(jīng)被定義在新的通信標(biāo)準(zhǔn)協(xié)議中[7]。筆者以提高壓縮速率和壓縮率為主要目標(biāo)，兼顧芯片面積和功耗，使用4列雙哈希并行匹配及變長壓縮編碼高速拼接實現(xiàn)壓縮邏輯。最終將其應(yīng)用于基帶數(shù)據(jù)追蹤模塊，實現(xiàn)追蹤數(shù)據(jù)實時壓縮。

1 Deflate無損壓縮技術(shù)

Deflate壓縮算法是結(jié)合LZ77和哈夫曼編碼算法的兩級無損壓縮算法，圖1描述了這種算法的一般實現(xiàn)，數(shù)據(jù)首先經(jīng)過第一級LZ77壓縮，然后對其壓縮結(jié)果再進行第二級哈夫曼編碼壓縮。

1.1 LZ77算法優(yōu)化實現(xiàn)

LZ77[8]是一種通過一個副本反復(fù)替代原文本中重復(fù)出現(xiàn)的數(shù)據(jù)進行壓縮,是一種基于字典查詢的無損壓縮。該算法將當(dāng)前數(shù)據(jù)流與歷史數(shù)據(jù)相匹配，找到一個匹配數(shù)據(jù)，記錄該匹配數(shù)據(jù)的所在位置和匹配長度進行壓縮編碼。如果未匹配成功，則將原數(shù)據(jù)輸出。重復(fù)這個過程，將所有輸入進行編碼。LZ77壓縮最終輸出結(jié)果由三元組：字符、距離、長度構(gòu)成。圖1是壓縮電路結(jié)構(gòu)圖，虛線框內(nèi)為LZ77壓縮邏輯實現(xiàn)。

圖1 壓縮模塊結(jié)構(gòu)圖

為了加速匹配重復(fù)字符，如圖1所示，引入哈希邏輯實現(xiàn)快速索引。輸入字符經(jīng)哈希運算得出哈希地址，利用該哈希地址得到查詢數(shù)據(jù)位置指針。哈希函數(shù)構(gòu)造、鏈表維護及搜索匹配均影響著LZ77算法的效率，哈希表可利用較少位寬數(shù)據(jù)表征較多位寬數(shù)據(jù)，是壓縮關(guān)鍵技術(shù)。因此，哈希邏輯在壓縮模塊實現(xiàn)得到關(guān)注。東南大學(xué)李冰等人提出了雙哈希鏈表[9]，通過使用2種不同的哈希函數(shù)計算字符串前3字節(jié)的哈希值，降低偽匹配，提高匹配成功率。而筆者提出了4列雙哈希并行匹配結(jié)構(gòu)構(gòu)建哈希鏈表如表1所示，輸入數(shù)據(jù)經(jīng)過哈希運算生成表1中第一列哈希地址，利用輸入數(shù)據(jù)高位字節(jié)和另一哈希函數(shù)生成表1中哈希值[i]并記錄對應(yīng)指針[i]。因為哈希值存在多對一的關(guān)系，當(dāng)計算哈希地址沖突時，根據(jù)哈希值[i]進行指針優(yōu)先級選擇，進行LZ77壓縮算法距離計算。

4列雙哈希計算電路如圖2所示，圖中Hi即哈希值[i]，Pi即指針[i]，i=1,2,3,4。設(shè)計哈希邏輯時，同時也要考慮整個壓縮模塊的時序，哈希函數(shù)處理的字節(jié)數(shù)對應(yīng)的最小時間應(yīng)為哈希處理數(shù)據(jù)傳至歷史數(shù)據(jù)比較邏輯的延遲。通過比較哈希表中哈希值可以在4組同樣哈希地址的數(shù)據(jù)中選出最長的匹配數(shù)據(jù)。利用4列并行雙哈希判斷，可在匹配滑窗內(nèi)增加匹配長度，雙哈希計算也可降低偽匹配率；同時得益于硬件電路的4路并行比較，極大提升了壓縮速度。圖1中哈希表深度和歷史數(shù)據(jù)存儲大小影響著壓縮電路的壓縮率。在壓縮電路原型驗證階段，分別測試了哈希表深度和歷史數(shù)據(jù)存儲大小對壓縮率的影響。

表1 壓縮索引哈希表

圖2 4列雙哈希計算電路

1.2 哈夫曼編碼高速移位拼接

哈夫曼編碼是一種基于頻率統(tǒng)計的編碼方式，哈夫曼編碼分為動態(tài)哈夫曼編碼和靜態(tài)哈夫曼編碼。因為資源限制，文中仍采用了帶有前綴碼的靜態(tài)哈夫曼編碼。

LZ77壓縮結(jié)果由字符、距離、長度這三元組構(gòu)成。如果按固定字節(jié)存儲距離、長度，就會浪費存儲空間。按照統(tǒng)計結(jié)果，距離越小的，出現(xiàn)的次數(shù)越多；而距離越大的，出現(xiàn)的次數(shù)越少。因此距離較小的值就應(yīng)該用較少的數(shù)據(jù)位表示，距離較大則使用較多數(shù)據(jù)位表示。因此實時處理的數(shù)據(jù)長度會因當(dāng)前壓縮而長度不同。文中提出的移位拼接根據(jù)輸出數(shù)據(jù)位寬確定輸出寄存器的大小。式(1)即輸出前一級寄存器大小的一般公式描述：

Reg_Length=Max_compress_data_length+Output_length-Min_compress_data_length

(1)

式(1)表示當(dāng)輸出數(shù)據(jù)在當(dāng)前時鐘周期不足端口輸出位寬，則在下一個時鐘周期需要存儲的最大值為當(dāng)前輸出位寬減去壓縮數(shù)據(jù)最小值，加上下一個時鐘周期壓縮數(shù)據(jù)長度最大值。例如文中所計算距離哈夫曼編碼的硬件輸出端口為18位，最短壓縮編碼輸出位寬為9,而壓縮數(shù)據(jù)最長為23位，因此根據(jù)式(1)輸出緩存寄存器位寬為Reg_length=18-9+23=32。

圖3所示為高速移位拼接電路實現(xiàn)，因為壓縮數(shù)據(jù)位寬隨編碼長度變化而變化，當(dāng)拼接數(shù)據(jù)位寬超過輸出數(shù)據(jù)位寬時，需要兩個時鐘周期處理，所以圖3中多路選擇器選擇信號是當(dāng)前選擇信號和延遲一拍選擇信號選擇輸出數(shù)據(jù)。整個移位拼接電路實現(xiàn)分為3部分：(1)第一個時鐘周期，任意位寬數(shù)據(jù)輸入，不需要移位。(2)中間壓縮數(shù)據(jù)要使用圖3所示移位拼接電路，將數(shù)據(jù)移至相應(yīng)的位置與未輸出數(shù)據(jù)進行相或拼接存儲存入寄存器，輸出。(3)最后一個壓縮數(shù)據(jù)不能達到輸出位寬，則以0填充輸出。對于LZ77輸出中長度同樣采用該電路實現(xiàn)拼接輸出。最后將整個數(shù)據(jù)按ZIP包格式輸出。

圖3 高速移位拼接電路

2 壓縮電路測試結(jié)果

壓縮電路分別由前硅功能驗證、FPGA原型[10-11]驗證和后硅性能驗證進行了完備驗證測試。

2.1 標(biāo)準(zhǔn)測試向量

目前被廣泛采用的標(biāo)準(zhǔn)壓縮測試向量分別是Calgary Corpus, Canterbury Corpus和Silesia Corpus[12-14]。該標(biāo)準(zhǔn)測試源由英文文本，程序源代碼，圖像及二進制文件組成，能夠?qū)嚎s實現(xiàn)進行有效評測。文中分別從三組標(biāo)準(zhǔn)測試源選取了與追蹤數(shù)據(jù)屬性接近的測試數(shù)據(jù)進行測試，圖4，圖5橫坐標(biāo)即標(biāo)準(zhǔn)測試源樣本名稱。

圖4 不同匹配長度下壓縮電路壓縮性能測試

2.2 測試結(jié)果

設(shè)計中，固定哈希表(1KB)大小及歷史存儲器深度(2KB)，針對不同最大匹配長度，利用標(biāo)準(zhǔn)數(shù)據(jù)源進行測試評估。測試結(jié)果如圖4(a)，增大最大匹配長度，硬件額外開銷增加，壓縮率提升并不明顯，平均提升不到10%。圖4(b)是使用不同最大匹配長度，硬件的壓縮速度。隨著匹配長度的增加，歷史存儲器訪問次數(shù)增加，數(shù)據(jù)匹配所需時間增長，使得壓縮速率有所下降，最大壓縮速率衰減超過32%。相較于文獻[9]硬件設(shè)計，文中壓縮實現(xiàn)壓縮率有所提升，平均壓縮速度是其6倍。

圖5(a)是固定匹配長度時(256)和歷史數(shù)據(jù)存儲(2KB)大小，哈希表深度分別為128和256，不同測試源對應(yīng)的壓縮。測試結(jié)果表明，哈希表深度的增加，提高3.84%平均壓縮率。圖5(b)是固定匹配長度(256)和哈希表深度(128)，歷史數(shù)據(jù)存儲大小分別是1KB和2KB，不同測試源對應(yīng)的壓縮率，歷史存儲器增大1倍，平均壓縮率提高1.34%。在同等條件下，增加哈希表深度比增加歷史存儲深度能更加有效地提升壓縮率。

圖5 不同存儲尺寸下壓縮電路壓縮率測試

文中設(shè)計硬件實現(xiàn)如下，64位輸入數(shù)據(jù)端口，128位輸出數(shù)據(jù)端口，最大匹配長度256，哈希表深度256，歷史數(shù)據(jù)存儲1 KB，工作時鐘頻率200MHz,采用TSMC 28 nm工藝，面積為0.022 mm2，占芯片總面積不到0.5%。與無損壓縮軟件實現(xiàn)相比，文中所提硬件壓縮模塊壓縮速度有極大提升。以Calgary Corpus為測試源進行壓縮率及壓縮速率測試，與文獻中軟硬件測試結(jié)果進行比較，結(jié)果如表2所示，其中硬件1是文獻[9]硬件設(shè)計。硬件2是文中硬件設(shè)計。硬件2壓縮電路實現(xiàn)其平均壓縮速度達1 031 Mbps，是文獻[9]中PC軟件平臺壓縮速率的50倍，筆記本平臺壓縮速率的57倍，硬件的6倍。與文獻[4]中Silesia測試源測試結(jié)果相比，文中設(shè)計硬件平均壓縮速率是其9倍。

表2 測試源壓縮結(jié)果比較

因為當(dāng)前軟件算法中使用了動態(tài)哈夫曼編碼，所以表2中壓縮算法軟件實現(xiàn)的壓縮率很高，動態(tài)統(tǒng)計地哈夫曼編碼可以較大地提升壓縮效率。對于硬件實現(xiàn)，動態(tài)哈夫曼編碼需要消耗大量存儲空間，并且有效統(tǒng)計概率計算也會降低壓縮速度。故當(dāng)前deflate算法硬件實現(xiàn)在滿足壓縮率指標(biāo)下，實現(xiàn)了實時壓縮，能夠滿足各類實時系統(tǒng)要求。

3 結(jié)束語

筆者基于專用硬件平臺，實現(xiàn)了deflate壓縮算法,使用了4列雙哈希并行匹配，采用靜態(tài)哈夫曼編碼方案，通過硬件流水設(shè)計提高了匹配速度，提升了壓縮速率。測試結(jié)果表明：

(1) 4列雙哈希并行匹配，有效提高了匹配效率和匹配長度，提高了壓縮率。

(2) 使用高速移位拼接設(shè)計，提出了變長數(shù)據(jù)處理的一般方法，提高了壓縮數(shù)據(jù)拼接輸出效率。

(3) 研究影響壓縮率及壓縮速率的參數(shù)：匹配長度，哈希表深度及歷史數(shù)據(jù)存儲大小，針對性能及面積要求，實現(xiàn)壓縮邏輯。

(4) 文中所實現(xiàn)壓縮電路，壓縮平均速率達1 031 Mbit/s，可滿足實時硬件系統(tǒng)壓縮要求，該模塊已應(yīng)用于基帶芯片數(shù)據(jù)追蹤模塊。