Data Dependency Reduction for High-Performance FPGA Implementation of DEFLATE Compression Algorithm

Abstract

The rapid development of modern information technology has resulted in a sharp increase in the rate of data growth. This results in a lack of storage space and network bandwidth. Compression technology is typically implemented to mitigate the increasing demand for storage and the transmission cost of data. However, data compression may impose a significant computational burden on the CPU, which results in a degradation of system performance. To solve this problem, a hardware offloading technique can be used. Hardware offloading not only reduces the computational load imposed on the CPU but also improves the performance of the compression algorithm by exploiting hardware parallelism. However, data-hazards associated with the compression algorithm hinders achieving the achievement of a high degree of parallelism. DEFLATE is a widely used lossless compression scheme. Many studies have attempted to eliminate the data dependencies associated with compression algorithms. Unfortunately, existing studies do not address data dependency elimination in Huffman encoding. Our work aims to parallelize Huffman encoding by solving the data-hazard problem in the algorithm. To address the data dependency that exists in the Huffman encoding algorithm, a new data representation for the intermediate data generated during data compression is proposed. The effectiveness of the proposed scheme was evaluated via the implementation of an architecture which applied the approach in the field-programmable gate array (FPGA) platform. Experimental results show that the proposed scheme can increase the throughput of the compressor by up to 14.4%.