【正文】 步驟 4。 4）剩余數(shù)據(jù)生成一個單獨的序列， offset 為 0，匹配長度為 0。 （ 2） token、 offset、 match length 以及 literal length 計算流程 ? token：核心控制處于步驟 2 且步驟 2 已經(jīng)執(zhí)行 3 個時鐘時，若不可匹配字符小于 15，則用 token 高 4 位表示不可匹配字符大小，否則 token 高 4 位為 15；若可匹配字符小于 19，則用 token 低 4 位等于可匹配字符大小減 4， 否則 token 高 4 位為 15。 ? offset：核心控制處于步驟 3 開始時， offset 等于 ip 減去 Ref。 畢業(yè)設(shè)計（論文）報告紙 18 ? literal length：核心控制處于步驟 2 時，通過對控制 ip 模塊的控制信號時長進行計數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。若不可匹配字符的大小大于 15 時， literal length 等于不可匹配字符的大小減去 15。 ? match length：核心控制處于步驟 3 時，通過對控制 ip 模塊的控制信號時長進行計數(shù)，獲得可匹配字符的大小，若其小于 19 則 match length 為 0，且不輸出。 （ 3）輸出控制算法流程 1）復(fù)位后開始查找匹配后第 4 個時鐘起將不可匹配字符從緩存中輸入到輸出緩存中。 2）等到查找到匹配后此時由于匹配檢測的延時恰好將不可匹配字符全部從緩存中寫入到輸出緩存，然后立即將 offset 寫入到輸出緩存中，若不可匹配字符大于等于 15 則按照規(guī)則立即寫入 literal length，若小于 15，則不用寫 literal length。 3）等到后向匹配查找結(jié)束后，若匹配字符長度大于等于 19 則接在 offset 后面寫入 match length，若匹配字符長度小于 19，則不用寫 match length。 4）在后向匹配查找結(jié)束后第三個時鐘寫入 token，然后回到第一步開始寫入下一個序列的不可匹配字符。 硬件調(diào)試時序圖 如圖 所示為核心控制邏輯的硬件調(diào)試時序圖。 圖 方案三硬件調(diào)試時序圖 其中， literal_ip_go 是當(dāng)查找匹配時控制 ip 移動的使能信號，只要 literal_ip_go 為 1 則每一個時鐘都使 ip 移動一個字節(jié)。而當(dāng) literal_ip_go 為 0 時間隔一個時鐘就啟動匹配控制 ip 移動。 壓縮速度計算 該 LZ4 壓縮核 的主頻為 140MHz。 畢業(yè)設(shè)計（論文）報告紙 19 由硬件調(diào)試時序圖中 ip 的變化可以看出，一個序列只包含 1 個空閑時鐘。 最小壓縮速度：由于一個序列只包含 1 個空閑時鐘，當(dāng)序列最多時速度最慢，則按照不可壓縮與可壓縮各占一半，以及每個序列包含 4 個不可匹配字符與 4 個可匹配字符計算，則最小速度為 140*8/9=。 最大壓縮速度：只要單位時間內(nèi)產(chǎn)生的序列越少，壓縮速度越快。則按照極限計算，全是不可匹配字符或者幾乎全是可匹配字符的情況下，壓縮速度接近于 140MByte/s。 各方案 優(yōu)缺點分析 資源消耗比 較 由于 LZ4 核對 RAM 塊的消耗最大，所以只要 RAM 足夠其余資源也就滿足消耗。 方案一：占用 RAM 大小為 521kByte； 方案二：占用 RAM 大小為 256kByte； 方案三：占用 RAM 大小為 320kByte； 壓縮速度比較 由上述分析可得： 方案一：壓縮速度為 50— 75MByte/s； 方案二：壓縮速度大約為 — 140MByte/s； 方案三：壓縮速度為 — 140MByte/s； 最佳方案選擇 下表給出了三種方案的優(yōu)缺點比較： 表 各方案優(yōu)缺點比較 特點 優(yōu)點 缺點 方案一 添加一個寬 32 位深 64k 的 RAM表存儲與 hash 表中對應(yīng)的 32 位的 4字節(jié)，檢測是否匹配或沖突時可直接輸出比較，減少時序。 硬件易于實現(xiàn)，每次循環(huán)完成 hash值計算、判斷。 占用資源多，速度慢。 方案二 去掉寬 32位深 64k 的 RAM 表，返回匹配處，讀取匹配的 4 個字節(jié)與當(dāng)前 4 個字節(jié)進行比較查找沖突。 減少 hash計算開銷，采用流水線形式，計算 hash占用資源少，可以實 現(xiàn)更多的核并行使用。 時序變長，最低壓縮速度無法保證。 畢業(yè)設(shè)計（論文）報告紙 20 值的同時輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待 hash計算檢測沖突后執(zhí)行下一步，提高速度。 方案三 添加一個寬 32 位深 32k 的 RAM 表存儲與hash 表中對應(yīng)的 32 位的 4字節(jié)，檢測是否匹配或沖突時可直接輸出比較，減少時序。 減少 hash計算開銷，采用流水線形式，計算 hash值的同時輸入數(shù)據(jù)，不用輸入數(shù)據(jù)后再等待 hash計算檢測沖突后執(zhí)行下一步，提高速度。 占用資源不算多，壓縮速度快且穩(wěn)定不受沖突的影響。 硬件實 現(xiàn)比較困難，時序緊湊對于原來的官方格式，沒有足夠的時間進行處理計算。 由表 可以看出，在速度與資源上，方案三的優(yōu)勢比較大，對應(yīng) 缺點可以通過更改 LZ4輸出格式來解決，具體格式見第 節(jié)。 畢業(yè)設(shè)計（論文）報告紙 21 第五章 LZ4 無損壓縮算法硬件實現(xiàn) 通過以上章節(jié)描述，確定選擇方案三后，通過 kintex7 kc705 開發(fā)板來實現(xiàn)并驗證方案三的功能與性能，下面主要介紹硬件實現(xiàn)各個模塊的功能。 LZ4 核總體框架 想要輸入數(shù)據(jù)開始壓縮之前將復(fù)位信號 rst1 置 0， input_en 和 wea_ip 置 1，然后輸入數(shù)據(jù)以及數(shù)據(jù)地址，每個數(shù)據(jù)對應(yīng)一個地址，輸入結(jié)束后，將 input_en 和 wea_ip 置 0，當(dāng) all_end為 1 時表示可以輸出數(shù)據(jù)，數(shù)據(jù)大小為 op， 將 op 之內(nèi)的數(shù)據(jù)通過 out_dop 輸出， out_op 是其對應(yīng)的地址。 下圖給出了 LZ4 核總體框架： 圖 LZ4 核總體框架 接口說明如下表： 表 接口說明 接口名稱 輸入輸出 說明 ip_in input 輸入數(shù)據(jù)地址 dip_in input 輸入數(shù)據(jù) input_en input 輸入使能（ 1 有效） wea_ip input 緩存寫入使能（ 1 有效） 畢業(yè)設(shè)計（論文）報告紙 22 rst1 input 復(fù)位（ 1 有效） out_op input 輸出數(shù)據(jù)地址 out_dop output 輸出數(shù)據(jù) Op output 壓縮后的數(shù)據(jù)大小 all_end output 壓縮完成標志（ 1 有效） LZ4 壓縮驗證結(jié)構(gòu)圖 下圖給出了 LZ4 壓縮驗證結(jié)構(gòu)圖： 圖 LZ4 壓縮驗證結(jié)構(gòu)圖 添加 數(shù)據(jù) 接口用做輸入輸出，便于對數(shù)據(jù)進行功能性驗證，將壓縮后的數(shù)據(jù)通過 數(shù)據(jù)接口 傳回電腦處理。 LZ4 核內(nèi)部模塊功能說明 （ 1） ip 控制模塊 畢業(yè)設(shè)計（論文）報告紙 23 圖 ip 控制模塊框圖 此模塊功能為： 對 ip 執(zhí)行加 1 和復(fù)位運算。 說明： 當(dāng)復(fù)位信號有效時， ip 為 0。當(dāng)信號 go 為 1 時，對 ip 執(zhí)行加 1 運算。 （ 2）移位寄存器控制模塊 移位寄存器控制模塊如下圖所示： 圖 移位寄存器控制模塊框圖 移位寄存器功能為： 將從輸入緩存中讀取的數(shù)據(jù)通過移位寄存變成 32 位的數(shù)據(jù)，便于核心控制模塊中計算hash 值等運算。 說明： 當(dāng)復(fù)位信號有效時， U32 為 0。當(dāng)信號 go 為 1 時，對 U32 執(zhí)行加移位運算， dat_4 是 U32的前 8 位。 （ 3） Ref 控制模塊 畢業(yè)設(shè)計（論文）報告紙 24 圖 Ref 控制模塊框圖 功能： 實現(xiàn)對 Ref 的寫入、復(fù)位、以及加 1 計算。 說明： rst 是復(fù)位信號，復(fù)位后 Ref 為 0。 如果 Ref_write 為 1，則 Ref 等于 Ref1； 如果 Ref_write 為 0，則 Ref 從當(dāng)前數(shù)值開始執(zhí)行加 1 運算。 （ 4） hash 表生成與流程控制模塊 圖 核心 控制模塊框圖 功能： 實現(xiàn) hash 值計算、實現(xiàn) hash 表寫入讀出、輸出 ip 控制信號 ip_go、輸出移位寄存器控制 畢業(yè)設(shè)計（論文）報告紙 25 信號、控制 Ref 的寫入、查找匹配判沖突、判斷匹配長度、計算偏移量 offset 判斷 ip 是否移動到末尾。 說明： 通過 U32ip 計算出 ash 值，再據(jù) hash 值執(zhí)行對 hash 表的寫入讀出，若當(dāng)前地址與 hash表中的地址之差小于 64k 則表示 hash 表中的地址有效， 若大于 64k 則表示 hash 表中的地址無效，寫入當(dāng)前地址再計算下一個數(shù)據(jù)的 hash 值重復(fù)上面的步驟。當(dāng) hash 表中的地址有效時，比較該地址起往后的 4 個字節(jié)與 U32ip 是否相同，若相同則代表匹配，不同則重復(fù)上述步驟直到匹配。查找到匹配后再計算偏移量。同時在查找過程中通過不同狀態(tài)控制 ip_go、Ref_write、 U32ip_go 等控制外圍模塊實現(xiàn)相應(yīng)的功能，使得查找匹配繼續(xù)往下進行。 （ 5） token 計算模塊 圖 token 計算模塊框圖 功能： 對不可匹配字符進行緩存、計算不可匹配字符長度、計算 token 高 4 位大小、給出寫入控制時寫入 token 的時機。 說明： 內(nèi)部有一個 8kByte 的 RAM 用于對不可匹配字符進行緩存。 （ 6）匹配長度計算模塊 畢業(yè)設(shè)計（論文）報告紙 26 圖 匹配長度計算模塊框圖 功能： 計算匹配長度、計算 token 后 4 位大小。 說明： 通過 literal_ip_go 進行計數(shù)，計算匹配長度大小，最后一個序列為 0。通過匹配長度大小判斷 token 后 4 位的大小。 （ 7） 寫入控制模塊 圖 寫入控制模塊框圖 功能： 控制生成數(shù)據(jù)按照 LZ4 規(guī)則寫入輸出緩存。 說明： 通過輸入的條件進行判斷當(dāng)前寫入數(shù)據(jù) ，控制寫入狀態(tài)切換。 畢業(yè)設(shè)計（論文）報告紙 27 寫入分為 5 個狀態(tài) 1）寫入字符串； 2）寫入 offset； 3）如果 literal_ength 不為 0，寫入 literal_ength。 4）如果 match_length 不為 0，寫入 match_length。 5）最后寫入 token。 LZ4 核性能 用 FPGA 實現(xiàn)的 LZ4 算法的單核壓縮數(shù)據(jù)速度肯定沒有 PC 的壓縮速度快，因此 FPGA的優(yōu)勢在于并行處理可以添加多個核進行同時處理，但是 FPGA 的資源有限，減少單核的資源開銷就可以實現(xiàn)更多核的并行處理，從而提高壓縮速度。 （ 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è)計（論文）報告紙 28 下圖給出了資 源消耗條形圖： 圖 資源消耗條形圖 （ 3）壓縮速度 LZ4 核主頻： 140MHz。 通過計算可以得出壓縮速度為： 124— 140MByte/s。 畢業(yè)設(shè)計（論文）報告紙 29 第六章 LZ4 無損壓縮算法硬件實現(xiàn)功能測 試 驗證數(shù)據(jù)壓縮的正確性不能只是對于時序進行分析，通過壓縮解壓后比較兩個文件是否相同才能完全說明數(shù)據(jù)壓縮的功能正確，因此本章節(jié)描述了如何進行小規(guī)模數(shù)據(jù)測試來驗證LZ4 壓縮核的正確性。 測試框架圖 原始文件通過串口調(diào)試助手從 PC 機傳輸給