论文部分内容阅读
随着互联网的快速发展,数据呈现指数级增长,有限的网络带宽和匮乏的存储资源成为数据处理的瓶颈。数据压缩是在不丢失有效信息的前提下,缩减数据量以减少存储空间、提高数据传输和处理效率的技术方法。然而,现有文本压缩算法多采用软件架构实现,并顺序执行于中央控制单元(Central Processing Unit,CPU),未考虑压缩算法的功耗和并行化。FPGA作为一种逻辑性强、速度高、功耗小以及灵活性强的高性能硬件平台,为压缩算法提供了新的运行环境,减少其对计算机资源的依赖,拓宽压缩算法的应用范围。本文重点讨论部分匹配预测模型d方法(Prediction by Partial Matching method d,PPMd)在FPGA平台上的实现。PPMd算法通过建立上下文统计模型,记录已压缩数据流4阶上下文字符信息和频度信息,根据存储信息预测待压缩数据流中出现各个字符的概率,最后将预测概率值运用区间编码器编码。算法实现的上下文索引树更新过程过于复杂,占用内存空间大,不利于并行,而FPGA平台适合并行度高的算法运行。因此需要调整算法架构以适应并行化,提高算法在FPGA平台上的执行效率。本文主要从查询和更新上下文索引树两个方面做了并行架构设计。各阶层查询操作不存在串行执行的联系,在FPGA内部实现5个阶层并行查询;上下文更新操作包括节点信息的更新和后继字符信息的更新,将各阶层更新操作分离,独立执行,实现部分阶层更新操作并行执行;修改逃逸字符概率预测模块,将逃逸字符概率预测和更新过程提前,根据匹配结果回退更新操作的机制,降低了逃逸字符概率预测模块的时钟延迟;增加字符对应节点已建立的标志位,减少读写DDR的次数;最后修改了上下文索引树的存储结构,将字符和字符的频度信息与指向下一阶层节点的指针信息分离存储,每次字符匹配查询时,读写DDR的数据量减少为原来一半。本设计最终实现了完整的压缩算法IP核,包括输入输出模块、预测更新模块、编码模块以及主控制模块,各个模块之间实现了较高的并行度。本文在Atlys Spartan-6 FPGA平台上实现的压缩算法单核吞吐率可以达到23Mb/s。将PPMd压缩算法移植到FPGA平台之上,可以减少算法对CPU等资源的过多依赖,从而拓宽算法的工程应用范围,增强压缩算法的实用性。