無損數(shù)據(jù)壓縮算法的FPGA實現(xiàn)本科畢業(yè)論

1、精品文檔 編號 南京航空航天大學畢業(yè)設計題 目無損數(shù)據(jù)壓縮算法的FPGA實現(xiàn)學生姓名梅發(fā)強學 號041220318學 院電子信息工程學院專 業(yè)信息工程班 級0412206指導教師劉偉強 副教授二一六年五月歡迎下載精品文檔南京航空航天大學本科畢業(yè)設計論文誠信承諾書本人鄭重聲明：所呈交的畢業(yè)設計論文題目：無損數(shù)據(jù)壓縮算法的FPGA實現(xiàn)是本人在導師的指導下獨立進行研究所取得的成果。盡本人所知，除了畢業(yè)設計論文中特別加以標注引用的內(nèi)容外，本畢業(yè)設計論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。作者簽名： 年 月 日 學號：歡迎下載精品文檔無損數(shù)據(jù)壓縮算法的FPGA實現(xiàn)摘 要隨著信息技術的快速開

2、展，數(shù)據(jù)量呈現(xiàn)爆炸性增長，因此數(shù)據(jù)壓縮越來越受到人們的重視。目前，無損壓縮算法大多數(shù)都是基于軟件方式的實現(xiàn)，但是這在很多場合下已經(jīng)不能滿足高速數(shù)字系統(tǒng)的要求，所以基于硬件方式的實現(xiàn)成為了新的研究熱點。目前已有LZ77、LZ78及LZW等算法的硬件實現(xiàn)，但是都存在搜索窗口較小，壓縮率較低，速度較慢等缺陷。本文出于硬件實現(xiàn)的考慮，對LZ4算法進行了適當?shù)男薷?，基于FPGA進行實現(xiàn)，經(jīng)實測發(fā)現(xiàn)其壓縮率和速度都得到了顯著提升。關鍵詞：無損壓縮， LZ4， Verilog， FPGA FPGA Implementation of Lossless Data CompressionAbstractWith

3、 the rapid development of information technology, the amount of data presents explosive growth. Therefore, more and more attention has been paid to the data compression. Up to date, most of lossless compression algorithms are realized in software. However, software implementation in many occasions c

4、annot meet the real time requirements of high-speed system. The hardware implementation of data compression algorithms is becoming a research hotspot. Nowadays, there are hardware implementations of the lossless data compression algorithms such as LZ77, LZ78, LZW etc. But they have defects including

5、 small search window, low compression rate, and slow processing speed. In this thesis, for the consideration of the hardware implementation, the LZ4 algorithm is appropriately modified to be implemented on Xilinx FPGA KC 705 evaluation board, which offers higher compression rate and speed.Key Words：

6、Lossless compression; LZ4; Verilog; FPGA目 錄摘 要iAbstractii第一章 引 言11.1 課題研究背景及意義11.2 本文研究內(nèi)容和結(jié)構(gòu)安排2第二章 根本原理和常用算法32.1 數(shù)據(jù)信息量、熵和冗余度介紹32.2 LZ系列算法概述32.3 LZ4算法簡介4第三章 LZ4無損壓縮算法原理53.1 數(shù)據(jù)流格式53.2 官方LZ4格式53.3 修改后的LZ4格式73.4 算法流程73.4.1 hash表73.4.2 匹配算法83.4.3 流操作83.5 解壓93.5.1 官方LZ4格式解壓流程93.5.2 修改后的LZ4格式解壓流程9第四章 LZ4無損

7、壓縮算法硬件實現(xiàn)方案114.1 方案一114.1.1 硬件框圖114.1.2 算法流程124.1.3 硬件調(diào)試時序圖134.1.4 壓縮速度計算144.2 方案二144.2.1 硬件框圖144.2.2 算法流程144.2.3 硬件調(diào)試時序圖164.2.4 壓縮速度計算164.3 方案三164.3.1 硬件框圖164.3.2 算法流程174.3.3 硬件調(diào)試時序圖184.3.4 壓縮速度計算184.4 各方案優(yōu)缺點分析194.4.1 資源消耗比擬194.4.2 壓縮速度比擬194.4.3 最正確方案選擇19第五章 LZ4無損壓縮算法硬件實現(xiàn)215.1 LZ4核總體框架215.2 LZ4壓縮驗證結(jié)

8、構(gòu)圖225.3 LZ4核內(nèi)部模塊功能說明225.4 LZ4核性能27第六章 LZ4無損壓縮算法硬件實現(xiàn)功能測試296.1 測試框架圖296.2 數(shù)據(jù)測試表格296.3 與已有的LZ系列的實現(xiàn)比照30第七章 LZ4解壓縮算法硬件實現(xiàn)317.1 LZ4解壓核總體框架317.2 LZ4解壓驗證結(jié)構(gòu)圖317.3 LZ4解壓核內(nèi)部模塊功能說明32輸入模擬FIFO32數(shù)據(jù)解壓控制模塊33輸出控制模塊34輸出RAM模塊347.4 LZ4解壓核輸出速度計算34第八章 總結(jié)36參 考 文 獻37致 謝38 歡迎下載精品文檔第一章 引 言1.1 課題研究背景及意義隨著信息時代的到來，人們對數(shù)據(jù)越來越依賴，數(shù)據(jù)交換

