基于FPGA的LZO實(shí)時(shí)無損壓縮的硬件設(shè)計(jì)

　　本文通過對(duì)多種壓縮算法作進(jìn)一步研究對(duì)比后發(fā)現(xiàn)，LZO壓縮算法是一種被稱為實(shí)時(shí)無損壓縮的算法，LZO壓縮算法在保證實(shí)時(shí)壓縮速率的優(yōu)點(diǎn)的同時(shí)提供適中的壓縮率。如圖1（A）給出了Linux操作系統(tǒng)下常見開源壓縮算法的壓縮速率的測(cè)試結(jié)果，LZO壓縮算法速率極快;如圖1（B）給出了Gzip壓縮算法和LZO壓縮算法的壓縮率測(cè)試結(jié)構(gòu)，從圖中可以看出，LZO壓縮算法可以提供平均約50%的壓縮率。

　　1 LZO壓縮算法基本原理分析

　　1.1 LZO壓縮算法壓縮原理

　　LZO壓縮算法采用（重復(fù)長度L，指回距離D）代替當(dāng)前已經(jīng)在歷史字符串中出現(xiàn)過的字符串，其中，重復(fù)長度是指，后出現(xiàn)的字符串與先出現(xiàn)的字符串中連續(xù)相同部分的長度;指回距離是指，先后兩個(gè)相同字符串之間相隔的距離（每個(gè)字節(jié)為一個(gè)單位）;如果沒出現(xiàn)過（定義為新字符），則首先輸出新字符的個(gè)數(shù)，再輸出新字符。例如，待處理的字符串為“ABCDEFGHABCDEFJKLM”，壓縮算法逐個(gè)處理字符，處理ABCDEFGH時(shí)沒發(fā)現(xiàn)重復(fù)字符;處理到ABCDEF時(shí)發(fā)現(xiàn)這些字符在歷史字符串中已經(jīng)出現(xiàn)過，計(jì)算重復(fù)長度為6，指回距離（當(dāng)前A離歷史A的距離）為8，則用（6，8）代替ABCDEF;處理到JKLM時(shí)沒發(fā)現(xiàn)重復(fù)字符，字符串到此處理完畢，則整個(gè)字符串被壓縮成：（08）h ABCDEFGH（6，8）（04）h JKLM，其中h表示16進(jìn)制。

　　1.2 LZO壓縮算法編碼

　　LZO壓縮后的數(shù)據(jù)需要經(jīng)過特定的格式進(jìn)行編碼，如圖2所示， LZO壓縮算法這樣做的目的有兩方面：調(diào)整LZO壓縮率，使得LZO適合壓縮重復(fù)長度短，但指回距離較長的數(shù)據(jù);使得解壓縮過程更加簡(jiǎn)單，解壓縮速度更快，且不需要額外的內(nèi)存。

　　2 LZO壓縮算法硬件設(shè)計(jì)與加速方案

　　2.1 LZO壓縮算法硬件結(jié)構(gòu)

　　如圖3（A）給出了一種LZO壓縮算法的硬件結(jié)構(gòu)，其中輸入緩存模塊：用于緩存DMA傳輸?shù)拇龎嚎s數(shù)據(jù)，為高速緩存模塊提供數(shù)據(jù)源用以進(jìn)行壓縮操作;高速緩存模塊：臨時(shí)緩存待壓縮數(shù)據(jù)，為LZSS壓縮模塊提供待壓縮數(shù)據(jù)，初始化時(shí)提前寫入一定量的數(shù)據(jù);LZSS模塊：對(duì)待壓縮數(shù)據(jù)進(jìn)行壓縮處理;字典模塊：存儲(chǔ)壓縮過程中產(chǎn)生的壓縮信息，例如歷史字符串的索引信息，這樣便可為后續(xù)數(shù)據(jù)壓縮提供歷史字符串信息;LZO編碼模塊：對(duì)LZSS壓縮后的數(shù)據(jù)按照LZO編碼格式進(jìn)行編碼，并將編碼數(shù)據(jù)組包成固定長度的數(shù)據(jù)包，方便總線通訊;輸出緩存模塊：緩存編碼后的數(shù)據(jù)，為DMA讀操作提供壓縮后的數(shù)據(jù)源;Avalon總線接口：按照Avalon總線規(guī)范對(duì)LZO壓縮算法模塊進(jìn)行封裝，為后續(xù)集成SOPC提供準(zhǔn)備。

　　2.2 LZO壓縮算法硬件加速方案

　　（1）分離雙端口RAM

