论文部分内容阅读
FPGA技术已经取得了巨大进步,FPGA芯片在容量和速度上都达到了较高的水平,现在已经有许多学者研究如何使用FPGA完成对应用程序的加速。Deflate算法是无专利保护的可以自由使用的无损压缩算法,一方面用历史数据的指针来代替输入数据,另一方面通过哈夫曼编码对替换后的数据再次压缩。Deflate压缩由Deflate编码和哈夫曼编码两部分组成。哈夫曼编码是经典的信息编码算法之一,可以应用到各种领域中,目前已经有许多的研究哈夫曼编码的硬件实现。而Deflate编码方面,虽然也存在许多研究,但是字典窗口大小都比较小,这极大地影响了硬件实现的压缩性能。
本文对FPGA及压缩算法做简要介绍,对Deflate的原理及性能进行分析。在分析的基础上,采用脉动阵列方法,在芯片110T FPGA上实现Deflate压缩算法的硬件加速,主要工作如下:
1、本文研究了不同的分块压缩、以及字典采用的窗口大小对编码性能的影响。研究发现,为了进一步发挥硬件的并行性,硬件系统可以同时实现多路编码模块,对同一个文件进行分块压缩或同时压缩不同的文件。其中,前者可以加速单个文件的压缩过程,后者可以提高系统的整体吞吐率。在使用分块压缩时,本块无法使用其它块的历史信息,所以当字典窗口大小小于32K的时,压缩效果降低严重。因此本文提出一种基于FPGA的窗口大小为32K的Deflate压缩算法的硬件系统设计。
2、本文研究了不同的最大匹配长度对编码性能的影响。Deflate编码阶段是整个压缩过程的核心部分,研究发现最大匹配长度在16时,能较好地完成对测试集的压缩。因此为了节约开销,在不过分损失性能的前提下,本文最终确定采用最大匹配长度为16的硬件实现方案。
3、由于Deflate压缩算法是一种结合哈希表的压缩算法,会产生一定程度的哈希表膨胀的问题。为了解决该问题,提出一种了基于改进后的循环存储的哈希表实现方法,避免了窗口的移动。该方法能在不移动窗口内数据的前提下,实现对哈希表的截断。
通过对上述设计进行的性能分析可以得出,该设计具备兼顾单个文件的压缩速度和系统整体吞吐率等优势。同时,该方案所实现的系统在使用110T FPGA芯片时可以工作在200MHz,相对于3GHz的Xeon处理器有2.4倍的加速比。