9、量日益增大，海量數(shù)據(jù)帶來的大規(guī)模數(shù)據(jù)處理也變得更加復雜。將數(shù)據(jù)進行有效的壓縮能夠減少存儲所需的空間以及最大限度地利用有限的通信帶寬。而且，經(jīng)過壓縮的數(shù)據(jù)在一定程度上是對原始數(shù)據(jù)的加密，從而更加地提高數(shù)據(jù)的平安性1。數(shù)據(jù)壓縮通常分為無損壓縮和有損壓縮。圖像、視頻、音頻等不是十分注重細節(jié)的數(shù)據(jù)大多數(shù)都采用有損壓縮技術，用于此類應用場景的有MPEG，H.263，H.264等當今流行的壓縮技術23。但是像程序、電子檔案等類似的需要完全可以復原的重要信息，就必須采用無損壓縮技術，用于這種要求解壓縮后的數(shù)據(jù)與原始數(shù)據(jù)完全一致的場合的常見算法有LZ77、LZSS、GZIP、BZIP2、RAR等。人們對無損壓

10、縮技術的研究已經(jīng)有很長的一段時間，其中LZ系列的壓縮算法和最小冗余度構(gòu)造算法Huffman算法屬于最重要的無損壓縮技術?，F(xiàn)在流行的壓縮技術根本上都是由這些算法衍生而來45。但是，當今很多壓縮解壓方案都是基于軟件方式的實現(xiàn)。采用軟件方式的壓縮解壓存在一個致命的弱點，那就是過多地消耗珍貴的CPU資源而且速度慢。特別是當壓縮解壓大量數(shù)據(jù)時，占有的CPU資源是非常大的，而且由于CPU采用的指令工作方式使得速度很慢，另外系統(tǒng)非常不穩(wěn)定，很難滿足一些特殊環(huán)境下的應用要求。所以，如何有效提高壓縮算法的效率，減少龐大數(shù)據(jù)量壓縮解壓給CPU和內(nèi)存帶來的壓力成為了現(xiàn)在壓縮解壓技術的主要開展方向?，F(xiàn)代VLSI技術的

11、開展使得采用硬件方式來實現(xiàn)壓縮解壓成為可能。用專用硬件提供壓縮解壓可以解決上述軟件壓縮解壓所存在的缺點。即它可以：l、提高了壓縮解壓的速度，有利于實時性處理；2、節(jié)省了珍貴的CPU資源。因為硬件方式相比軟件方式實現(xiàn)的速度快很多，依靠電路實現(xiàn)不需要循環(huán)的指令計算，而且能夠采取并行的實現(xiàn)方式，這樣降低了資源和能源的消耗。如今已經(jīng)有不少采用硬件方式的壓縮解壓方案在信息產(chǎn)業(yè)的各個環(huán)節(jié)被應用，具有長遠的開展前景67。1.2 本文研究內(nèi)容和結(jié)構(gòu)安排本文主要研究LZ4算法流程、硬件實現(xiàn)、以及算法優(yōu)化。通過對現(xiàn)有的LZ4文獻以及官方的C程序，了解并掌握LZ4算法的壓縮和解壓原理。在對LZ4算法足夠了解后，將算

12、法細分成幾個步驟得出算法流程圖。通過算法流程圖，將整個算法細分成許多子模塊，每個子模塊實現(xiàn)一個簡單的功能，通過流程控制將每個模塊關聯(lián)起來，最后實現(xiàn)每個子模塊都處于同時工作狀態(tài)，提高壓縮速度，實現(xiàn)并行處理功能。本文章節(jié)內(nèi)容安排如下：第一章主要介紹LZ4算法的FPGA高速實現(xiàn)的研究背景，介紹了數(shù)據(jù)壓縮的歷史與現(xiàn)狀，并明確了本文的研究內(nèi)容；第二章分析了數(shù)據(jù)壓縮原理，說明了什么樣的數(shù)據(jù)才能壓縮，并對LZ系列算法做了一個大概的介紹。第三章對LZ4無損壓縮算法原理進行了詳細的介紹，包括LZ4數(shù)據(jù)格式以及LZ4算法流程。第四章提供了三個LZ4無損壓縮算法的硬件實現(xiàn)方案，并詳細介紹了每個方案的實現(xiàn)流程以及每個

13、方案的優(yōu)缺點，同時對其性能做出了詳細的比擬。第五章介紹了LZ4無損壓縮算法硬件實現(xiàn)程序的結(jié)構(gòu)以及每個模塊的功能，同時給出了在kintex7 kc705開發(fā)板上運行的到的一些資源消耗信息。第六章是對LZ4無損壓縮算法的硬件實現(xiàn)做的一些數(shù)據(jù)測試，計算了其壓縮率，并將它的壓縮速度與市場上的一些產(chǎn)品做比擬。第七章是根據(jù)壓縮算法而做的解壓算法的FPGA實現(xiàn)，其中詳細介紹了解壓流程以及解壓程序中每個模塊的功能。第八章是對整個論文的總結(jié)。第二章 根本原理和常用算法數(shù)據(jù)壓縮的前提是數(shù)據(jù)可以被壓縮。從信息論中可以知道什么樣的數(shù)據(jù)壓縮后會變小，什么樣的數(shù)據(jù)壓縮后占據(jù)空間反而會變大。根據(jù)數(shù)據(jù)的信息量、熵和冗余度可以

14、計算出壓縮后的最小體積，但是由于算法原理、數(shù)據(jù)格式不同會導致始終達不到理論值。不過可以通過理論來知道為何數(shù)據(jù)可以被壓縮，也可以通過這些理論來指導數(shù)據(jù)壓縮的實現(xiàn)。2.1 數(shù)據(jù)信息量、熵和冗余度介紹信息量是指一個隨機事件的不確定性，通常用熵來表示。信息論量度信息的根本出發(fā)點，是把獲得的信息看作用以消除不確定性的東西，因此信息數(shù)量的大小，可以用被消除的不確定性的多少來表示。一個消息的可能性越小，其信息就越多；消息的可能性越大，其信息就越少。信息論中把一個事件如字符所攜帶的信息量定義為8：2.1其中PXi為實踐發(fā)生字符Xi的概率。將信息所有可能事件的信息量進行平均，就得到信息的熵。信源X的信息熵(En

15、tropy) H(x)定義為8：2.2信源經(jīng)常由于事件相關或概率分布不均勻等原因，而使實際的熵小于其最大熵，這樣就產(chǎn)生了信息的冗余。冗余度R定義為：2.32.2 LZ系列算法概述LZ系列算法起源于兩位以色列研究者J.Ziv和A.Lempel在1977年發(fā)布的LZ77數(shù)據(jù)壓縮的通用算法，該算法與Huffman及算術編碼更加有效，通過不斷的開展演變最后提出了很多改良算法，比方1978年由二人提出的改良算法LZ78以及1984年T.A.Welch提出的LZW算法等。這些衍生改良的算法統(tǒng)稱為LZ系列算法。LZ77、LZSS、LZ78、LZW算法都是通過創(chuàng)立字典進行壓縮的算法，LZ77和LZSS里的詞典

