A High-Throughput Hardware Accelerator for Lempel-Ziv 4 Compression Algorithm

LZ4 is a dictionary-based compression algorithm[13], which was initially conceived as a distinct compressed data format. Compressed data files are composed of LZ4 sequences, which include a token, literal length, literals, offset, and match length, as depicted in Fig. 1.

LZ4 achieves data compression by leveraging statistical redundancy in data patterns and employing a mechanism to eliminate repeated literals. It identifies recurring data strings from previous data and substitutes them with an offset-length pair, utilizing a dictionary to determine the offset of previous literals and their match length.

A typical hardware parallel implementation of the LZ4 compression algorithm consists of five major stages, including hash calculation, hash table update, match searching, extended match, and sequence encoding, as illustrated in Fig. 2. We use a designed Parallelization Window Size (PWS) to represent parallelism. Within this parallelization window, a set of spatial locations enables concurrent execution of the compression algorithm across multiple consecutive bytes.

We have conducted a thorough analysis of the typical LZ4 implementation on FPGA and identified two primary factors that significantly limit the potential for throughput enhancement in parallel architectures.

• •

  Some implementations employ FIFO structures[10] or advance the parallelization window[11] to capture all non-overlapping matches, aiming to enhance the compression ratio. However, this approach inherently leads to a decrease in the effective degree of parallelism compared to the theoretical parallelism.

• •

  The presence of a loop within the current parallel architectures[9, 10, 11] poses as a bottleneck, constraining the operating frequency and subsequently limiting the maximum achievable throughput.

As previously discussed in Section II-B, researchers have employed FIFO or advanced the starting address of the next parallelization window to enhance the compression ratio, at the expense of reducing the parallelism. The rationale behind these operations ensuring a higher compression ratio is their ability to prevent the oversight of scenarios where multiple non-overlapping matches occur within the parallelization window.

For instance, considering the case where PWS is set to 8 bytes, there is only one scenario where multiple non-overlapping matches exist within the parallelization window. As depicted in Fig. 3(a), the first match ends within the current parallelization window and the starting position of the subsequent match exists within the remaining data of the same window. In this situation, after spending a clock cycle to compress the first match, the compression of the second match within the same parallelization window still requires an additional clock cycle to be carried out, which results in a lower degree of parallelism compared to the previous compression stages where one parallelization window could be fully processed within a single clock cycle. So when encountering the scenario depicted in Fig. 3(a), the actual parallelism will fall below the theoretical parallelism. The extent of this reduction is dependent on the frequency of occurrences of scenarios similar to Fig. 3(a) within the dataset. This inevitable decrease in actual parallelism will ultimately result in a decrement in overall throughput. For example, Benes et al.[10] suffered from a throughput reduction from 10 Gbps to 6.08 Gbps with the implementation of FIFO, while Liu et al.[11] saw their throughput decrease from 6.4 Gbps to 4.5 Gbps by advancing the starting address of the subsequent parallelization window. Their throughput all decreased by approximately 30% to 40% due to the decline in parallelism.

Hence, to enhance the parallelism and align it with the theoretical parallelism, we constrain each parallelization window to process only a single match, as depicted in Fig. 3(b). This approach does not continue to search for matches within the remaining data of the current window, and instead, it starts to find matches from the beginning of the next parallelization window, which will inevitably result in some data within the matched segment being treated as literals, as marked within the orange box in Fig. 3(b), leading to a slight but acceptable compromise in compression ratio.

Subsequently, we evaluate the degradation in compression ratio resulting from our proposed approach using standard test datasets, commonly referred to as corpus. The corpus sets typically encompass a diverse range of input data, ensuring relevance to real-world scenarios. The Calgary corpus[14], is selected in the compression ratio evaluation. The performance of the aforementioned method is presented in Table I.

As shown in Table I, the compression ratio suffers from a modest attenuation ranging from 0.86% to 5.39% across various numbers of hash table entries, which can be considered negligible when contrasted with the throughput enhancement achieved by aligning the actual parallelism with the theoretical parallelism.