　　為了加速LZO壓縮算法字符串的比對(duì)過程，本文提出如圖3（B）所示的分離雙端口RAM的結(jié)構(gòu)，圖中的多路選擇器1用于將待壓縮數(shù)據(jù)交替式寫入雙端口RAM1和雙端口RAM2之一中，多路選擇器2用于將讀取的數(shù)據(jù)交替式輸出。例如，現(xiàn)有字符ABCDEFGHIJ要存入雙端口RAM中，具體如下：ABCD通過多路選擇器1被寫入RAM1中的data1處，EFGH通過多路選擇器1被寫入RAM2中的data2處，IJ通過多路選擇1被寫入data3，此時(shí)LZO壓縮算法模塊需要讀取字符串BCDE，則在讀取RAM1中data1處的BCD的同時(shí)讀取RAM2中data2處的E，即給RAM1讀地址的同時(shí)可以給RAM2讀地址，這樣同一時(shí)刻可以讀2處地址對(duì)應(yīng)的內(nèi)容。相比于一般性雙端口RAM結(jié)構(gòu)，本結(jié)構(gòu)可以實(shí)現(xiàn)一次完成讀取操作。做進(jìn)一步擴(kuò)展可得出如下結(jié)論：若RAM的寬度為W，則讀取字符數(shù)在2W以內(nèi)時(shí)，采用分離雙端口RAM結(jié)構(gòu)可以一次完成讀取操作;則讀取字符數(shù)在2~2W以內(nèi)時(shí)，采用一般性雙端口RAM結(jié)構(gòu)可能要讀兩次。當(dāng)然，不僅RAM的寬度可以增加，RAM的個(gè)數(shù)也可以增加，當(dāng)RAM的寬度和RAM個(gè)數(shù)越大時(shí)，完成讀操作只需一次的可能性就越大。

　?。?）塊標(biāo)記

　　LZO壓縮算法在壓縮每個(gè)數(shù)據(jù)塊之前都要對(duì)字典模塊進(jìn)行初始化為0的操作，即對(duì)RAM進(jìn)行寫0操作，然而寫0操作會(huì)耗費(fèi)若干個(gè)周期。若字典模塊深度為16K，即RAM的深度為16K，當(dāng)進(jìn)行寫0操作時(shí)至少花費(fèi)16K個(gè)周期。通常解決此類問題的一種方法是采用乒乓操作的方式，即用兩個(gè)字典來交替處理。為了解決初始化帶來的時(shí)間花費(fèi)和資源消耗的問題，本文提出一種如圖3（C）所示的塊標(biāo)記字典結(jié)構(gòu)，該結(jié)構(gòu)主要包括：LZSS壓縮控制模塊，用于產(chǎn)生壓縮信息，即字符索引及字符所對(duì)應(yīng)的Hash值;flag產(chǎn)生模塊，用于產(chǎn)生0或者1兩種flag標(biāo)識(shí)，表示是當(dāng)前數(shù)據(jù)塊還是歷史數(shù)據(jù)塊;信息合并模塊，用于將字符索引和flag標(biāo)識(shí)進(jìn)行合并，然后存入字典模塊。整個(gè)結(jié)構(gòu)的工作原理可歸納如下：flag標(biāo)識(shí)0或1表示是當(dāng)前數(shù)據(jù)塊或歷史數(shù)據(jù)塊，如壓縮第一個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為0，壓縮第二個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為1，壓縮第三個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為0，壓縮第四個(gè)數(shù)據(jù)塊時(shí)標(biāo)識(shí)為1，如此進(jìn)行反復(fù);LZSS壓縮控制模塊產(chǎn)生字符索引然后與flag進(jìn)行合并共同存入通過字符計(jì)算出的Hash值對(duì)應(yīng)的地址處。例如，現(xiàn)假設(shè)已經(jīng)壓縮到第二個(gè)數(shù)據(jù)塊，則根據(jù)上面的工作原理可知，當(dāng)前的標(biāo)識(shí)應(yīng)該為1，在壓縮時(shí)取出字典中的信息并判斷第一個(gè)bit位，如果第一個(gè)bit位為0則說明該壓縮信息是歷史數(shù)據(jù)塊，壓縮信息無效;如果第一個(gè)bit位為1則說明可能是當(dāng)前數(shù)據(jù)塊（因?yàn)橐灿锌赡苁呛芫靡郧暗臄?shù)據(jù)塊），根據(jù)壓縮信息取出相應(yīng)字符進(jìn)行比對(duì)確認(rèn)。

　　綜上所述，塊標(biāo)記字典結(jié)構(gòu)具有如下特點(diǎn)：無需初始化操作，避免了初始化過程帶來的時(shí)間花費(fèi);摒棄了乒乓操作的思想，節(jié)省了乒乓操作帶來的大量資源的消耗;該結(jié)構(gòu)在片上資源緊缺的情況下是最優(yōu)的選擇。

　　（3）字典分離

　　軟件在實(shí)現(xiàn)LZO壓縮算法過程中，當(dāng)碰撞發(fā)生時(shí)，LZO壓縮算法會(huì)進(jìn)行第二次Hash操作，該次Hash操作在第一次Hash操作的基礎(chǔ)上進(jìn)行偏移。為了提升LZO壓縮算法的壓縮率，本文提出一種如圖3（D）所示的字典分離的結(jié)構(gòu)，當(dāng)Hash碰撞發(fā)生時(shí)，LZO壓縮算法進(jìn)行第二次Hash操作，但第二次Hash操作對(duì)應(yīng)的字符串索引不再存入第一個(gè)字典中，而是單獨(dú)開辟一塊RAM空間進(jìn)行存儲(chǔ)。字典分離結(jié)構(gòu)的總存儲(chǔ)空間增加了字典2的大小，這樣在壓縮文件的過程中，文件的壓縮信息量也會(huì)增加?？梢?，該結(jié)構(gòu)可以改進(jìn)LZO壓縮算法的壓縮率。