16、是指當前數(shù)據(jù)是否在以前出現(xiàn)過的數(shù)據(jù)中出現(xiàn)過，出現(xiàn)過就用出現(xiàn)過的字符的位置代替當前數(shù)據(jù)，而不同的是LZ78以及LZW是將出現(xiàn)過的數(shù)據(jù)進行編碼，如果當前數(shù)據(jù)在以前出現(xiàn)過，那么用編碼代替當前數(shù)據(jù)。LZ4算法也是由LZ77算法衍生而來，不同的是LZ4算法更加注重與壓縮和解壓的速度，用最少的步驟實現(xiàn)匹配查找與編碼，從而提高壓縮速度。2.3 LZ4算法簡介LZ4算法也屬于LZ系列算法，其主要概念與LZ77算法一致。LZ4與LZ77算法一樣，擁有一個滑動窗口以及一個預讀緩存區(qū)域。LZ4的預讀緩存區(qū)域為4個字節(jié)，而滑動窗口的大小可以根據(jù)實際需要進行修改。預讀緩存區(qū)是用來保存當前輸入數(shù)據(jù)的前4個字節(jié)，將這4個字

17、節(jié)進行hash計算后，判斷當前字節(jié)是否在滑動窗口中出現(xiàn)過，假設在滑動窗口中出現(xiàn)過那么可以進行匹配，繼續(xù)往后查找匹配，查找結(jié)束后將當前字節(jié)與之前出現(xiàn)過的字節(jié)處的距離表示當前這一段數(shù)據(jù)，然后通過相應的格式組合成一個序列。而整個LZ4壓縮后的文件就是有許多個類似的序列組合而成。第三章 LZ4無損壓縮算法原理LZ4無損數(shù)據(jù)壓縮是當今最快的壓縮算法，當然不是指只要用LZ4壓縮算法就會比其他算法實現(xiàn)更快，而是指這個算法的流程更少，使用更少的步驟來完成整個流程，這樣壓縮算法的速度在相同條件下自然就比其他算法更加快速。以下介紹了整個LZ4無損壓縮算法的原理，包括壓縮后的數(shù)據(jù)格式。為了實現(xiàn)流輸入，在后面介紹了修

18、改后的LZ4無損壓縮算法原理以及壓縮后的數(shù)據(jù)格式。3.1 數(shù)據(jù)流格式下列圖給出了LZ4壓縮后的數(shù)據(jù)流格式10，其中前面4Byte是表示這個文件是什么格式，通常是一個特定的數(shù)字來代表其是LZ4壓縮文件，后面的3-15Byte用來表示整個數(shù)據(jù)流的大小。中間的Block就是一個個數(shù)據(jù)塊了，這是壓縮文件的主體。其后的4個字節(jié)都是0，用來表示數(shù)據(jù)結(jié)束。Stream checksum那么是一個校驗碼，也可以去掉。 圖3.1 數(shù)據(jù)流格式簡圖3.2 官方LZ4格式LZ4的格式如下911：1數(shù)據(jù)格式每一個輸入的數(shù)據(jù)塊可以壓縮成假設干個序列，每個序列都包含有令牌token、字符串literals、字符串長度lit

19、eral length、偏移量offset以及匹配長度match length。每個序列格式如圖3.29所示： 圖3.2 數(shù)據(jù)格式2token高4位代表不可匹配字符長度，當不可匹配字符長度大于等于15時高4位為15；當不可匹配字符長度小于15時，高4位就等于不可匹配字符長度。低4位代表匹配字符長度，當匹配字符長度大于等于19時低4位為15；當匹配字符長度小于19時，低4位等于匹配字符長度減去4。3literal length如果token高4位為小于15，那么該值為0，且不會輸出到壓縮文件里，表示未壓縮數(shù)據(jù)長度等于token高4位的值；如果token高4位等于15，表示不可壓縮數(shù)據(jù)大于等于15

20、，此時該值等于未壓縮數(shù)據(jù)長度減去15后的大小。假設token高4位等于15，那么需要在該序列后添加一個字節(jié)來表示完整的長度值。每一個添加的字節(jié)取值范圍為0到255。這樣，兩個位置的值組合共同表示完整的長度。假設附加的一字節(jié)數(shù)據(jù)還是不能表示完整的長度，那么繼續(xù)在后面添加一個字節(jié)，以此類推。4literals該序列為未壓縮的數(shù)據(jù)，由原數(shù)據(jù)復制得到，該數(shù)據(jù)跟在token和literal length后面。5offset當輸入的數(shù)據(jù)經(jīng)查找發(fā)現(xiàn)之前出現(xiàn)過相同的數(shù)據(jù)時，此處的數(shù)據(jù)將會被壓縮，而offset的值表示這兩處相同數(shù)據(jù)之間的偏移量。該序列有一個規(guī)那么，即0是一個無效值，不能使用，1代表“當前位置減

