第一部分 設(shè)計概述 /Design Introduction

1.1設(shè)計目的

本設(shè)計中，計劃實現(xiàn)對文件的壓縮及解壓，同時優(yōu)化壓縮中所涉及的信號處理和計算密集型功能，實現(xiàn)對其的加速處理。本設(shè)計的最終目標(biāo)是證明在充分并行化的硬件體系結(jié)構(gòu) FPGA 上實現(xiàn)該算法時，可以大大提高該算法的速度。我們將首先使用C語言進行代碼實現(xiàn)，然后在Vivado HLS中綜合實現(xiàn)，并最終在FPGA板（pynq-z2）上進行硬件實現(xiàn)，同時于jupyter notebook中使用python來進行功能驗證。

為使代碼可綜合同時又需要較少的硬件，我們已進行了許多改進，包括以下方面：

將所有浮點變量進行量化處理，量化為Q16.16定點，以簡化算術(shù)運算。與定點相反，浮點型變量需要更多的硬件來執(zhí)行某些操作。

將余弦矩陣實現(xiàn)為8×8查找表，從而消除了對昂貴的CORDIC引擎的需求。

在頂層封裝時選用AXILITE接口，用于將文件從處理器傳輸給FPGA并讀回。這是PS端和PL端進行數(shù)據(jù)傳輸所必須的功能。

在各個功能函數(shù)分別進行流水線化，展開循環(huán)和內(nèi)聯(lián)功能，以最大程度地減少延遲并最大程度地提高吞吐量。

1.2 掌握技能

在本項目中，學(xué)習(xí)到了如下：

學(xué)習(xí)gzip的文件格式，及deflate壓縮算法。能夠使用deflate算法對文件進行壓縮處理，同時將其封裝為gzip型文件。

學(xué)習(xí)了hls和python語言的使用。能夠通過hls進行相關(guān)的IP核開發(fā)，同時能夠使用python語言來對pynq-z2進行調(diào)試。

學(xué)習(xí)了vivado的使用核功能實現(xiàn)。能夠靈活利用HLS和vivado來進行功能開發(fā)。

1.3 應(yīng)用方向

隨著大數(shù)據(jù)時代來臨，大量信息需要通過互聯(lián)網(wǎng)進行傳輸，占用的網(wǎng)絡(luò)資源急劇增加，給網(wǎng)絡(luò)傳輸帶來極大的壓力。數(shù)據(jù)壓縮技術(shù)能夠節(jié)約數(shù)據(jù)存儲空間、傳輸時間和帶寬，從而緩解傳輸壓力。無損壓縮 Gzip 是目前最常用的一種壓縮工具，被廣泛應(yīng)用在網(wǎng)絡(luò)資料的下載和數(shù)據(jù)備份等領(lǐng)域。其中開源代碼 zlib 是 Gzip 算法最著名的實現(xiàn)版本，但因其算法本身計算量較大，導(dǎo)致壓縮的數(shù)據(jù)吞吐率較低。

FPGA 在數(shù)據(jù)處理速度上有著通用處理器無法比擬的巨大優(yōu)勢，能夠大大提升Gzip的處理速度，減小CPU的開銷。

1.4 團隊分工

李佩琦負(fù)責(zé)hls和vivado實現(xiàn)，同時使用python進行功能驗證。

馮一飛負(fù)責(zé)資料查找，同時負(fù)責(zé)協(xié)助李佩琦進行功能實現(xiàn)和功能測試。

1.5 作品展示

整體功能已經(jīng)實現(xiàn)，能夠在pynq z2上通過gzip壓縮方式對txt文件或大段字符串進行壓縮。具體展示如圖1，左側(cè)是在hls仿真是產(chǎn)生的結(jié)果，右側(cè)是通過jupyter notebook在pynq z2上進行調(diào)試的結(jié)果，兩者是一致的，壓縮功能能夠正常運行。圖2是jupyter notebook上部分python代碼。

圖 1

圖2

第二部分 系統(tǒng)組成及功能說明 /System Construction & Function Description

2.1 系統(tǒng)的功能實現(xiàn)

本設(shè)計中，在pynq-z2 FPGA平臺上使用Gzip對文件進行了壓縮算法的加速實現(xiàn)。整體分為兩部分，硬件部分采用靜態(tài)霍夫曼編碼，使用deflate對文件進行壓縮操作。Python模塊將FPGA硬件的deflate輸出進行封裝，將其封裝為gzip格式。

2.2 項目系統(tǒng)框圖

系統(tǒng)結(jié)構(gòu)框圖如圖3所示。

圖3

