基于FPGA的LZO实时无损压缩的硬件设计

出处:EEPW 发布于:2015-04-28 14:30:55

  本文通过对多种压缩算法作进一步研究对比后发现,LZO压缩算法是一种被称为实时无损压缩的算法,LZO压缩算法在保证实时压缩速率的优点的同时提供适中的压缩率。如图1(A)给出了Linux操作系统下常见开源压缩算法的压缩速率的测试结果,LZO压缩算法速率极快;如图1(B)给出了Gzip压缩算法和LZO压缩算法的压缩率测试结构,从图中可以看出,LZO压缩算法可以提供平均约50%的压缩率。


  1 LZO压缩算法基本原理分析
  1.1 LZO压缩算法压缩原理
  LZO压缩算法采用(重复长度L,指回距离D)代替当前已经在历史字符串中出现过的字符串,其中,重复长度是指,后出现的字符串与先出现的字符串中连续相同部分的长度;指回距离是指,先后两个相同字符串之间相隔的距离(每个字节为一个单位);如果没出现过(定义为新字符),则首先输出新字符的个数,再输出新字符。例如,待处理的字符串为“ABCDEFGHABCDEFJKLM”,压缩算法逐个处理字符,处理ABCDEFGH时没发现重复字符;处理到ABCDEF时发现这些字符在历史字符串中已经出现过,计算重复长度为6,指回距离(当前A离历史A的距离)为8,则用(6,8)代替ABCDEF;处理到JKLM时没发现重复字符,字符串到此处理完毕,则整个字符串被压缩成:(08)h ABCDEFGH(6,8)(04)h JKLM,其中h表示16进制。
  1.2 LZO压缩算法编码
  LZO压缩后的数据需要经过特定的格式进行编码,如图2所示, LZO压缩算法这样做的目的有两方面:调整LZO压缩率,使得LZO适合压缩重复长度短,但指回距离较长的数据;使得解压缩过程更加简单,解压缩速度更快,且不需要额外的内存


  2 LZO压缩算法硬件设计与加速方案
  2.1 LZO压缩算法硬件结构
  如图3(A)给出了一种LZO压缩算法的硬件结构,其中输入缓存模块:用于缓存DMA传输的待压缩数据,为高速缓存模块提供数据源用以进行压缩操作;高速缓存模块:临时缓存待压缩数据,为LZSS压缩模块提供待压缩数据,初始化时提前写入一定量的数据;LZSS模块:对待压缩数据进行压缩处理;字典模块:存储压缩过程中产生的压缩信息,例如历史字符串的索引信息,这样便可为后续数据压缩提供历史字符串信息;LZO编码模块:对LZSS压缩后的数据按照LZO编码格式进行编码,并将编码数据组包成固定长度的数据包,方便总线通讯;输出缓存模块:缓存编码后的数据,为DMA读操作提供压缩后的数据源;Avalon总线接口:按照Avalon总线规范对LZO压缩算法模块进行封装,为后续集成SOPC提供准备。


  2.2 LZO压缩算法硬件加速方案
  (1)分离双端口RAM
  为了加速LZO压缩算法字符串的比对过程,本文提出如图3(B)所示的分离双端口RAM的结构,图中的多路选择器1用于将待压缩数据交替式写入双端口RAM1和双端口RAM2之一中,多路选择器2用于将读取的数据交替式输出。例如,现有字符ABCDEFGHIJ要存入双端口RAM中,具体如下:ABCD通过多路选择器1被写入RAM1中的data1处,EFGH通过多路选择器1被写入RAM2中的data2处,IJ通过多路选择1被写入data3,此时LZO压缩算法模块需要读取字符串BCDE,则在读取RAM1中data1处的BCD的同时读取RAM2中data2处的E,即给RAM1读地址的同时可以给RAM2读地址,这样同一时刻可以读2处地址对应的内容。相比于一般性双端口RAM结构,本结构可以实现完成读取操作。做进一步扩展可得出如下结论:若RAM的宽度为W,则读取字符数在2W以内时,采用分离双端口RAM结构可以完成读取操作;则读取字符数在2~2W以内时,采用一般性双端口RAM结构可能要读两次。当然,不仅RAM的宽度可以增加,RAM的个数也可以增加,当RAM的宽度和RAM个数越大时,完成读操作只需的可能性就越大。
  (2)块标记
  LZO压缩算法在压缩每个数据块之前都要对字典模块进行初始化为0的操作,即对RAM进行写0操作,然而写0操作会耗费若干个周期。若字典模块深度为16K,即RAM的深度为16K,当进行写0操作时至少花费16K个周期。通常解决此类问题的一种方法是采用乒乓操作的方式,即用两个字典来交替处理。为了解决初始化带来的时间花费和资源消耗的问题,本文提出一种如图3(C)所示的块标记字典结构,该结构主要包括:LZSS压缩控制模块,用于产生压缩信息,即字符索引及字符所对应的Hash值;flag产生模块,用于产生0或者1两种flag标识,表示是当前数据块还是历史数据块;信息合并模块,用于将字符索引和flag标识进行合并,然后存入字典模块。整个结构的工作原理可归纳如下:flag标识0或1表示是当前数据块或历史数据块,如压缩个数据块时标识为0,压缩第二个数据块时标识为1,压缩第三个数据块时标识为0,压缩第四个数据块时标识为1,如此进行反复;LZSS压缩控制模块产生字符索引然后与flag进行合并共同存入通过字符计算出的Hash值对应的地址处。例如,现假设已经压缩到第二个数据块,则根据上面的工作原理可知,当前的标识应该为1,在压缩时取出字典中的信息并判断个bit位,如果个bit位为0则说明该压缩信息是历史数据块,压缩信息无效;如果个bit位为1则说明可能是当前数据块(因为也有可能是很久以前的数据块),根据压缩信息取出相应字符进行比对确认。
  综上所述,块标记字典结构具有如下特点:无需初始化操作,避免了初始化过程带来的时间花费;摒弃了乒乓操作的思想,节省了乒乓操作带来的大量资源的消耗;该结构在片上资源紧缺的情况下是的选择。
  (3)字典分离
  软件在实现LZO压缩算法过程中,当碰撞发生时,LZO压缩算法会进行第二次Hash操作,该次Hash操作在次Hash操作的基础上进行偏移。为了提升LZO压缩算法的压缩率,本文提出一种如图3(D)所示的字典分离的结构,当Hash碰撞发生时,LZO压缩算法进行第二次Hash操作,但第二次Hash操作对应的字符串索引不再存入个字典中,而是单独开辟一块RAM空间进行存储。字典分离结构的总存储空间增加了字典2的大小,这样在压缩文件的过程中,文件的压缩信息量也会增加。可见,该结构可以改进LZO压缩算法的压缩率。
  3 LZO压缩系统集成与测试验证
  3.1 LZO压缩系统硬件结构
  如图4(A)为LZO压缩系统SOPC硬件结构,内层虚线表示FPGA,虚线内的模块有相应的代码或硬件电路构成,外层虚线表示DE2开发板,开发板提供了相应的资源。图中:PC机通过线将待压缩的数据传送至DE2开发板上的SDRAM,数据经压缩后再经线回传至PC机;Nios II处理器负责与用户交互,对待压缩数据进行管理,控制整个SOPC的正常工作;JTAG-UART用于设计过程中的软件和硬件调试;DMA控制器用于高速数据传输,它将片外SDRAM中的待压缩数据传送到LZO压缩算法模块,将LZO压缩算法模块中被压缩后的数据传送到片外SDRAM中;LZO压缩算法模块用于对用户传输过来的数据进行压缩,它与片外SRAM进行通讯;LCD控制器用于控制LCD的显示,LCD可显示LZO压缩文件开始与结束,增加用户交互的可视性,例如显示待压缩文件的大小,压缩后的文件大小等;PIO控制LED指示灯的亮与灭,LED灯可用于指示LZO压缩文件开始与结束,增加用户交互的可视性;On-chip memory用于存储系统启动时的软硬件配置等信息;SDRAM控制器用于控制SDRAM与系统数据的交换;SDRAM用于存储指令和数据;SRAM用于存储LZO压缩算法过程中产生的压缩信息,在硬件设计中扮演字典的角色,采用片外SRAM的原因是考虑到FPGA片内资源可能不够使用;以上所有涉及到的模块均采用Avalon总线规范进行数据通信,它们共同挂载到数据总线上,Avalon总线具有自身的仲裁结构、地址分析等功能,易于用户集成开发。


  3.2 开发板简介
  测试与验证平台如图4(B)所示的DE2开发板,该开发板上的芯片为Altera公司的Cyclone II EP2C35 FPGA。选择该开发板作为测试平台主要基于以下考虑:拥有足够的片外存储资源(SDRAM 8MB、SRAM 512KB);拥有较丰富的片上逻辑资源(35K LEs);拥有丰富的可用于调试的外设(LCD、7-segment-displays);支持 Nios II嵌入式软核;成本较低。
  3.3 测试结果及对比
  针对LZO压缩算法模块和集成后的系统进行板级测试,一方面验证算法模块及集成后的系统的功能正确性,另一方面测试分析算法模块及集成后系统的性能。测试内容包括:数据压缩率(压缩后的文件大小/压缩前的文件大小),数据压缩速率(单个周期内处理的字节数)。
  通过图5(A)可知,压缩率提升的是1.pdf文件,提升的是7.mp3文件(音频文件已经采用音频压缩算法压缩过了),除去值和值后取平均值,则压缩率提升为1.37%;通过图5(B)不难发现,压缩速率提升快的为2.txt文件,提升慢的为10.dll文件,除去值和值后取平均值,则压缩速率提升为4.81倍。