21、一個字節(jié)。offset用小頭結(jié)構(gòu)表示，最大值為65525。6match length表示匹配數(shù)據(jù)的長度。匹配數(shù)據(jù)的最小值為4，因此，假設token后4位的值為0，那么意味著實際匹配的數(shù)據(jù)為4個字節(jié)，假設token后4位的值為15，那么意味著實際匹配的數(shù)據(jù)為19字節(jié)。匹配長度假設超出15，采取的措施和literal length里面采取的方法一致。7最后一個序列規(guī)那么1壓縮序列的最后5個字節(jié)必須是literals。2不能匹配最后12個字節(jié)的數(shù)據(jù)。因此一個文件的最后一個序列至少有12個字節(jié)數(shù)據(jù)應被壓縮為literals。3最后一個序列匹配長度為0，offset為0。3.3 修改后的LZ4格式1數(shù)據(jù)

22、格式由于在硬件實現(xiàn)的時候，由于是高速流操作，輸入數(shù)據(jù)需要在幾個時鐘內(nèi)判斷是否匹配，判斷結(jié)束后不可匹配數(shù)據(jù)需要立即輸出到緩存中。假設按照原來的格式，那么必須先計算出不可匹配字符長度，然后再將不可匹配字符輸出，這樣數(shù)據(jù)輸出的時間開銷將變大，因此會減小壓縮速度。所以通過改變數(shù)據(jù)格式來提高壓縮速度。修改后的數(shù)據(jù)格式如下：說明：token、offset的格式與標準格式一致。 圖3.3 修改后的LZ4數(shù)據(jù)格式2length of literals當token高4位小于15時，literal length為0字節(jié)。當token高4為為15時，literal length為2個字節(jié)，位于不可匹配字符中第16、

23、17個字節(jié)，字符長度大小為literal length中以前一個字節(jié)為高8位和后一個字節(jié)為低8位組合成的一個16位的數(shù)據(jù)。3match length當token低4位小于15時，match length為0字節(jié)，實際匹配長度為token后四位加4。當token低4為15時，match length為2個字節(jié)，位于offset后兩個字節(jié)，實際匹配長度大小為match length中以前一個字節(jié)為高8位和后一個字節(jié)為低8位組合成的一個16位的數(shù)據(jù)、token后四位和4相加的結(jié)果。3.4 算法流程3.4.1 hash表LZ4通過計算哈希值建立哈希表來查找匹配字符串。這個哈希表的映射關系為(key,

24、value)：key是4個字節(jié)的二進制數(shù)。value為這4個字節(jié)在數(shù)據(jù)塊中的位置。選擇哈希表的大小時要根據(jù)實際要求作出選擇：1如果側(cè)重壓縮比，那么可以將哈希表設置大一些。2如果更看重壓縮速度，那么哈希表應該適中，以便于能裝入L1 cache。哈希表使用的內(nèi)存默認值為16KB，能裝進L1 cache，這也是LZ4壓縮速度快的一個原因。當前主流的Intel X86 L1 Data Cache為32KB，所以哈希表的大小最好不要超過32KB。Hash值計算采用整數(shù)哈希算法。2654435761U是2到232的黃金分割素數(shù)，2654435761 / 4294967296 = 0.618033987。計

25、算哈希值時，輸入為4個字節(jié)的二進制數(shù)，輸出可以分為2字節(jié)值、4字節(jié)值兩種哈希值。3.4.2 匹配算法匹配算法執(zhí)行步驟：1令當前的地址為ip，它的哈希值為h。2令下個地址為forwardIp，它的哈希值為forwardH (下個循環(huán)賦值給ip、h)。3按照哈希值h，獲取哈希表中的值ref。3.1ref為初始值，沒有匹配，繼續(xù)往下查找。3.2ref不為初始值，有匹配。3.2.1如果ref不在滑動窗口內(nèi)，放棄當前值，繼續(xù)向下查找。3.2.2如果ref對應的4個字節(jié)和ip對應的4個字節(jié)不一樣，是沖突，繼續(xù)向下查找匹配。3.3.3如果ref在滑動窗口內(nèi)，且對應的4個字節(jié)一樣，說明找到了match，退出匹

26、配查找。4） 保存ip和h的對應關系。3.4.3 流操作流操作循環(huán)步驟：1讀取4字節(jié)，根據(jù)hash算法計算hash值。2讀取hash表的地址，寫入當前地址，調(diào)用匹配算法查詢是否匹配。3假設查找到了匹配那么向后繼續(xù)查找計算匹配長度，否那么返回第一步讀取后4個字節(jié)繼續(xù)查找。4假設匹配且后向匹配完成，接著將計算好了的數(shù)據(jù)寫入輸出緩存中5當前序列輸出完成后，返回第一步讀取后4字節(jié)查找下一個匹配。如果地址移動到了最后5個字節(jié)，那么采取相應的算法規(guī)那么，最后5個字節(jié)單獨作為一個序列不進行匹配。3.5 解壓3.5.1 官方LZ4格式解壓流程以下為官方LZ4格式解壓流程11：1讀取magic number判斷

27、文件格式，假設是LZ4格式的進入解壓程序，否那么退出。2讀取stream describe判斷文件大小，確定末尾地址3讀取第一個序列的token，即stream describe后一個字節(jié)。假設token高4位為15，那么繼續(xù)向后讀取后一個字節(jié)，假設該字節(jié)為255，那么繼續(xù)往下直到讀取到第一個小于255的字節(jié)為止，不可匹配字符長度就是這些所有字節(jié)的值求和再加上15。假設token高4位小于15，說明不可匹配字符長度就等于token高4位的值。4確定不可匹配字符長度后，將不可匹配字符復制到輸出緩存中。5根據(jù)不可匹配字符長度計算出offset的位置，讀取offset的倆個字節(jié)，將其拼接成一個16位

