Massively Parallel Huffman Decoding on GPUs
Massively Parallel Huffman Decoding on GPUs
复制标题
GPU 上的大规模并行霍夫曼解码
DOI：
10.1145/3225058.3225076
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
B. Schmidt
中科院分区：
文献类型：
--
作者：
André Weißenberger;B. Schmidt
数据压缩是广泛应用程序中的基本构件。压缩除了用于节省硬盘上的宝贵存储空间外，还可以用来增加通过最先进的文件系统实现的连接存储的有效带宽。在可预见的未来，动态压缩和解压缩对于数据密集型应用的处理将变得至关重要，例如流深度学习任务或下一代测序流水线，这确立了快速并行实施的需求。霍夫曼编码是许多压缩方法的组成部分。然而，由于固有的数据相关性(即，解码符号的位置取决于其前身)，高效地并行实现霍夫曼解压是困难的。本文利用哈夫曼码的自同步特性，提出了第一个与霍夫曼原方法兼容的大规模并行译码实现方案。我们在三种不同的支持CUDA的图形处理器(Titan V、Titan XP、GTX 1080)上进行的性能评估显示，与基于最先进CPU的ZStandard Huffman解码器相比，性能提升了一个数量级以上。我们的实施可在https://github.com/weissenberger/gpuhd.上获得
Data compression is a fundamental building block in a wide range of applications. Besides its intended purpose to save valuable storage on hard disks, compression can be utilized to increase the effective bandwidth to attached storage as realized by state-of-the-art file systems. In the foreseeing future, on-the-fly compression and decompression will gain utmost importance for the processing of data-intensive applications such as streamed Deep Learning tasks or Next Generation Sequencing pipelines, which establishes the need for fast parallel implementations. Huffman coding is an integral part of a number of compression methods. However, efficient parallel implementation of Huffman decompression is difficult due to inherent data dependencies (i.e. the location of a decoded symbol depends on its predecessors). In this paper, we present the first massively parallel decoder implementation that is compatible with Huffman's original method by taking advantage of the self-synchronization property of Huffman codes. Our performance evaluation on three different CUDA-enabled GPUs (TITAN V, TITAN XP, GTX 1080) demonstrates speedups of over one order-of-magnitude compared to the state-of-art CPU-based Zstandard Huffman decoder. Our implementation is available at https://github.com/weissenberger/gpuhd.