关键词:FPGA

版权与免责声明

凡本网注明“出处:维库电子市场网”的所有作品,版权均属于维库电子市场网,转载请必须注明维库电子市场网,https://www.dzsc.com,违反者本网将追究相关法律责任。

本网转载并注明自其它出处的作品,目的在于传递更多信息,并不代表本网赞同其观点或证实其内容的真实性,不承担此类作品侵权行为的直接责任及连带责任。其他媒体、网站或个人从本网转载时,必须保留本网注明的作品出处,并自负版权等法律责任。

如涉及作品内容、版权等问题,请在作品发表之日起一周内与本网联系,否则视为放弃相关权利。

上传BOM文件: BOM文件
*公司名:
*联系人:
*手机号码:
QQ:
应用领域:

有效期:
OEM清单文件: OEM清单文件
*公司名:
*联系人:
*手机号码:
QQ:
有效期:

扫码下载APP,
一键连接广大的电子世界。

在线人工客服

买家服务:
卖家服务:

0571-85317607

客服在线时间周一至周五
9:00-17:30

关注官方微信号,
第一时间获取资讯。

建议反馈

联系人:

联系方式:

按住滑块,拖拽到最右边
>>
感谢您向阿库提出的宝贵意见,您的参与是维库提升服务的动力!意见一经采纳,将有感恩红包奉上哦!