2.3 gzip的基本組成

Gzip 壓縮是廣泛使用的數(shù)據(jù)壓縮方案，核心是 Deflate算法，主要包括 LZ77 編碼和哈夫曼編碼兩大部分。

2.3.1 gzip文件頭的基本組成

文件頭部分結(jié)構(gòu)如圖4：

圖4

上面兩個“+”之間的內(nèi)容代表一個字節(jié)，所以上面除了MTIME使用四個字節(jié)之外，其他只占用一個字節(jié)。

ID1 和ID2（IDentification） ：這兩個字節(jié)用于標(biāo)識gzip文件，其中，ID1 = 31（0x1f，?37），ID2 = 139（0x8b，213），如果判斷某文件以這兩個字節(jié)開頭，那么可以初步認(rèn)為這是gzip文件，但具體是不是，必須該文件格式完全符合gzip文件格式才行；

CM （CompressionMethod）：該字段用于標(biāo)識當(dāng)前gzip壓縮文件內(nèi)部的壓縮結(jié)果所使用的壓縮方法，取值范圍[0,8]，其中，[0,7]保留，目前只用8，即gzip使用deflate壓縮方法；

FLG （FLaGs）：標(biāo)記位，該標(biāo)記位中的每一比特分別代表后面對應(yīng)擴展位是否存在，各比特位含義不在此處列舉；

MTIME （ModificationTIME）：該字段給出了被壓縮的原始文件最近被修改的時間。該時間使用Unix格式，即，自1970年1月1日0時起到現(xiàn)在的秒數(shù)。

XFL （eXtraFLags）：該字段是用來記錄gzip文件中所使用的壓縮方法，由于當(dāng)前gzip只使用一種壓縮算法，即deflate，所以針對deflate，該字段有如下含義，

XFL= 2 – 壓縮率最大但是壓縮速度最慢（的那個壓縮級別）；

XFL= 4 – 最快的壓縮（級別）；

OS （OperatingSystem）：該字段表示執(zhí)行壓縮操作的文件系統(tǒng)。該字段用于識別和確定確定文本文件的行結(jié)束標(biāo)志。

2.3.2 gzip文件尾和文件體的基本組成

相比gzip文件頭，gzip文件尾較簡單，只由四個字節(jié)構(gòu)成，結(jié)構(gòu)如圖5：

圖 5

CRC32 （Cyclic Redundancy Check）：用標(biāo)準(zhǔn)循環(huán)冗余校驗算法對原始數(shù)據(jù)進行計算的結(jié)果。

ISIZE （InputSIZE）：將原始數(shù)據(jù)大小對2^32取模的結(jié)果。

上面已經(jīng)將整個gzip文件的基本文件格式分析完畢，下面簡單介紹gzip文件的文件體。該文件體主要與壓縮算法deflate相關(guān)。因為只要用到deflate的文件格式，該部分都是一樣的，比如gzip的文件體和PKzip的文件體“基本”是一樣的，因為它們都使用deflate進行壓縮。

2.4 DEFLATE 算法原理

DEFLATE 算法標(biāo)準(zhǔn)是由兩個壓縮算法聯(lián)合構(gòu)成的，壓縮流程如6圖所示，其中主要包含 LZ77 和哈夫曼編碼。首先利用 LZ77 算法進行字典查找替代，消除重復(fù)信息，然后進行哈夫曼編碼構(gòu)造平均長度最短的壓縮碼流。

圖6

2.5 LZ77 算法

LZ77 算法是一種基于字典模型的壓縮算法。DEFLATE 算法中用到的 LZ77 算法是在原始 LZ77 算法的基礎(chǔ)上略加改進得到的，但算法基本思想保持不變。其基本原理為：將先輸入的數(shù)據(jù)作為字典信息進行保存，利用數(shù)據(jù)中存在字符串重復(fù)帶來的數(shù)據(jù)冗余性，根據(jù)字典中存儲的歷史數(shù)據(jù)對后續(xù)數(shù)據(jù)進行替換達到壓縮的目的。

具體在 Gzip 壓縮的參考軟件代碼 zlib 中實現(xiàn) LZ77 算法的流程為：首先讀入緩存窗口大小 CHUNK 的數(shù)據(jù)，其中窗口的大小與匹配最大距離 MAX_MATCH 有關(guān)；依次計算輸入字符串的哈希值，將哈希值的作為字典地址的索引值，將字符串的位置信息依次存放在由哈希鏈表組成的字典中其哈希值對應(yīng)的位置上；然后對當(dāng)前的字符串根據(jù)索引值查找可能匹配的歷史字符串并進行最長匹配查找，判斷是否滿足匹配條件，若滿足則進行匹配對的替換；若不滿足則按照原始字符串輸出。對于 LZ77 壓縮算法的實現(xiàn)關(guān)鍵點在于歷史字符串的存儲、當(dāng)前字符串的匹配查找、以及最長匹配選擇。