28、的數(shù)據(jù)，根據(jù)offset確定匹配的位置。6假設token低4位為15，那么從offset的兩個字節(jié)后讀取一個字節(jié)，假設該字節(jié)為255那么繼續(xù)讀取下一個，直到不為255為止，這時匹配字符長度就等于這些字節(jié)求和后再加上19。假設token低4位小于15，說明可匹配字符長度等于token低4位的值再加上4。7確定匹配字符長度后，從匹配的位置處開始向后拷貝字符，拷貝字符的長度和匹配字符的長度一致。8待拷貝完成后，讀取下一個token，按照上述規(guī)那么繼續(xù)往下解壓直到解壓到末尾地址結(jié)束。3.5.2 修改后的LZ4格式解壓流程以下為修改后的LZ4格式解壓流程1讀取magic number判斷文件格式，假設是

29、LZ4格式的進入解壓程序，否那么退出。2讀取stream describe判斷文件大小，確定末尾地址3讀取第一個序列的token，即stream describe后一個字節(jié)。假設token高4位為15，那么從token開始向后數(shù)15個字節(jié)，第16、17個字節(jié)便是literal length。將第16、17個字節(jié)合并成一個16位的數(shù)據(jù)literal length，不可匹配字符長度就等于literal length加上15。假設token高4位小于15，說明不可匹配字符長度就等于token高4位的值。4確定不可匹配字符長度后，將不可匹配字符復制到輸出緩存中。5根據(jù)不可匹配字符長度計算出offset

30、的位置，讀取offset的倆個字節(jié)，將其拼接成一個16位的數(shù)據(jù)，根據(jù)offset確定匹配的位置。6假設token低4位為15，那么從offset的兩個字節(jié)后讀取兩個字節(jié)，將這兩個字節(jié)合并成一個16位的數(shù)據(jù)match length，不可匹配字符長度就等于match length加上19。假設token低4位小于15，說明可匹配字符長度等于token低4位的值再加上4。7確定匹配字符長度后，從匹配的位置處開始向后拷貝字符，拷貝字符的長度和匹配字符的長度一致。8待拷貝完成后，讀取下一個token，按照上述規(guī)那么繼續(xù)往下解壓直到解壓到末尾地址結(jié)束。第四章 LZ4無損壓縮算法硬件實現(xiàn)方案本章節(jié)提出了三個

31、不同的硬件實現(xiàn)方案，每個方案都有各自的側(cè)重點，方案一簡單，方案二提高速度的同時減少RAM資源消耗，方案三壓縮速度快。每一個方案都通過仿真驗證，其性能也通過仿真測試過，以下就是方案的具體描述。4.1 方案一4.1.1 硬件框圖與官方無損壓縮算法不同的是添加了一個32位64K地址的RAM塊，用這個RAM塊來存儲與hash值對應的32位字節(jié)，在進行匹配判斷的時候不需要再返回在輸入緩存中讀取hash表中的地址對應的32位數(shù)據(jù)，可以直接從該RAM塊讀出后判斷比擬。這樣做的好處在于省去了沖突帶來的額外時間開銷，同時可以減少查找匹配的步驟提高壓縮速度。方案一的硬件模塊分為輸入緩存、ip控制、移位存放器等9個

32、模塊，通過ip控制將輸入緩存中的數(shù)據(jù)讀出傳送給移位存放器，而移位存放器將數(shù)據(jù)變成32位數(shù)據(jù)傳輸給核心控制模塊進行hash計算、匹配查找的操作，直到查找到匹配后，讀出匹配處的地址，根據(jù)地址讀出緩存中該地址后的數(shù)據(jù)，然后繼續(xù)后向匹配查找。在查找的同時將不可匹配字符傳輸給輸出控制，通過字符長度模塊計算不可匹配字符長度然后傳給輸出控制。在查找到匹配之后，通過匹配長度模塊計算匹配長度，將匹配長度傳給輸出模塊。輸出模塊根據(jù)接收到的數(shù)據(jù)組合后輸出到輸出緩存中完成壓縮操作。以下為方案一的硬件框圖： 圖4.1 方案一硬件框圖下面將具體介紹方案一的算法流程。4.1.2 算法流程1方案一核心算法流程如下：1啟動壓縮

33、時，通過ip控制，每個時鐘ip加一，同時控制移位存放器移位，當ip等于4時停止，同時停下移位存放器移位。2一個時鐘后hash計算得出hash值。同時hash表以及4字節(jié)存儲空間寫輸入使能。3再過一個時鐘，讀出hash表中的地址Ref以及4字節(jié)存儲空間中的4個字節(jié)U32Ref。同時寫入當前的ip值以及移位存放器輸出的32位數(shù)據(jù)U32ip。假設Ref小于當前ip值且不為0，同時U32Ref等于U32ip那么說明當前4個字節(jié)與地址在Ref處的4個字節(jié)相同，啟動匹配程序進入步驟5，否那么進入步驟4。4hash表以及4字節(jié)存儲空間允許輸入，發(fā)脈沖信號給ip控制，使ip加1,同時控制移位存放器移動一位，假

34、設ip未移動到倒數(shù)第5個字節(jié)時回到步驟2。假設ip移動到倒數(shù)第5個字節(jié)時跳到步驟8。5通過Ref控制讀出位于Ref處匹配4字節(jié)后的相應字節(jié)。6判斷dRef與dip是否相等，假設相等，控制Ref與ip加1后回到步驟5；否那么進入步驟7。假設ip移動到倒數(shù)第5個字節(jié)時不管dRef與dip是否相等都跳到步驟8。7一個序列查找完成，增加ip，控制移位存放器，使移位存放器中不再有前面的匹配字符，然后回到步驟2，開始查找下一個序列。8剩余數(shù)據(jù)生成一個單獨的序列，offset為0，匹配長度為0。2token、offset、match length以及l(fā)iteral length計算流程:l token：核心

