A General SIMD-Based Approach to Accelerating Compression Algorithms
A General SIMD-Based Approach to Accelerating Compression Algorithms
复制标题
一种基于 SIMD 的通用加速压缩算法的方法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ji
中科院分区：
文献类型：
--
作者：
Wayne Xin Zhao;Xudong Zhang;D. Lemire;Dongdong Shan;Jian;Hongfei Yan;Ji
压缩算法对于面向数据的任务非常重要，尤其是在“大数据”时代。配备强大 SIMD 指令集的现代处理器为我们提供了实现更好压缩性能的机会。先前的研究表明，基于 SIMD 的优化可以成倍提高解码速度。根据这些开创性的研究，我们提出了一种加速压缩算法的通用方法。通过实例化该方法，我们开发了几种新颖的整数压缩算法，称为 Group-Simple、Group-Scheme、Group-AFOR 和 Group-PFD，并实现了它们相应的矢量化版本。我们在两个公共 TREC 数据集、一个维基百科数据集和一个 Twitter 数据集上评估了所提出的算法。凭借具有竞争力的压缩比和编码速度，我们基于 SIMD 的算法在解码速度方面优于最先进的非矢量化算法。
Compression algorithms are important for data-oriented tasks, especially in the era of “Big Data.” Modern processors equipped with powerful SIMD instruction sets provide us with an opportunity for achieving better compression performance. Previous research has shown that SIMD-based optimizations can multiply decoding speeds. Following these pioneering studies, we propose a general approach to accelerate compression algorithms. By instantiating the approach, we have developed several novel integer compression algorithms, called Group-Simple, Group-Scheme, Group-AFOR, and Group-PFD, and implemented their corresponding vectorized versions. We evaluate the proposed algorithms on two public TREC datasets, a Wikipedia dataset, and a Twitter dataset. With competitive compression ratios and encoding speeds, our SIMD-based algorithms outperform state-of-the-art nonvectorized algorithms with respect to decoding speeds.