Revisiting Huffman Coding: Toward Extreme Performance on Modern GPU Architectures
Revisiting Huffman Coding: Toward Extreme Performance on Modern GPU Architectures
复制标题
DOI：
10.1109/ipdps49936.2021.00097
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Jiannan Tian;Cody Rivera;S. Di;Jieyang Chen;Xin Liang;Dingwen Tao;F. Cappello
中科院分区：
文献类型：
--
作者：
Jiannan Tian;Cody Rivera;S. Di;Jieyang Chen;Xin Liang;Dingwen Tao;F. Cappello
当今的高性能计算（HPC）应用正在产生大量的数据，这些数据在执行期间高效地存储和传输是具有挑战性的，使得数据压缩正在成为减轻存储负担和数据移动成本的关键技术。霍夫曼编码可以说是信息理论中最有效的熵编码算法，因此它可以被发现是许多现代压缩算法（如DEFLATE）的基本步骤。另一方面，如今的HPC应用越来越依赖超级计算机上的GPU等加速器，而霍夫曼编码在GPU上的吞吐量较低，导致整个数据处理出现明显瓶颈。在本文中，我们提出并实现了一个高效的霍夫曼编码方法的基础上现代GPU架构，解决了两个关键的挑战：（1）如何并行化整个霍夫曼编码算法，包括码书的建设，以及（2）如何充分利用现代GPU架构的高内存带宽的特点。具体贡献有四个方面。(1)我们开发了一个有效的并行码本的GPU上的建设，有效地扩展与输入符号的数量。(2)我们提出了一种新的减少基于编码方案，可以有效地合并的码字在GPU上。(3)我们通过利用最先进的CUDA API（如Cooperative Groups）来优化GPU的整体性能。(4)我们评估我们的霍夫曼编码器彻底使用六个现实世界的应用程序数据集在两个先进的GPU和比较与我们实现的多线程霍夫曼编码器。实验结果表明，与最先进的GPU霍夫曼编码器相比，我们的解决方案在NVIDIA RTX 5000和V100上的编码吞吐量分别提高了5.0倍和6.8倍，在两个28核Xeon Platinum 8280 CPU上的多线程编码器上提高了3.3倍。
Today’s high-performance computing (HPC) applications are producing vast volumes of data, which are challenging to store and transfer efficiently during the execution, such that data compression is becoming a critical technique to mitigate the storage burden and data movement cost. Huffman coding is arguably the most efficient Entropy coding algorithm in information theory, such that it could be found as a fundamental step in many modern compression algorithms such as DEFLATE. On the other hand, today’s HPC applications are more and more relying on the accelerators such as GPU on supercomputers, while Huffman encoding suffers from low throughput on GPUs, resulting in a significant bottleneck in the entire data processing. In this paper, we propose and implement an efficient Huffman encoding approach based on modern GPU architectures, which addresses two key challenges: (1) how to parallelize the entire Huffman encoding algorithm, including codebook construction, and (2) how to fully utilize the high memory-bandwidth feature of modern GPU architectures. The detailed contribution is fourfold. (1) We develop an efficient parallel codebook construction on GPUs that scales effectively with the number of input symbols. (2) We propose a novel reduction based encoding scheme that can efficiently merge the codewords on GPUs. (3) We optimize the overall GPU performance by leveraging the state-of-the-art CUDA APIs such as Cooperative Groups. (4) We evaluate our Huffman encoder thoroughly using six real-world application datasets on two advanced GPUs and compare with our implemented multithreaded Huffman encoder. Experiments show that our solution can improve the encoding throughput by up to 5.0× and 6.8× on NVIDIA RTX 5000 and V100, respectively, over the state-of-the-art GPU Huffman encoder, and by up to 3.3× over the multithread encoder on two 28-core Xeon Platinum 8280 CPUs.