　　3 LZO壓縮系統(tǒng)集成與測(cè)試驗(yàn)證

　　3.1 LZO壓縮系統(tǒng)硬件結(jié)構(gòu)

　　如圖4（A）為LZO壓縮系統(tǒng)SOPC硬件結(jié)構(gòu)，內(nèi)層虛線表示FPGA，虛線內(nèi)的模塊有相應(yīng)的代碼或硬件電路構(gòu)成，外層虛線表示DE2開發(fā)板，開發(fā)板提供了相應(yīng)的資源。圖中：PC機(jī)通過下載線將待壓縮的數(shù)據(jù)傳送至DE2開發(fā)板上的SDRAM，數(shù)據(jù)經(jīng)壓縮后再經(jīng)下載線回傳至PC機(jī);Nios II處理器負(fù)責(zé)與用戶交互，對(duì)待壓縮數(shù)據(jù)進(jìn)行管理，控制整個(gè)SOPC的正常工作;JTAG-UART用于設(shè)計(jì)過程中的軟件和硬件調(diào)試;DMA控制器用于高速數(shù)據(jù)傳輸，它將片外SDRAM中的待壓縮數(shù)據(jù)傳送到LZO壓縮算法模塊，將LZO壓縮算法模塊中被壓縮后的數(shù)據(jù)傳送到片外SDRAM中;LZO壓縮算法模塊用于對(duì)用戶傳輸過來的數(shù)據(jù)進(jìn)行壓縮，它與片外SRAM進(jìn)行通訊;LCD控制器用于控制LCD的顯示，LCD可顯示LZO壓縮文件開始與結(jié)束，增加用戶交互的可視性，例如顯示待壓縮文件的大小，壓縮后的文件大小等;PIO控制LED指示燈的亮與滅，LED燈可用于指示LZO壓縮文件開始與結(jié)束，增加用戶交互的可視性;On-chip memory用于存儲(chǔ)系統(tǒng)啟動(dòng)時(shí)的軟硬件配置等信息;SDRAM控制器用于控制SDRAM與系統(tǒng)數(shù)據(jù)的交換;SDRAM用于存儲(chǔ)指令和數(shù)據(jù);SRAM用于存儲(chǔ)LZO壓縮算法過程中產(chǎn)生的壓縮信息，在硬件設(shè)計(jì)中扮演字典的角色，采用片外SRAM的原因是考慮到FPGA片內(nèi)資源可能不夠使用;以上所有涉及到的模塊均采用Avalon總線規(guī)范進(jìn)行數(shù)據(jù)通信，它們共同掛載到數(shù)據(jù)總線上，Avalon總線具有自身的仲裁結(jié)構(gòu)、地址分析等功能，易于用戶集成開發(fā)。

　　3.2 開發(fā)板簡(jiǎn)介

　　測(cè)試與驗(yàn)證平臺(tái)如圖4（B）所示的DE2開發(fā)板，該開發(fā)板上的核心芯片為Altera公司的Cyclone II EP2C35 FPGA。選擇該開發(fā)板作為測(cè)試平臺(tái)主要基于以下考慮：擁有足夠的片外存儲(chǔ)資源（SDRAM 8MB、SRAM 512KB）;擁有較豐富的片上邏輯資源（35K LEs）;擁有豐富的可用于調(diào)試的外設(shè)（LCD、7-segment-displays）;支持 Nios II嵌入式軟核;成本較低。

　　3.3 測(cè)試結(jié)果及對(duì)比

　　針對(duì)LZO壓縮算法模塊和集成后的系統(tǒng)進(jìn)行板級(jí)測(cè)試，一方面驗(yàn)證算法模塊及集成后的系統(tǒng)的功能正確性，另一方面測(cè)試分析算法模塊及集成后系統(tǒng)的性能。測(cè)試內(nèi)容包括：數(shù)據(jù)壓縮率（壓縮后的文件大小/壓縮前的文件大?。?，數(shù)據(jù)壓縮速率（單個(gè)周期內(nèi)處理的字節(jié)數(shù)）。

　　通過圖5（A）可知，壓縮率提升最大的是1.pdf文件，提升最小的是7.mp3文件（音頻文件已經(jīng)采用音頻壓縮算法壓縮過了），除去最大值和最小值后取平均值，則壓縮率提升為1.37%;通過圖5（B）不難發(fā)現(xiàn)，壓縮速率提升最快的為2.txt文件，提升最慢的為10.dll文件，除去最大值和最小值后取平均值，則壓縮速率提升為4.81倍。