【正文】 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 29 第六章 LZ4 無損壓縮算法硬件實(shí)現(xiàn)功能測 試 驗(yàn)證數(shù)據(jù)壓縮的正確性不能只是對于時(shí)序進(jìn)行分析，通過壓縮解壓后比較兩個(gè)文件是否相同才能完全說明數(shù)據(jù)壓縮的功能正確，因此本章節(jié)描述了如何進(jìn)行小規(guī)模數(shù)據(jù)測試來驗(yàn)證LZ4 壓縮核的正確性。 （ 1） 開發(fā)環(huán)境 表 開發(fā)環(huán)境 開發(fā)板 芯片型號 開發(fā)平臺 Kintex7 KC705 Xc7k325tffg9002 （ 2） 資源消耗情況 表 資源消耗情況 資源列表 已使用的資源 可使用的資源 百分比 FF 605 407600 LUT 1302 203800 Memory LUT 1 64000 I/O 15 500 BRAM 445 BUFG 3 32 MMCM 1 10 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 28 下圖給出了資 源消耗條形圖： 圖 資源消耗條形圖 （ 3）壓縮速度 LZ4 核主頻： 140MHz。 5）最后寫入 token。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 27 寫入分為 5 個(gè)狀態(tài) 1）寫入字符串； 2）寫入 offset； 3）如果 literal_ength 不為 0，寫入 literal_ength。 （ 7） 寫入控制模塊 圖 寫入控制模塊框圖 功能： 控制生成數(shù)據(jù)按照 LZ4 規(guī)則寫入輸出緩存。 說明： 通過 literal_ip_go 進(jìn)行計(jì)數(shù)，計(jì)算匹配長度大小，最后一個(gè)序列為 0。 說明： 內(nèi)部有一個(gè) 8kByte 的 RAM 用于對不可匹配字符進(jìn)行緩存。同時(shí)在查找過程中通過不同狀態(tài)控制 ip_go、Ref_write、 U32ip_go 等控制外圍模塊實(shí)現(xiàn)相應(yīng)的功能，使得查找匹配繼續(xù)往下進(jìn)行。當(dāng) hash 表中的地址有效時(shí)，比較該地址起往后的 4 個(gè)字節(jié)與 U32ip 是否相同，若相同則代表匹配，不同則重復(fù)上述步驟直到匹配。 （ 4） hash 表生成與流程控制模塊 圖 核心 控制模塊框圖 功能： 實(shí)現(xiàn) hash 值計(jì)算、實(shí)現(xiàn) hash 表寫入讀出、輸出 ip 控制信號 ip_go、輸出移位寄存器控制 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 25 信號、控制 Ref 的寫入、查找匹配判沖突、判斷匹配長度、計(jì)算偏移量 offset 判斷 ip 是否移動到末尾。 說明： rst 是復(fù)位信號，復(fù)位后 Ref 為 0。當(dāng)信號 go 為 1 時(shí)，對 U32 執(zhí)行加移位運(yùn)算， dat_4 是 U32的前 8 位。 （ 2）移位寄存器控制模塊 移位寄存器控制模塊如下圖所示： 圖 移位寄存器控制模塊框圖 移位寄存器功能為： 將從輸入緩存中讀取的數(shù)據(jù)通過移位寄存變成 32 位的數(shù)據(jù)，便于核心控制模塊中計(jì)算hash 值等運(yùn)算。 說明： 當(dāng)復(fù)位信號有效時(shí)， ip 為 0。 下圖給出了 LZ4 核總體框架： 圖 LZ4 核總體框架 接口說明如下表： 表 接口說明 接口名稱 輸入輸出 說明 ip_in input 輸入數(shù)據(jù)地址 dip_in input 輸入數(shù)據(jù) input_en input 輸入使能（ 1 有效） wea_ip input 緩存寫入使能（ 1 有效） 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 22 rst1 input 復(fù)位（ 1 有效） out_op input 輸出數(shù)據(jù)地址 out_dop output 輸出數(shù)據(jù) Op output 壓縮后的數(shù)據(jù)大小 all_end output 壓縮完成標(biāo)志（ 1 有效） LZ4 壓縮驗(yàn)證結(jié)構(gòu)圖 下圖給出了 LZ4 壓縮驗(yàn)證結(jié)構(gòu)圖： 圖 LZ4 壓縮驗(yàn)證結(jié)構(gòu)圖 添加 數(shù)據(jù) 接口用做輸入輸出，便于對數(shù)據(jù)進(jìn)行功能性驗(yàn)證，將壓縮后的數(shù)據(jù)通過 數(shù)據(jù)接口 傳回電腦處理。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 21 第五章 LZ4 無損壓縮算法硬件實(shí)現(xiàn) 通過以上章節(jié)描述，確定選擇方案三后，通過 kintex7 kc705 開發(fā)板來實(shí)現(xiàn)并驗(yàn)證方案三的功能與性能，下面主要介紹硬件實(shí)現(xiàn)各個(gè)模塊的功能。 硬件實(shí) 現(xiàn)比較困難，時(shí)序緊湊對于原來的官方格式，沒有足夠的時(shí)間進(jìn)行處理計(jì)算。 減少 hash計(jì)算開銷，采用流水線形式，計(jì)算 hash值的同時(shí)輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待 hash計(jì)算檢測沖突后執(zhí)行下一步，提高速度。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 20 值的同時(shí)輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待 hash計(jì)算檢測沖突后執(zhí)行下一步，提高速度。 減少 hash計(jì)算開銷，采用流水線形式，計(jì)算 hash占用資源少，可以實(shí) 現(xiàn)更多的核并行使用。 占用資源多，速度慢。 方案一：占用 RAM 大小為 521kByte； 方案二：占用 RAM 大小為 256kByte； 方案三：占用 RAM 大小為 320kByte； 壓縮速度比較 由上述分析可得： 方案一：壓縮速度為 50— 75MByte/s； 方案二：壓縮速度大約為 — 140MByte/s； 方案三：壓縮速度為 — 140MByte/s； 最佳方案選擇 下表給出了三種方案的優(yōu)缺點(diǎn)比較： 表 各方案優(yōu)缺點(diǎn)比較 特點(diǎn) 優(yōu)點(diǎn) 缺點(diǎn) 方案一 添加一個(gè)寬 32 位深 64k 的 RAM表存儲與 hash 表中對應(yīng)的 32 位的 4字節(jié)，檢測是否匹配或沖突時(shí)可直接輸出比較，減少時(shí)序。則按照極限計(jì)算，全是不可匹配字符或者幾乎全是可匹配字符的情況下，壓縮速度接近于 140MByte/s。 最小壓縮速度：由于一個(gè)序列只包含 1 個(gè)空閑時(shí)鐘，當(dāng)序列最多時(shí)速度最慢，則按照不可壓縮與可壓縮各占一半，以及每個(gè)序列包含 4 個(gè)不可匹配字符與 4 個(gè)可匹配字符計(jì)算，則最小速度為 140*8/9=。 壓縮速度計(jì)算 該 LZ4 壓縮核 的主頻為 140MHz。 圖 方案三硬件調(diào)試時(shí)序圖 其中， literal_ip_go 是當(dāng)查找匹配時(shí)控制 ip 移動的使能信號，只要 literal_ip_go 為 1 則每一個(gè)時(shí)鐘都使 ip 移動一個(gè)字節(jié)。 4）在后向匹配查找結(jié)束后第三個(gè)時(shí)鐘寫入 token，然后回到第一步開始寫入下一個(gè)序列的不可匹配字符。 2）等到查找到匹配后此時(shí)由于匹配檢測的延時(shí)恰好將不可匹配字符全部從緩存中寫入到輸出緩存，然后立即將 offset 寫入到輸出緩存中，若不可匹配字符大于等于 15 則按照規(guī)則立即寫入 literal length，若小于 15，則不用寫 literal length。 ? match length：核心控制處于步驟 3 時(shí)，通過對控制 ip 模塊的控制信號時(shí)長進(jìn)行計(jì)數(shù)，獲得可匹配字符的大小，若其小于 19 則 match length 為 0，且不輸出。 畢業(yè)設(shè)計(jì)（論文）報(bào)告紙 18 ? literal length：核心控制處于步驟 2 時(shí)，通過對控制 ip 模塊的控制信號時(shí)長進(jìn)行計(jì)數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。 （ 2） token、 offset、 match length 以及 literal length 計(jì)算流程 ? token：核心控制處于步驟 2 且步驟 2 已經(jīng)執(zhí)行 3 個(gè)時(shí)鐘時(shí)，若不可匹配字符小于 15，則用 token 高 4 位表示不可匹配字符大小，否則 token 高 4 位為 15；若可匹配字符小于 19，則用 token 低 4 位等于可匹配字符大小減 4， 否則 token 高 4 位為 15。若 ip 大于輸入數(shù)據(jù)大小減 5 后的結(jié)果則跳到步驟 4。若 ip 大于輸入數(shù)據(jù)大小減 5 后的結(jié)果則跳到步驟 4。同時(shí)寫入當(dāng)前的 ip 值以及移位寄存器輸出的 32 位數(shù)據(jù) U32ip。 2）一個(gè)時(shí)鐘后繼續(xù)計(jì)算 hash 值。 算法流程 （ 1）核心算法流程 1）啟動壓縮時(shí)，通過 ip 控制，每個(gè)時(shí)鐘 ip 加一，同時(shí)控制移位寄存器 移位，當(dāng) ip 等于4 時(shí)啟動 hash 計(jì)算得出 hash 值。但是和方案一一樣，添加一個(gè) 32 位 64k 地址的 RAM 塊，這樣就可以有效的避免沖突帶來的額外時(shí)間開銷，但是對硬件資源消耗較大。 通過對測試文件的仿真計(jì)算得到，仿真文件的壓縮速度為 75MByte/s 符合計(jì)算范圍。 hash 表為 64k 大小，按照每個(gè)序列都會遇到?jīng)_突，同時(shí)可壓縮與不可壓縮各一半，則壓縮速度為： 140*8/18=。 由硬件調(diào)試時(shí)序圖可以看出，一個(gè)序列至少包含 9 個(gè)空閑時(shí)鐘。 Hash_ip 是 hash值。 圖 方案二 硬件調(diào)試時(shí)序圖 其中， Ip_go 是控制 ip 移動的使能信號，只要 ip_go 為 1 則每一個(gè)時(shí)鐘都使 ip 移動一個(gè)字節(jié)。 3）等待，當(dāng)前序列完成后返回第 2 步直到結(jié)束。 （ 3）輸出控制算法流程 1）復(fù)位后等待第一個(gè)序列完成。若不可匹配字符的大小大于 15 時(shí)， literal length 等于不可匹配字符的大小減去 15。 ? Offset：核心控制處于步驟 3 時(shí)， offset 等于 ip 減去 Ref。 7）剩余數(shù)據(jù)生成一個(gè)單獨(dú)的序列， offset 為 0，匹配長度為 0。若 ip 大于輸入數(shù)據(jù)大小減 5 后的結(jié)果則跳到步驟 7。 4）判斷 U32ip 與 Ref 處 4 個(gè)字節(jié)是否相等，相等則進(jìn)入步驟 5，否則返回步驟 2。 3）通過 Ref 控制讀出位于 Ref 處匹配的 4 個(gè)相應(yīng)的字節(jié)。若 Ref小于當(dāng)前 ip 值且不為 0 則說 明當(dāng)前 4 個(gè)字節(jié)與地址在 Ref 處的 4 個(gè)字節(jié)有可能相同，啟動沖突判斷程序進(jìn)入步驟 3；否則繼續(xù)。同時(shí)讀出 hash 表中的地址 Ref 以及 4 字節(jié)存儲空間中的 4 個(gè)字節(jié) U32Ref。同時(shí) hash 表以及 4 字節(jié)存儲空間寫輸入使能。 下圖 給出了方案二的硬件框圖： 圖 方案二硬件框圖 下面將介紹方案二的算法流程。但是由于需要返回讀取數(shù)據(jù)，可能會因?yàn)闆_突造成大量的時(shí)間開銷，從而降低壓縮速度。 最大壓縮速度：當(dāng)幾乎全可匹配時(shí)，由上述分析可知 ip 移動速度大約是 150MHz/s 除以 2得 75MByte/s。按照極限情況計(jì)算。由時(shí)序圖可以看出查找匹配時(shí)每 3 個(gè)狀態(tài)， ip 加 1，也就是每 3 個(gè)時(shí)鐘 ip 加 1。 hash_ip 是 hash 值。 圖 方案一硬件調(diào)試時(shí)序圖 其中， ip_go 是控制 ip 移動的脈沖信號，每一個(gè)脈沖都使 ip 移動一個(gè)字節(jié)。 3）等待，當(dāng)前序列完成后返回第 2 步直到結(jié)束。 （ 3）輸出控制算法流程 1）復(fù)位后等待第一個(gè)序列完成。若不可匹配字符的大小大于 15 時(shí)， literal length 等于不可匹配字符的大小減去 15。 ? Offset：核心控制處于步驟 5 時(shí)， offset 等于 ip 減去 Ref。 8）剩余數(shù)據(jù)生成一個(gè)單獨(dú)的序列， offset 為 0，匹配長度為 0。若 ip 移動到倒數(shù)第 5 個(gè)字節(jié)時(shí)不論 dRef 與 dip 是否相等都跳到步驟 8。 5）通過 Ref 控制讀 出位于 Ref 處匹配 4 字節(jié)后的相應(yīng)字節(jié)。 4） hash 表以及 4 字節(jié)存儲空間允許輸入，發(fā)脈沖信號給 ip 控制，使 ip 加 1,同時(shí)控制移位寄存器移動一位，若 ip 未移動到倒數(shù)第 5 個(gè)字節(jié)時(shí)回到步驟 2。同時(shí)寫入當(dāng)前的 ip 值以及移位寄存器輸出的 32 位數(shù)據(jù) U32ip。同時(shí) hash 表以及 4 字節(jié)存儲空間寫輸入使能。 算法流程 （ 1）方案一核心算法流程如下： 1）啟動壓縮時(shí)，通過 ip 控制，每個(gè)時(shí)鐘 ip 加一，同時(shí)控制移位寄存器移位，當(dāng) ip 等于4 時(shí)停止，同時(shí)停下移位寄存器移位。輸出模塊根據(jù)接收到的數(shù)據(jù)組合后輸出到輸出緩存中完成壓縮操作。在查找的同時(shí)將不可匹配字符傳輸給輸出控制，通過字符長度模塊計(jì)算不可匹配字符長 度然后傳給輸出控制。這樣做的好處在于省去了沖突帶來的額外時(shí)間開銷，同時(shí)可以減少查找匹配的步驟提高壓縮速度。每一個(gè)方案都通過仿真驗(yàn)證，其性能也通過仿真測試過，以下就是方案的具體描述。 8）待拷貝完成后，讀取下一個(gè) token，按照上述 規(guī)則繼續(xù)往下解壓直到解壓到末尾地址結(jié)束。若 token 低 4位小于 15，說明可匹配字符長度等于 token 低 4 位的值再加上 4。 5）根據(jù)不可匹配字符長度計(jì)算出 offset 的位置，讀取 offset 的倆個(gè)字節(jié)，將其拼接成一個(gè) 16 位的數(shù)據(jù)，根據(jù) offset 確定匹配的位置。若 token 高 4位小于 15，說明不