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

1.1設(shè)計(jì)目的

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

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

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

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

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

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

1.2 掌握技能

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

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

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

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

1.3 應(yīng)用方向

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

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

1.4 團(tuán)隊(duì)分工

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

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

1.5 作品展示

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

圖 1

圖2

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

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

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

2.2 項(xiàng)目系統(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

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

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

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

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

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

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

XFL= 2 – 壓縮率最大但是壓縮速度最慢（的那個(gè)壓縮級(jí)別）；

XFL= 4 – 最快的壓縮（級(jí)別）；

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

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

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

圖 5

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

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

上面已經(jīng)將整個(gè)gzip文件的基本文件格式分析完畢，下面簡(jiǎn)單介紹gzip文件的文件體。該文件體主要與壓縮算法deflate相關(guān)。因?yàn)橹灰玫絛eflate的文件格式，該部分都是一樣的，比如gzip的文件體和PKzip的文件體“基本”是一樣的，因?yàn)樗鼈兌际褂胐eflate進(jìn)行壓縮。

2.4 DEFLATE 算法原理

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

圖6

2.5 LZ77 算法

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

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

2.6 Huffman 編碼

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

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

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

圖7

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

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

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

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

圖8

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

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

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

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

圖9

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

圖10

圖11

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

圖12

圖 13

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

圖14

圖15

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

圖16

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

圖17

完