【正文】 字符長度后，將不可匹配字符復(fù)制到輸出緩存中。 6）若 token 低 4 位為 15，則從 offset 的兩個字節(jié)后讀取兩個字節(jié)，將這兩個字節(jié)合并成一個 16 位的數(shù)據(jù) match length，不可匹配字符長度就等于 match length 加上 19。 7）確定匹配字符長度后，從匹配的位置處開始向后拷貝字符，拷貝字符的長度和匹配字符的長度一致。 畢業(yè)設(shè)計（論文）報告紙 11 第四章 LZ4 無損壓縮算法硬件實現(xiàn)方案 本章節(jié)提出了三個不同的硬件實現(xiàn)方案，每個方案都有各自的側(cè)重點，方案一簡單，方案二提高速度的同時減少 RAM 資源消耗，方案三壓縮速度快。 方案一 硬件框圖 與官方無損壓縮算法不同的是添加了一個 32 位 64K 地址的 RAM 塊，用這個 RAM 塊來存儲與 hash值對應(yīng)的 32 位字節(jié)，在進行匹配判斷的時候不需要再返回在輸入緩存中讀取 hash表中的地 址對應(yīng)的 32 位數(shù)據(jù)，可以直接從該 RAM 塊讀出后判斷比較。 方案一的硬件模塊分為輸入緩存、 ip 控制、移位寄存器等 9 個模塊，通過 ip 控制將輸入緩存中的數(shù)據(jù)讀出傳送給移位寄存器，而移位寄存器將數(shù)據(jù)變成 32 位數(shù)據(jù)傳輸給核心控制模塊進行 hash 計算、匹配查找的操作，直到查找到匹配后，讀出匹配處的地址，根據(jù)地址讀出緩存中該地址后的數(shù)據(jù)，然后繼續(xù)后向匹配查找。在查找到匹配之后，通過匹配長度模塊計算匹配長度，將匹配長度傳給輸出模塊。 以下為方案一的硬件框圖： 畢業(yè)設(shè)計（論文）報告紙 12 圖 方案一硬件框圖 下面將具體介紹方案一的算法流程。 2）一個時鐘后 hash 計算得出 hash 值。 3）再過一個時鐘，讀出 hash 表中的地址 Ref 以及 4 字節(jié)存儲空間中的 4 個字節(jié) U32Ref。若 Ref 小于當前 ip 值且不為 0，同時 U32Ref 等于 U32ip 則說明當前 4 個字節(jié)與地址在 Ref 處的 4 個字節(jié)相同，啟動匹配程序進入步驟 5，否則進入步驟 4。若 ip 移動到倒數(shù)第 5 個字節(jié)時跳到步驟 8。 6）判斷 dRef 與 dip 是否相等，若相等，控制 Ref 與 ip 加 1 后回到步驟 5；否則進入步驟7。 7）一個序列查找完成，增加 ip，控制移位寄存器，使移位寄存器中不再有前面的匹配字符，然后回到步驟 2，開始查找下一個序列。 畢業(yè)設(shè)計（論文）報告紙 13 （ 2） token、 offset、 match length 以及 literal length 計算流程 : ? token：核心控制 處于步驟 7 且步驟 7 剛結(jié)束時，若不可匹配字符小于 15，則用 token 高4 位表示不可匹配字符大小，否則 token 高 4 位為 15；若可匹配字符小于 19，則用 token低 4 位等于可匹配字符大小減 4，否則 token 高 4 位為 15。 ? literal length：核心控制處于步驟 2 到步驟 4 時，通過對控制 ip 模塊的脈沖計數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。 ? match length：核心控制處于步驟 5 到步驟 7 時，通過對控制 ip 模塊的脈沖計數(shù)，獲得可匹配字符的大小，若其小于 19 則 match length 為 0，且不輸出。 2）第一個序列完成后，依次寫入 token、 literal length、 literal、 offset、 match length。 硬件調(diào)試時序圖 如圖 所示，該圖是方案一的核心控制邏輯的硬 件調(diào)試時序圖。 state 是用于匹配查找狀態(tài)切換標志，每個時鐘加一。 畢業(yè)設(shè)計（論文）報告紙 14 壓縮速度計算 該 LZ4 壓縮核主頻是 150MHz。而找到匹配后每 2 個狀態(tài) ip 加 1，也就是 ip 每 2 個時鐘加 1。 最小壓縮速度：當全不可匹配時，由上述分析可知 ip 移動速度大約是 150MHz/s 除以 3得 50MByte/s。 方案二 硬件框圖 與方案一不同的是，方案二需要優(yōu)化硬件結(jié)構(gòu)，縮短時序，同時去掉那個 32 位 64k 地址的 RAM塊，通過返回讀取緩存中的數(shù)據(jù)然后再進行沖突判斷，這樣做的好處在于減少了 RAM資源的消耗，可以使程序消耗更少的資源。同時由于沖突的影響會導(dǎo)致程序工作時的壓縮速度極不穩(wěn)定。 算法流程 畢業(yè)設(shè)計（論文）報告紙 15 （ 1）方案二核心算法流程： 1）啟動壓縮時，通過 ip 控制，每個時鐘 ip 加一，同時控制移位寄存器移位，當 ip 等于4 時啟動 hash 計算得出 hash 值。 2）一個時鐘后繼續(xù)計算 hash 值。同時寫入當前的 ip 值以及移位寄存器輸出的 32 位數(shù)據(jù) U32ip。若 ip 大于輸入數(shù)據(jù)大小減 5 后的結(jié)果則跳到步驟 7。進入步驟 4。 5）移動 Ref 到匹配的 4 字節(jié)后一字節(jié)處，判斷 dRef 與 dip 是否相等，若相等，控制 Ref與 ip 加 1 后繼續(xù)判斷；否則進入步驟 6。 6）一個序列查找完成，增加 ip，控制移位寄存 器，使移位寄存器中不再有前面的匹配字符，然后回到步驟 2,開始查找下一個序列。 （ 2） token、 offset、 match length 以及 literal length 計算流程 ? token：核心控制處于步驟 6 且步驟 6 剛結(jié)束時，若不可匹配字符小于 15，則用 token 高4 位表示不可匹配字符大小，否則 token 高 4 位為 15；若可匹配字符小于 19，則用 token低 4 位等于可匹配字符大小減 4，否則 token 高 4 位為 15。 ? literal length：核心控制處于步驟 2 時，通過對控制 ip 模塊的控制信號時長進行計數(shù)，獲得不可匹配字符的大小，若其小于 15 則 literal length 為 0，且不輸出。 ? match length：核心控制處于步驟 5 和步驟 6 時，通過對控制 ip 模塊的控制信號時長進行計數(shù)，獲得可匹配字符的大小，若其小于 19 則 match length 為 0，且不輸出 。 2）第一個序列完成后，依次寫入 token、 literal length、 literal、 offset、 match length。 畢業(yè)設(shè)計（論文）報告紙 16 硬件調(diào)試時序圖 如圖 所示是方案二的核心控制邏輯的硬件調(diào)試時序圖。 State 是用于返回讀取匹配的 4 字節(jié)的狀態(tài)切換標志，每個 時鐘加一。 壓縮速度計算 該 LZ4 壓縮核的主頻為 140MHz。 最小壓縮速度：由于沖突數(shù)量并不可預(yù)測，所以最低速度無法通過計算獲得，只能通過估計大概數(shù)值。 最大壓縮速度：當沒有沖突時且壓縮產(chǎn)生的序列越少時速度越大，按照極限計算，只有一個序列，且無沖突，則最大速度為 140MByte/s。 方案三 硬件框圖 方案三的結(jié)構(gòu)結(jié)合了以上兩個方案，同樣需要優(yōu)化硬件結(jié)構(gòu)，縮短時序。 畢業(yè)設(shè)計（論文）報告紙 17 下圖為方案三硬件框圖： 圖 方案三硬件 圖 下面將介紹方案三算法流程。同時 hash 表以及 4 字節(jié)存儲空間寫輸入使能。同時讀出 hash 表中的地址 Ref 以及 4 字節(jié)存儲空間中的 4 個字節(jié) U32Ref。若 Ref小于當前 ip 值且不為 0，同時 U32Ref 等于 U32ip 則說明當前 4 個字節(jié)與地址在 Ref 處的 4個字節(jié)相同，啟動匹配程序進入步驟 3；否則繼續(xù)。 3）移動 Ref 到匹配的 4 字節(jié)后一字節(jié)處，判斷 dRef 與 dip 是否相等，若相等，控制 Ref與 ip 加 1 后繼續(xù)判斷；否則進入步驟 2。 4）剩余數(shù)據(jù)生成一個單獨的序列， offset 為 0，匹配長度為 0。 ? offset：核心控制處于步驟 3 開始時， offset 等于 ip 減去 Ref。若不可匹配字符的大小大于 15 時， literal length 等于不可匹配字符的大小減去 15。 （ 3）輸出控制算法流程 1）復(fù)位后開始查找匹配后第 4 個時鐘起將不可匹配字符從緩存中輸入到輸出緩存中。 3）等到后向匹配查找結(jié)束后，若匹配字符長度大于等于 19 則接在 offset 后面寫入 match length，若匹配字符長度小于 19，則不用寫 match length。 硬件調(diào)試時序圖 如圖 所示為核心控制邏輯的硬件調(diào)試時序圖。而當 literal_ip_go 為 0 時間隔一個時鐘就啟動匹配控制 ip 移動。 畢業(yè)設(shè)計（論文）報告紙 19 由硬件調(diào)試時序圖中 ip 的變化可以看出，一個序列只包含 1 個空閑時鐘。 最大壓縮速度：只要單位時間內(nèi)產(chǎn)生的序列越少，壓縮速度越快。 各方案 優(yōu)缺點分析 資源消耗比 較 由于 LZ4 核對 RAM 塊的消耗最大，所以只要 RAM 足夠其余資源也就滿足消耗。 硬件易于實現(xiàn)，每次循環(huán)完成 hash值計算、判斷。 方案二 去掉寬 32位深 64k 的 RAM 表，返回匹配處，讀取匹配的 4 個字節(jié)與當前 4 個字節(jié)進行比較查找沖突。 時序變長，最低壓縮速度無法保證。 方案三 添加一個寬 32 位深 32k 的 RAM 表存儲與hash 表中對應(yīng)的 32 位的 4字節(jié)，檢測是否匹配或沖突時可直接輸出比較，減少時序。 占用資源不算多，壓縮速度快且穩(wěn)定不受沖突的影響。 由表 可以看出，在速度與資源上，方案三的優(yōu)勢比較大，對應(yīng) 缺點可以通過更改 LZ4輸出格式來解決，具體格式見第 節(jié)。 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，當 all_end為 1 時表示可以輸出數(shù)據(jù)，數(shù)據(jù)大小為 op， 將 op 之內(nèi)的數(shù)據(jù)通過 out_dop 輸出， out_op 是其對應(yīng)的地址。 LZ4 核內(nèi)部模塊功能說明 （ 1） ip 控制模塊 畢業(yè)設(shè)計（論文）報告紙 23 圖 ip 控制模塊框圖 此模塊功能為： 對 ip 執(zhí)行加 1 和復(fù)位運算。當信號 go 為 1 時，對 ip 執(zhí)行加 1 運算。 說明： 當復(fù)位信號有效時， U32 為 0。 （ 3） Ref 控制模塊 畢業(yè)設(shè)計（論文）報告紙 24 圖 Ref 控制模塊框圖 功能： 實現(xiàn)對 Ref 的寫入、復(fù)位、以及加 1 計算。 如果 Ref_write 為 1，則 Ref 等于 Ref1； 如果 Ref_write 為 0，則 Ref 從當前數(shù)值開始執(zhí)行加 1 運算。 說明： 通過 U32ip 計算出 ash 值，再據(jù) hash 值執(zhí)行對 hash 表的寫入讀出，若當前地址與 hash表中的地址之差小于 64k 則表示 hash 表中的地址有效， 若大于 64k 則表示 hash 表中的地址無效，寫入當前地址再計算下一個數(shù)據(jù)的 hash 值重復(fù)上面的步驟。查找到匹配后再計算偏移量。 （ 5） token 計算模塊 圖 token 計算模塊框圖 功能： 對不可匹配字符進行緩存、計算不可匹配字符長度、計算 token 高 4 位大小、給出寫入控制時寫入 token 的時機。 （ 6）匹配長度計算模塊 畢業(yè)設(shè)計（論文）報告紙 26 圖 匹配長度計算模塊框圖 功能： 計算匹配長度、計算 token 后 4 位大小。通過匹配長度大小判斷 token 后 4 位的大小。 說明： 通過輸入的條件進行判斷當前寫入數(shù)據(jù) ，控制寫入狀態(tài)切換。 4）如果 match_length 不為 0，寫入 match_length。 LZ4 核性能 用 FPGA 實現(xiàn)的 LZ4 算法的單核壓縮數(shù)據(jù)速度肯定沒有 PC 的壓縮速度快，因此 FPGA的優(yōu)勢在于并行處理可以添加多個核進行同時處理，但是 FPGA 的資源有限，減少單核的資源開銷就可以實現(xiàn)更多核的并行處理，從而提高壓縮速度。 通過計算可以得出壓縮速度為： 124— 140MByte/s。 測試框架圖 原始文件通過串口調(diào)試助手從 PC 機傳