Enhancing the frequency of the circuit is one of the most straightforward and effective ways to boost throughput. The underlying cause of the frequency bottleneck in contemporary parallel architectures[9, 10, 11], as extensively illustrated in Section II-B, is the presence of a loop within the architecture. In order to break this loop, it is essential to resolve the time dependency of the address signal during the extended match stage.

In this paper, we aim to establish an upper boundary for the maximum match length, ensuring that the search for the maximum match length can be accomplished within a single clock cycle. By this approach, we no longer need to rely on the match results of the current cycle to determine the address for the next cycle, thus effectively eliminating the temporal dependency and breaking the loop within the architecture.

Furthermore, this operation ensures predictable output delay. By adopting the proposed strategy, the maximum match length information can be promptly obtained within a single clock cycle during the extended match stage, immediately following the discovery of the first match. This attribute distinguishes our approach from the original extended match stage, which exhibited unpredictable delay due to its reliance on the size of the match length.

The disadvantage of establishing a maximum match length limit is apparent. As clearly depicted in Fig. 4, this approach may result in the fragmentation of a long match into multiple shorter ones. Additionally, any small match at the end, measuring less than 4 bytes, will be discarded. This is due to the output format of the LZ4 algorithm, which requires a minimum match length of 4 bytes.

To quantitatively assess the impact of this measure on the compression ratio, we conduct tests utilizing the Calgary corpus. As depicted in Table II, as the maximum match length limit increases, the decrease in compression ratio gradually wanes.

However, setting an excessively high maximum match length limit is not always optimal. As the limit increases, the hardware resources required for match comparison gradually expand. Consequently, to achieve a balance between compression ratio and hardware resource utilization, we have chosen a maximum match length limit of 36 bytes. This choice results in a compression ratio reduction of about 4.46% $\sim$ 8.23%.

This section evaluates the change in the compression ratio when combining the two proposed schemes. The results, tested using the Calgary corpus, are presented in Table III. The compression ratio reduction ranges from 4.93% to 11.68% with various numbers of hash table entries. Given that throughput often takes precedence over compression ratio in numerous applications of lossless compression algorithms[6, 12], a compromise of about 10% in compression ratio to achieve a substantial enhancement in throughput is deemed acceptable.

The parallel compression kernel consists of several modules, all designed to facilitate multi-byte parallel processing.

We implement our hardware architecture on an FPGA to build a high-throughput compression kernel. The selected platform is the Xilinx Kintex-7 XC7K325TFBG676-3 as [7] did.

Given that in previous works[9, 10, 11], the PWS for the LZ4 parallel architecture has been consistently set to 8 bytes, we have also chosen to set our PWS to 8 bytes for a fair comparison. The implementation results is compared with other FPGA implementations of the LZ4 algorithm. Table IV presents a comparison of the designs in terms of frequency, resource utilization, and throughput. The respective implementation platforms (FPGAs) exhibit comparability in terms of resources and/or frequency due to their similarities.

Table IV demonstrates that despite employing the worst technology conditions, our single-kernel parallel architecture achieves a frequency of 251.51 MHz, which surpasses the highest frequency of the current parallel architecture (Benes[10]) by 1.610$\times$, and trails only behind the serial architecture (Xilinx[16]) due to the parallel implementation and technological reasons. As a result of this enhanced frequency, our architecture boasts the maximum throughput among all existing LZ4 architectures, reaching a peak value of 16.10 Gbps. This throughput is an impressive 2.648$\times$ higher than the current leading throughput reported by Benes[10].

In terms of hardware resources, our design also holds advantages. By imposing two limiting conditions, we eliminate the feedback control loops from the original circuit, resulting in a decrease in LUT and FF resources. As can be seen from Table IV, disregarding the MLZ4C algorithm[7], which is incompatible with the official LZ4 tool due to alterations in the LZ4 compression format, our design boasts an area efficiency ratio of 1.131 Gbps/K slices, notably surpassing other architectures, including Benes[10], Xilinx[16], and HybriDC[11].