35、控制處于步驟7且步驟7剛結(jié)束時，假設不可匹配字符小于15，那么用token高4位表示不可匹配字符大小，否那么token高4位為15；假設可匹配字符小于19，那么用token低4位等于可匹配字符大小減4，否那么token高4位為15。l Offset：核心控制處于步驟5時，offset等于ip減去Ref。l literal length：核心控制處于步驟2到步驟4時，通過對控制ip模塊的脈沖計數(shù)，獲得不可匹配字符的大小，假設其小于15那么literal length為0，且不輸出。假設不可匹配字符的大小大于15時，literal length等于不可匹配字符的大小減去15。l match len

36、gth：核心控制處于步驟5到步驟7時，通過對控制ip模塊的脈沖計數(shù)，獲得可匹配字符的大小，假設其小于19那么match length為0，且不輸出。3輸出控制算法流程1復位后等待第一個序列完成。2第一個序列完成后，依次寫入token、literal length、literal、offset、match length。3等待，當前序列完成后返回第2步直到結(jié)束。4.1.3 硬件調(diào)試時序圖如圖4.2所示，該圖是方案一的核心控制邏輯的硬件調(diào)試時序圖。圖4.2 方案一硬件調(diào)試時序圖其中，ip_go是控制ip移動的脈沖信號，每一個脈沖都使ip移動一個字節(jié)。state是用于匹配查找狀態(tài)切換標志，每個時鐘加

37、一。hash_ip是hash值。4.1.4 壓縮速度計算該LZ4壓縮核主頻是150MHz。由時序圖可以看出查找匹配時每3個狀態(tài)，ip加1，也就是每3個時鐘ip加1。而找到匹配后每2個狀態(tài)ip加1，也就是ip每2個時鐘加1。按照極限情況計算。最小壓縮速度：當全不可匹配時，由上述分析可知ip移動速度大約是150MHz/s除以3得50MByte/s。最大壓縮速度：當幾乎全可匹配時，由上述分析可知ip移動速度大約是150MHz/s除以2得75MByte/s。4.2 方案二4.2.1 硬件框圖與方案一不同的是，方案二需要優(yōu)化硬件結(jié)構(gòu)，縮短時序，同時去掉那個32位64k地址的RAM塊，通過返回讀取緩存中的

38、數(shù)據(jù)然后再進行沖突判斷，這樣做的好處在于減少了RAM資源的消耗，可以使程序消耗更少的資源。但是由于需要返回讀取數(shù)據(jù)，可能會因為沖突造成大量的時間開銷，從而降低壓縮速度。同時由于沖突的影響會導致程序工作時的壓縮速度極不穩(wěn)定。下列圖給出了方案二的硬件框圖： 圖4.3 方案二硬件框圖下面將介紹方案二的算法流程。4.2.2 算法流程1方案二核心算法流程：1啟動壓縮時，通過ip控制，每個時鐘ip加一，同時控制移位存放器移位，當ip等于4時啟動hash計算得出hash值。同時hash表以及4字節(jié)存儲空間寫輸入使能。2一個時鐘后繼續(xù)計算hash值。同時讀出hash表中的地址Ref以及4字節(jié)存儲空間中的4個字

39、節(jié)U32Ref。同時寫入當前的ip值以及移位存放器輸出的32位數(shù)據(jù)U32ip。假設Ref小于當前ip值且不為0那么說明當前4個字節(jié)與地址在Ref處的4個字節(jié)有可能相同，啟動沖突判斷程序進入步驟3；否那么繼續(xù)。假設ip大于輸入數(shù)據(jù)大小減5后的結(jié)果那么跳到步驟7。3通過Ref控制讀出位于Ref處匹配的4個相應的字節(jié)。進入步驟4。4判斷U32ip與Ref處4個字節(jié)是否相等，相等那么進入步驟5，否那么返回步驟2。5移動Ref到匹配的4字節(jié)后一字節(jié)處，判斷dRef與dip是否相等，假設相等，控制Ref與ip加1后繼續(xù)判斷；否那么進入步驟6。假設ip大于輸入數(shù)據(jù)大小減5后的結(jié)果那么跳到步驟7。6一個序列查

40、找完成，增加ip，控制移位存放器，使移位存放器中不再有前面的匹配字符，然后回到步驟2,開始查找下一個序列。7剩余數(shù)據(jù)生成一個單獨的序列，offset為0，匹配長度為0。2token、offset、match length以及l(fā)iteral length計算流程l token：核心控制處于步驟6且步驟6剛結(jié)束時，假設不可匹配字符小于15，那么用token高4位表示不可匹配字符大小，否那么token高4位為15；假設可匹配字符小于19，那么用token低4位等于可匹配字符大小減4，否那么token高4位為15。l Offset：核心控制處于步驟3時，offset等于ip減去Ref。l litera

41、l length：核心控制處于步驟2時，通過對控制ip模塊的控制信號時長進行計數(shù)，獲得不可匹配字符的大小，假設其小于15那么literal length為0，且不輸出。假設不可匹配字符的大小大于15時，literal length等于不可匹配字符的大小減去15。l match length：核心控制處于步驟5和步驟6時，通過對控制ip模塊的控制信號時長進行計數(shù)，獲得可匹配字符的大小，假設其小于19那么match length為0，且不輸出。3輸出控制算法流程1復位后等待第一個序列完成。2第一個序列完成后，依次寫入token、literal length、literal、offset、match

