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

来源:本站
导读:目前正在解读《基于FPGA的LZO实时无损压缩的硬件设计》的相关信息,《基于FPGA的LZO实时无损压缩的硬件设计》是由用户自行发布的知识型内容!下面请观看由(电工技术网 - www.9ddd.net)用户发布《基于FPGA的LZO实时无损压缩的硬件设计》的详细说明。
简介:本文通过对多种压缩算法作进一步研究对比后发现,LZO压缩算法是一种被称为实时无损压缩的算法,LZO压缩算法在保证实时压缩速率的优点的同时提供适中的压缩率。如图1(A)给出了Linux操作系统下常见开源压缩算法的压缩速率的测试结果,LZO压缩算法速率极快;如图1(B)给出了Gzip压缩算法和LZO压缩算法的压缩率测试结构,从图中可以看出,LZO压缩算法可以提供平均约50%的压缩率。

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

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

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适合压缩重复长度短,但指回距离较长的数据;使得解压缩过程更加简单,解压缩速度更快,且不需要额外的内存。

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

2 LZO压缩算法硬件设计与加速方案

2.1 LZO压缩算法硬件结构

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

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

2.2LZO压缩算法硬件加速方案

(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压缩算法的压缩率。

3LZO压缩系统集成与测试验证

3.1LZO压缩系统硬件结构

如图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总线具有自身的仲裁结构、地址分析等功能,易于用户集成开发。

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

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

3.2 开发板简介

测试与验证平台如图4(B)所示的DE2开发板,该开发板上的核心芯片为Altera公司的Cyclone II EP2C35FPGA。选择该开发板作为测试平台主要基于以下考虑:拥有足够的片外存储资源(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的LZO实时无损压缩的硬件设计

提醒:《基于FPGA的LZO实时无损压缩的硬件设计》最后刷新时间 2024-03-14 00:56:07,本站为公益型个人网站,仅供个人学习和记录信息,不进行任何商业性质的盈利。如果内容、图片资源失效或内容涉及侵权,请反馈至,我们会及时处理。本站只保证内容的可读性,无法保证真实性,《基于FPGA的LZO实时无损压缩的硬件设计》该内容的真实性请自行鉴别。