2.6 Huffman 編碼

哈夫曼編碼（ Huffman coding ）在數(shù)據(jù)壓縮的分類中提到，是一種基于統(tǒng)計模型的壓縮算法。其編碼理論依據(jù)是統(tǒng)計符號出現(xiàn)的概率，對符號按照概率從小到大進行排序，將其中出現(xiàn)概率最小的符號分配最長的編碼長度，按照這樣的規(guī)則進行變長編碼，達到平均編碼長度最小。具體編碼過程為：首先統(tǒng)計不同符號出現(xiàn)的概率，然后根據(jù)概率構(gòu)建哈夫曼樹，最后根據(jù)哈夫曼樹得到每個符號的哈夫曼編碼。具體步驟如下：

步驟 1：統(tǒng)計 n 個不同信源符號出現(xiàn)的概率；

步驟 2：將概率按照從大到小的順序進行排列，并將其作為節(jié)點數(shù)為 1的子樹；

圖7

步驟 3：選出概率最小的兩個信源符號所在的子樹構(gòu)成新的子樹，并且新合成的子樹概率為這兩個信源符號的概率相加；

步驟 4：重復(fù)步驟 3，直到所有信源符號的所在子樹均被加入到同一樹中；

步驟 5. 對構(gòu)建的樹所有父節(jié)點的左結(jié)點標(biāo)記為 0，右結(jié)點標(biāo)記為 1；

步驟 6. 統(tǒng)計根節(jié)點到每個子節(jié)點的路徑，按照步驟 5 中 0-1 標(biāo)記的路徑就是對應(yīng)葉節(jié)點信源的哈夫曼編碼。

圖8

另外，在 Gzip 壓縮中，哈夫曼編碼的實現(xiàn)有兩種：分別為靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼。其中靜態(tài)哈夫曼編碼不需要對編碼的字符做頻率統(tǒng)計，而是直接根據(jù)預(yù)先定義的編碼規(guī)范表查找進行編碼；似的，在解碼的過程中也不需要統(tǒng)計頻率而直接使用與編碼一致的編碼規(guī)范表進行解碼。對于動態(tài)哈夫曼編碼則遵循哈夫曼編碼的原理，需要對出現(xiàn)的字符進行頻率統(tǒng)計，生成哈夫曼樹，再據(jù)此生成編碼表進行編碼。

在本設(shè)計中，我們采用靜態(tài)哈夫曼編碼來進行實現(xiàn)。

第三部分 完成情況及性能參數(shù) /Final Design & Performance Parameters

整體功能已經(jīng)實現(xiàn)。并具備一定的加速效果，相比純arm進行壓縮速度提高了1.6倍。Vivado硬件工程能夠通過綜合、應(yīng)用、生成比特流。最后通過Jupyter Notebook在pynq z2平臺上進行功能驗證。具體展示如圖9，左側(cè)是在hls仿真是產(chǎn)生的結(jié)果，右側(cè)是通過jupyter notebook在pynq z2上進行調(diào)試的結(jié)果，兩者是一致的，壓縮功能能夠正常運行。

圖9

圖10，圖11中，hls正常進行仿真，首先通過壓縮算法對txt文件或字符串進行壓縮，接著進行解壓操作，將解壓后的代碼與源代碼進行比較，如果結(jié)果一致，則能夠驗證壓縮算法本身功能的準(zhǔn)確性。

圖10

圖11

在圖12，圖13中，我們展示了部分壓縮算法代碼及優(yōu)化指令，整體設(shè)計的源代碼為github上的開源代碼，在優(yōu)化后我們外部的接口采用hls::stream的形式，內(nèi)部使用到了pipeline，unroll等。

圖12

圖 13

在圖14,15中我們展示資源占比情況和時序分析，進行優(yōu)化后實現(xiàn)了部分流水。

圖14

圖15

圖16中，vivado電路設(shè)計圖中hls生成的gzip ip核通過dma與ps端進行數(shù)據(jù)交互。

圖16

圖17中，我們展示notebook部分調(diào)試代碼，為了方便查看對部分輸出結(jié)果進行輸出，與HLS仿真結(jié)果進行對比發(fā)現(xiàn)結(jié)果正確，達到了最初的設(shè)計要求。

圖17

完