42、 length。3等待，當前序列完成后返回第2步直到結(jié)束。4.2.3 硬件調(diào)試時序圖如圖4.4所示是方案二的核心控制邏輯的硬件調(diào)試時序圖。圖4.4 方案二硬件調(diào)試時序圖其中，Ip_go是控制ip移動的使能信號，只要ip_go為1那么每一個時鐘都使ip移動一個字節(jié)。State是用于返回讀取匹配的4字節(jié)的狀態(tài)切換標志，每個時鐘加一。Hash_ip是hash值。4.2.4 壓縮速度計算該LZ4壓縮核的主頻為140MHz。由硬件調(diào)試時序圖可以看出，一個序列至少包含9個空閑時鐘。最小壓縮速度：由于沖突數(shù)量并不可預測，所以最低速度無法通過計算獲得，只能通過估計大概數(shù)值。hash表為64k大小，按照每個序列

43、都會遇到?jīng)_突，同時可壓縮與不可壓縮各一半，那么壓縮速度為：140*8/18=62.2MByte/s。最大壓縮速度：當沒有沖突時且壓縮產(chǎn)生的序列越少時速度越大，按照極限計算，只有一個序列，且無沖突，那么最大速度為140MByte/s。通過對測試文件的仿真計算得到，仿真文件的壓縮速度為75MByte/s符合計算范圍。4.3 方案三4.3.1 硬件框圖方案三的結(jié)構(gòu)結(jié)合了以上兩個方案，同樣需要優(yōu)化硬件結(jié)構(gòu)，縮短時序。但是和方案一一樣，添加一個32位64k地址的RAM塊，這樣就可以有效的防止沖突帶來的額外時間開銷，但是對硬件資源消耗較大。下列圖為方案三硬件框圖： 圖4.5 方案三硬件圖下面將介紹方案三算

44、法流程。4.3.2 算法流程1核心算法流程1啟動壓縮時，通過ip控制，每個時鐘ip加一，同時控制移位存放器移位，當ip等于4時啟動hash計算得出hash值。同時hash表以及4字節(jié)存儲空間寫輸入使能。2一個時鐘后繼續(xù)計算hash值。同時讀出hash表中的地址Ref以及4字節(jié)存儲空間中的4個字節(jié)U32Ref。同時寫入當前的ip值以及移位存放器輸出的32位數(shù)據(jù)U32ip。假設Ref小于當前ip值且不為0，同時U32Ref等于U32ip那么說明當前4個字節(jié)與地址在Ref處的4個字節(jié)相同，啟動匹配程序進入步驟3；否那么繼續(xù)。假設ip大于輸入數(shù)據(jù)大小減5后的結(jié)果那么跳到步驟4。3移動Ref到匹配的4字

45、節(jié)后一字節(jié)處，判斷dRef與dip是否相等，假設相等，控制Ref與ip加1后繼續(xù)判斷；否那么進入步驟2。假設ip大于輸入數(shù)據(jù)大小減5后的結(jié)果那么跳到步驟4。4剩余數(shù)據(jù)生成一個單獨的序列，offset為0，匹配長度為0。2token、offset、match length以及l(fā)iteral length計算流程l token：核心控制處于步驟2且步驟2已經(jīng)執(zhí)行3個時鐘時，假設不可匹配字符小于15，那么用token高4位表示不可匹配字符大小，否那么token高4位為15；假設可匹配字符小于19，那么用token低4位等于可匹配字符大小減4，否那么token高4位為15。l offset：核心控制處

46、于步驟3開始時，offset等于ip減去Ref。l literal length：核心控制處于步驟2時，通過對控制ip模塊的控制信號時長進行計數(shù)，獲得不可匹配字符的大小，假設其小于15那么literal length為0，且不輸出。假設不可匹配字符的大小大于15時，literal length等于不可匹配字符的大小減去15。l match length：核心控制處于步驟3 時，通過對控制ip模塊的控制信號時長進行計數(shù)，獲得可匹配字符的大小，假設其小于19那么match length為0，且不輸出。3輸出控制算法流程1復位后開始查找匹配后第4個時鐘起將不可匹配字符從緩存中輸入到輸出緩存中。2等到

47、查找到匹配后此時由于匹配檢測的延時恰好將不可匹配字符全部從緩存中寫入到輸出緩存，然后立即將offset寫入到輸出緩存中，假設不可匹配字符大于等于15那么按照規(guī)那么立即寫入literal length，假設小于15，那么不用寫literal length。3等到后向匹配查找結(jié)束后，假設匹配字符長度大于等于19那么接在offset后面寫入match length，假設匹配字符長度小于19，那么不用寫match length。4在后向匹配查找結(jié)束后第三個時鐘寫入token，然后回到第一步開始寫入下一個序列的不可匹配字符。4.3.3 硬件調(diào)試時序圖如圖4.6所示為核心控制邏輯的硬件調(diào)試時序圖。圖4.6

48、 方案三硬件調(diào)試時序圖其中，literal_ip_go是當查找匹配時控制ip移動的使能信號，只要literal_ip_go為1那么每一個時鐘都使ip移動一個字節(jié)。而當literal_ip_go為0時間隔一個時鐘就啟動匹配控制ip移動。4.3.4 壓縮速度計算該LZ4壓縮核的主頻為140MHz。由硬件調(diào)試時序圖中ip的變化可以看出，一個序列只包含1個空閑時鐘。最小壓縮速度：由于一個序列只包含1個空閑時鐘，當序列最多時速度最慢，那么按照不可壓縮與可壓縮各占一半，以及每個序列包含4個不可匹配字符與4個可匹配字符計算，那么最小速度為140*8/9=124.4MByte/s。最大壓縮速度：只要單位時間內(nèi)

49、產(chǎn)生的序列越少，壓縮速度越快。那么按照極限計算，全是不可匹配字符或者幾乎全是可匹配字符的情況下，壓縮速度接近于140MByte/s。4.4 各方案優(yōu)缺點分析4.4.1 資源消耗比擬由于LZ4核對RAM塊的消耗最大，所以只要RAM足夠其余資源也就滿足消耗。方案一：占用RAM大小為521kByte；方案二：占用RAM大小為256kByte；方案三：占用RAM大小為320kByte；4.4.2 壓縮速度比擬由上述分析可得：方案一：壓縮速度為5075MByte/s；方案二：壓縮速度大約為62.2140MByte/s；方案三：壓縮速度為124.4140MByte/s；4.4.3 最正確方案選擇下表給出了

