A 43.3 bit/cycle Inflate Accelerator Featuring Static-Dynamic Huffman Decoder with Multiple Checkpoints and Optimized End-Of-Block Control for Hyperscale data
Wei Zhang, Yiwei Luo, Yangyi Zhang, Jiaqi Ouyang, Guodong Wang, Xianglong Wang, Gang Shi, Lei Chen, Fengwei An · 2024
Today’s explosively growing data volumes and the high storage cost make compression crucial for the Big Data industry. Deflate is a widely used lossless compression format that incorporates the LZ77 algorithm, which replaces repeated character strings withpairs, and the Huffman algorithm, which recodes characters based on their frequency of occurrence. The decoding process for a deflate-encoded file is called inflate. The decompression speed is critical, as stored data are typically compressed once but repeatedly decompressed for use in data processing systems. Consequently, strategies have been developed to enhance the decompression speed of inflate. The main challenge in improving inflate throughput lies in the data dependencies that invalidate parallel operations in Huffman decoding. Some studies [1], [2] have modified the deflate format to eliminate these data dependencies and achieve parallelism, but this approach results in incompatibility with existing inflate implementations. A speculative Huffman decoder for the GZIP decompressor, as proposed in [3], improves parallelism, resulting in a 69% increase in throughput. However, a single index checkpoint cannot ensure the success of the speculative thread (ST), which affects inflate throughput. Additionally, the ST stops when it encounters an end-of-block (EOB) marker and only restarts after the primary thread (PT) meets an EOB, limiting the ST’s efficiency. When Huffman decoding is accelerated, the throughput of the LZ77 decoder may become the critical path. The LZ77 decoder can be parallelized using a two-pass method. Other approaches [4], [5] cyclically partition the history buffer to access multiple memory locations simultaneously.