2. 东南大学 成贤学院, 南京 210018
2. Chengxian College, Southeast University, Nanjing 210018, China
随着信息和通信技术的迅猛发展,庞大的数据必须进行有效的压缩,才能减少数据交换量,最大限度地利用有限的数据传输带宽.无损压缩要求对压缩的数据进行重构(解压缩)后原来的数据完全相同,具有高保真性的无损压缩被大量应用到服务器和工作站等大数据处理系统中,IBM和百度等公司均对其做过积极研究.LZMA压缩算法是LZ77压缩算法的一个改进版本,由 Pavlov于1998年发明,目前在7zip压缩算法中被作为默认的压缩算法[1, 2].
虽然LZMA能够提供较高的压缩率,但处理过程中需要大量的随机访问存储器(RAM,Random Access Memory),并且会耗费较多CPU资源.对海量数据进行处理时,长时间占用大量CPU资源,使得在执行LZMA数据压缩的同时进行其他操作变成了难题.
目前一个高性能FPGA中包含了上千个独立的双端口RAM块,一个或多个的内嵌处理器以及海量的可配置资源.尽管这些资源相比CPU的工作频率要慢很多,但却可以提供高性能的并行运算,从而使得加速LZMA压缩算法成为了可能.虽然国内外已有众多的关于数据无损压缩加速的电路实现方案,但却不能在支持高压缩带宽的同时,提供很好的压缩比.本文主要针对LZMA算法的FPGA硬件实现进行了研究,在高速压缩的同时提供更好的压缩比例. 1 LZMA算法
LZMA压缩算法的结构与Deflate算法极其相似[3, 4],只是将其中的Huffman编码替代成了区间编码,值得注意的是区间编码是一种基于整数运算的概率编码,其压缩效果十分接近数据的熵值.在LZMA算法中,首先由LZ77压缩算法在搜索缓存(search buffer)中寻找与前向缓存(look-ahead buffer)中匹配最长的字符串,然后输出一个关于(DIS,LEN,LIT)的标识.其中,DIS代表了look-ahead buffer中与search buffer中相匹配的两组数据首个字节之间的距离,最大的值取决于search buffer的大小;LEN代表了最大的匹配长度,通常是一个较小的数值;LIT代表下一个字符,通常是一个ASCII编码值[5, 6, 7].当LZ77压缩算法完成对数据的第1次压缩后,区间编码根据不同的输出数据流采用不同的压缩策略,以便解压的时候识别[8].
如图 1所示,是一台核心为Core i3-2100 CPU@3.1 GHz,内存为4 GB的工作站全负荷运算时,LZMA-SDK_4.26[9]的数据吞吐测试结果曲线图,其平均的压缩速率仅为10~20 Mb/s.
在LZMA压缩中,数据流都是比特形式的,数据流被分成不同种类的数据包,经过区间编码后变成限定区间内的某一个数据后输出.如表 1所示,在LZMA算法中共有7种数据类型,为了将资源消耗控制在可接受的范围内,本文限定LZMA压缩的数据格式仅为前2种.
数据包(bit) | 包名称 | 描述 |
0+ASCII | Lit | 新字符 |
1+0+len+dis | Match | 重复字串 |
1+1+0+0 | ShortRep | 与之前出现的字符一样 |
1+1+0+1+len | LongRep[0] | DIS与上一次一样 |
1+1+1+0+len | LongRep[1] | DIS与倒数第2次一样 |
1+1+1+1+0+len | LongRep[2] | DIS与倒数第3次一样 |
1+1+1+1+1+len | LongRep[3] | DIS与倒数第4次一样 |
根据LZMA的压缩流程,本文将实现电路划分为3个部分:LZ77压缩控制器、区间编码控制器和数据读出控制器.
如图 2所示,LZ77压缩控制器将写入的数据进行第1次压缩,并将压缩后的编码数据流向后传输;区间编码控制器按照既定压缩编码进一步压缩数据;数据读出控制器将区间编码控制器输出的数据拼接成更合理的数据格式,以适应外部高速总线,并在数据读出控制器中添加了数据缓冲存储,保证了外部高速总线的高利用率.
2.1 LZ77压缩控制器如图 3所示,LZ77压缩控制器包括:数据读入缓存、Hash表存储模块和LZ77压缩算法控制模块.
数据读入缓存:采取了乒乓RAM的方式对需要压缩的数据进行读取.当一个数据块中的数据正在被压缩时,通过握手信号通知外部总线,向另一个数据块存储区域中写入下一个将压缩的数据信息,通过交替的向数据读入缓存中写入数据,保证LZ77压缩算法控制模块不需要等待数据,实现不间断地对数据进行处理.Hash表存储模块:存储已编码字符的信息.一系列的测试结果[10]表明在搜索深度为4时,LZ77压缩算法的效率已经达到极限范围.因此,设计中没有采用两个RAM实现多级链表(以往的目的是减少资源),而是使用4个Read-First模式的RAM级联,这样可以在同一个读周期内读取多个Hash值,减少多次搜索对RAM进行操作的时间,从而达到加速的目的;并且可以根据搜索深度的配置使能相关的RAM.LZ77压缩算法控制模块:产生上述两个模块的控制信号,对数据流按照LZ77算法进行压缩.
[1] | Salomon D. Data compression:the complete reference[M].4th ed.London:Springer,2007:241-246. |
[2] | Pavlov I. 7z format[EB/OL].US:Igor Pavlov,2013[2014-03-10].http://www.7-zip.org/7z.html. |
Click to display the text | |
[3] | Klausman. Gzip,Bzip2 and LZMA compared[EB/OL].US:CEST,2008[2014-03-10].http://blog.i-no.de/archives/2008/05/08/. |
Click to display the text | |
[4] | Rigler S, Bishop W,Kennings A.FPGA-based lossless data compression using Huffman and LZ77 algorithms[C]//Electrical and Computer Engineering.Canada:CCECE,2007:1235-1238. |
Click to display the text | |
[5] | Ziv J,Lempel A. Universal algorithm for sequential data compression[J].IEEE Transactions on Information Theory,1977,IT-23(3):337-343. |
Click to display the text | |
[6] | Ranganathan N, Henriques S.High-speed VLSI designs for Lempel-Ziv-based data compression[J].IEEE Transactions on Circuits and Systems II:Analog and Digital Signal Processing,1993,40(2):96-106. |
Click to display the text | |
[7] | Shcherbakov I, Weis C,Wehn N.A high-performance FPGA-based implementation of the LZSS compression algorithm[C]//Data Compression Conference(DCC).Washington,DC:IEEE,2012:449-453. |
Click to display the text | |
[8] | Martin G N N. Range encoding:an algorithm for removing redundancy from a digitized message[C]//IERE Conference Proceedings.London:IERE,1979,43:187-197. |
[9] | Pavlov I. LZMA SDK[EB/OL].US:Igor Pavlov,2013[2014-03-10].http://www.7zip.org/sdk.html. |
Click to display the text | |
[10] | 孙圣. 一种基于FPGA的Defalte压缩算法研究与实现[D].桂林:桂林理工大学,2010. Sun S.A research and implementation of Deflate compression algorithm on FPGA[D].Guilin:Guilin University of Technology,2010(in Chinese). |
[11] | Shcherbakov I, Weis C,When N.A parallel adaptive range coding compressor:algorithm,FPGA prototype,evaluation[C]//Data Compression Conference(DCC).Piscataway,NJ:IEEE,2012,119-128. |
Click to display the text | |
[12] | Xilinx. Xilinx FPGA[EB/OL].US:Xilinx,2011[2014-03-10].http://www.xilinx.com/products/silicon-devices/fpga/index.htm. |
Click to display the text | |
[13] | Xilinx. ML605 Hardware User Guide[EB/OL].US:Xilinx,2011[2014-03-10].http://www.xilinx.com/support/documentation/boards_and_kits/ug534.pdf |
Click to display the text | |
[14] | Leavline E J, Singh D A A G.Hardware implementation of LZMA data compression algorithm[J].International Journal of Applied Information Systems (IJAIS),2013,5(4):449-453. |
Click to display the text | |
[15] | Calgary Corpus. Calgary corpus database[EB/OL].US:Calgary Corpus,1987[2014-03-10].http://en.wikipedia.org/wiki/Calgary_Corpus. |
Click to display the text |