50、三種方案的優(yōu)缺點比擬：表4.1 各方案優(yōu)缺點比擬特點優(yōu)點缺點方案一添加一個寬32位深64k的RAM表存儲與hash表中對應的32位的4字節(jié)，檢測是否匹配或沖突時可直接輸出比擬，減少時序。硬件易于實現(xiàn)，每次循環(huán)完成hash值計算、判斷。占用資源多，速度慢。方案二去掉寬32位深64k的RAM表，返回匹配處，讀取匹配的4個字節(jié)與當前4個字節(jié)進行比擬查找沖突。減少hash計算開銷，采用流水線形式，計算hash值的同時輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待hash計算檢測沖突后執(zhí)行下一步，提高速度。占用資源少，可以實現(xiàn)更多的核并行使用。時序變長，最低壓縮速度無法保證。方案三添加一個寬32位深32k的RAM表存儲

51、與hash表中對應的32位的4字節(jié)，檢測是否匹配或沖突時可直接輸出比擬，減少時序。減少hash計算開銷，采用流水線形式，計算hash值的同時輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待hash計算檢測沖突后執(zhí)行下一步，提高速度。占用資源不算多，壓縮速度快且穩(wěn)定不受沖突的影響。硬件實現(xiàn)比擬困難，時序緊湊對于原來的官方格式，沒有足夠的時間進行處理計算。由表4.1可以看出，在速度與資源上，方案三的優(yōu)勢比擬大，對應缺點可以通過更改LZ4輸出格式來解決，具體格式見第2.3節(jié)。第五章 LZ4無損壓縮算法硬件實現(xiàn)通過以上章節(jié)描述，確定選擇方案三后，通過kintex7 kc705開發(fā)板來實現(xiàn)并驗證方案三的功能與性能，下面主

52、要介紹硬件實現(xiàn)各個模塊的功能。5.1 LZ4核總體框架想要輸入數(shù)據(jù)開始壓縮之前將復位信號rst1置0，input_en和wea_ip置1，然后輸入數(shù)據(jù)以及數(shù)據(jù)地址，每個數(shù)據(jù)對應一個地址，輸入結(jié)束后，將input_en和wea_ip置0，當all_end為1時表示可以輸出數(shù)據(jù)，數(shù)據(jù)大小為op，將op之內(nèi)的數(shù)據(jù)通過out_dop輸出，out_op是其對應的地址。下列圖給出了LZ4核總體框架：圖5.1 LZ4核總體框架接口說明如下表：表5.1 接口說明接口名稱輸入輸出說明ip_ininput輸入數(shù)據(jù)地址dip_ininput輸入數(shù)據(jù)input_eninput輸入使能1有效wea_ipinput緩存寫

53、入使能1有效rst1input復位1有效out_opinput輸出數(shù)據(jù)地址out_dopoutput輸出數(shù)據(jù)Opoutput壓縮后的數(shù)據(jù)大小all_endoutput壓縮完成標志1有效5.2 LZ4壓縮驗證結(jié)構(gòu)圖下列圖給出了LZ4壓縮驗證結(jié)構(gòu)圖： 圖5.2 LZ4壓縮驗證結(jié)構(gòu)圖添加數(shù)據(jù)接口用做輸入輸出，便于對數(shù)據(jù)進行功能性驗證，將壓縮后的數(shù)據(jù)通過數(shù)據(jù)接口傳回電腦處理。5.3 LZ4核內(nèi)部模塊功能說明1ip控制模塊圖5.3 ip控制模塊框圖此模塊功能為：對ip執(zhí)行加1和復位運算。說明：當復位信號有效時，ip為0。當信號go為1時，對ip執(zhí)行加1運算。2移位存放器控制模塊移位存放器控制模塊如下列圖

54、所示：圖5.4 移位存放器控制模塊框圖移位存放器功能為：將從輸入緩存中讀取的數(shù)據(jù)通過移位存放變成32位的數(shù)據(jù)，便于核心控制模塊中計算hash值等運算。說明：當復位信號有效時，U32為0。當信號go為1時，對U32執(zhí)行加移位運算，dat_4是U32的前8位。3Ref控制模塊圖5.5 Ref控制模塊框圖功能：實現(xiàn)對Ref的寫入、復位、以及加1計算。說明：rst是復位信號，復位后Ref為0。如果Ref_write為1，那么Ref等于Ref1；如果Ref_write為0，那么Ref從當前數(shù)值開始執(zhí)行加1運算。4 hash表生成與流程控制模塊圖5.6 核心控制模塊框圖功能：實現(xiàn)hash值計算、實現(xiàn)has

55、h表寫入讀出、輸出ip控制信號ip_go、輸出移位存放器控制信號、控制Ref的寫入、查找匹配判沖突、判斷匹配長度、計算偏移量offset判斷ip是否移動到末尾。說明：通過U32ip計算出ash值，再據(jù)hash值執(zhí)行對hash表的寫入讀出，假設當前地址與hash表中的地址之差小于64k那么表示hash表中的地址有效，假設大于64k那么表示hash表中的地址無效，寫入當前地址再計算下一個數(shù)據(jù)的hash值重復上面的步驟。當hash表中的地址有效時，比擬該地址起往后的4個字節(jié)與U32ip是否相同，假設相同那么代表匹配，不同那么重復上述步驟直到匹配。查找到匹配后再計算偏移量。同時在查找過程中通過不同狀態(tài)控制ip_g