SEP: A General Lossless Compression Framework with Semantics Enhancement and Multi-Stream Pipelines

1 Introduction

Lossless data compression reduces data size while preserving all the original information, which has been widely used in various fields, including data storage [Lagar-Cavilla et al., 2019], data transmission [Yang et al., 2023], to name a few. The performance of lossless compression method is mainly examined using compression ratio and compression speed [Schiopu and Munteanu, 2020; Chandra and Hsu, 2014]. To improve both factors, we construct a general lossless compression framework with semantics enhancement and multi-stream pipelines.

∗Corresponding author

The fundamental technique of lossless compression is entropy coding, which includes methods such as Huffman coding [Knuth, 1985; Moffat, 2019] and arithmetic coding [Rissanen and Langdon, 1979]. Given a system that generates symbols with certain probability distributions, according to Shannon's source coding theorem [Affeldt et al., 2014], the ideal code length I(x) of the next symbol x is expressed as follows:

where p(x) is the probability of the symbol to be encoded. Entropy coder requires the statistical model to predict the statistics of the system [Zhang et al., 2021]. Based on Equation 1, the entropy coder uses shorter code for more predictable symbols, which results in a higher compression ratio [Sullivan et al., 2012]. On top of the entropy coder, the deep-learning-based lossless compressors use neural networks to predict the statistical characteristics of the system [Mao et al., 2022b], which potentially gives higher p(x) and therefore higher compression ratio [Wu et al., 2016]. An inaccurate prediction of the statistical characteristics can result in an extremely small p(x), such that the symbol x can still be losslessly compressed but with a very low compression ratio.

To improve both compression ratio and compression speed of deep-learning-based lossless compressors, the existing research focus on different networks. The recent deep-learningbased lossless compressors are mainly built based on PyTorch [Mentzer et al., 2019]. In Table 1, we present the various characteristics of several deep-learning-based compressors. Compressors like tensorflow-compress [Knoll, 2016; Contoli and Lattanzi, 2023] and DecMac [Liu et al., 2019] use long-short-term memory (LSTM) to capture long-term dependencies within the input data stream. The latest research demonstrates that the mechanisms of transformer and multi-layer perception (MLP) can achieve even more accurate estimation and also higher compression speed compared to other deep-learning-based lossless compressors [Mao et al., 2022b]. NNCP [Bellard, 2019], TRACE [Mao et al., 2022b], OREO [Mao et al., 2022a] and PAC [Mao et al., 2023] are the typical compressors that use the transformer or MLP. Most deep-learning-based lossless compressors train their networks with a GPU to speed up the compression process [Kang et al., 2022; Ko et al., 2021]. PAC reduces the traffic of CPU-GPU data transfer using software cache in GPU memory [Mao et al., 2023], which helps PAC compress faster. To further improve both compression ratio and compression speed, the main challenges faced by current deep-learning-based lossless compressors are summarized into three aspects: 1) Data feature extraction is difficult for byte streams. The lossless compression requires the compressor to convert several types of input (such as image, text, and sound, etc) into byte streams [Yamagiwa, 2022]. The semantics of such byte streams are highly sparse and varied, which makes it difficult to predict and gain a high compression ratio. 2) Disk I/O, CPU-GPU data transfer and arithmetic coding are time-consuming, which is taken up to one third of the total [Choukse et al., 2020]. Although existing methods use a cache mechanism to decrease the traffic of data transfer, these approaches only partially reduce the transfer overhead and do not fully utilize the parallel capabilities of multi-core CPUs and GPUs [Cloud et al., 2011]. 3) The compression of large-scale files results in high GPU memory footprint demand. PyTorch's GPU memory for multiple streams is isolated and cannot be reused, resulting in a huge waste of memory.

To overcome these challenges, we propose a lossless compression framework based on Semantics Enhancement and multi-stream Pipelines (SEP). The contributions are summarized as follows:

• Semantics enhancement module: We propose a series of novel approaches to capture complex semantic information of adjacent byte sequences, which achieve higher compression ratios across diverse data types.
• Multi-stream pipelines: We propose a multi-stream pipeline mechanism for parallel compression. By hiding disk I/O and CPU-GPU data transfer, such as Host
• to Device (H2D) and Device to Host (D2H), our objective is to fully use the hardware for compression speed.
• GPU Memory Optimization: We propose a method to enable GPU memory reuse across streams by breaking PyTorch's default stream-level memory isolation.
• State-of-the-art (SOTA) compression performance: Our experiments demonstrate that the SEP framework enhances the backbone neural networks' compression ratio by 5.1% on average, reduces compression time by 30.0%, and cuts GPU memory usage by 36.2%.

2 RelatedWork

[Deep-Learning Data Compression Methods] Recently, several deep-learning-based compressors have been proposed to improve compression ratios of heterogeneous files, e.g., video, image, etc. These approaches view the compression task as a sequential modeling problem, where the historical symbols are used as input to estimate the probability of the incoming symbol. NNCP [Bellard, 2019] and TRACE [Mao et al., 2022b] utilize transformers to achieve probability estimation. However, the semantic density of byte streams is very sparse, and existing models cannot extract enough information from byte streams, resulting in low compression rates. Furthermore, the compression speed of these compressors is impractical for real-world applications. For example, NNCP's dictionary size of 16,384 and its 55 MB transformer model lead to a compression speed of only 2.0 KB/s. TRACE achieves a compression speed of 15.9 KB/s, while PAC offers an even higher compression speed of 31.1 KB/s. Therefore, methods that improve both the compression ratio and speed are needed for deep-learning compressors.

[GPU Memory Optmization] The work on GPU memory optimization is mainly focused on offloading [Lin et al., 2023], recomputation [Peng et al., 2020] and defragmentation [Fang et al., 2022; Ren et al., 2021]. Offloading techniques like vDNN [Rhu et al., 2016] reduce memory usage on the GPU side but increase the communication between host and device, leading to higher host memory requirements. The recomputation technique like checkpoint [Chen et al., 2016] leads to irregular allocation requests, resulting in higher fragmentation. Defragmentation like Glake [Guo et al., 2024] is currently limited to only single-stream scenarios. Our work is the first to delve into GPU memory reuse in PyTorch's multi-stream environment, offering potential benefits for models and applications built with PyTorch.

3 Byte-StreamData Compression

Any data can be represented as a binary data stream. In bytestream data compression, each set of 8 bits is considered as a byte to be compressed [Mao et al., 2022b]. In this paper, we divide the byte stream into many sequences with length L ∈ N +, serving as input tokens for the model. Each sequence is denoted as X ∈ RL×1 . Our objective is to forecast the probability distribution for the next byte, which contains the probabilities for 256 possible byte values. The probability distribution computation is formalized as a Predictor function by Equation 2.

where ∑256 i=1 pi = 1 and pi denotes the probability of the i-th possible byte value. Once the probability distribution is predicted, we compress the input sequence with an arithmetic encoder. The ArithmeticEncoder function can be represented by Equation 3:

where Xcompressed denotes the compressed result and is written to disk. Multiple rounds of the above process constitute a complete data compression. For decompression, due to the model parameters being fixed, executing the training process again can produce the same probability distribution. The decompression results can be obtained through the arithmetic encoder [Howard and Vitter, 1992; Howard and Vitter, 2008].

4 The SEP Framework

4.1 Overview of SEP Architecture

The SEP framework divides the compression system into multiple components. Figure 1 shows the overview architecture of the SEP framework. All types of binary files are first converted to byte streams. These streams are divided and initialized to different task queues, with a random probability distribution. Then, the Semantics Enhancement (SE) Module extracts the features of the byte stream and turns them into the fusion patches with adaptive stride. By feeding the enhanced data into compressor backbones such as TRACE, PAC and others, the probability distribution of the next byte is predicted. Finally, the byte stream with a probability distribution is compressed by the arithmetic coder. Notably, our computation and GPU optimization modules can simultaneously reduce memory consumption and expedite the entire compression process above, which includes Direct Memory Access (DMA) and I/O hiding to enhance the GPU and CPU throughput. In the following subsections, we will detail the design and techniques implemented for each key component of our SEP framework. During decompression, the same model parameters are applied to reproduce the training process, ensuring the regeneration of the consistent probability distribution. This approach allows the decompression process to accurately restore the original data, achieving lossless compression. Most importantly, our SEP framework can also be fully used in the decompression process, leading to an improvement in decompression speed.

4.2 Semantics Enhancement Module Semantic-Patch Expansion

Byte stream data is characterized by low semantic density and uneven distribution [Coull and Gardner, 2019]. Existing methods use single-byte symbols as tokens for attention computation [Mao et al., 2023; Mao et al., 2022b]. However, the limited receptive field makes it difficult to learn semantic information. In the Semantic-Patch Expansion module, we transform single-byte symbols into sub-sequence level patches as tokens. This enables the network to better understand latent cross-patch semantic correlations and to achieve a high compression speed with fewer tokens.

As shown in Figure 2 (a), a single byte matrix X with the length of L is embedded with a matrix E ∈ R256×D , where D represents the dimension of the embedded vector. In Equation 4, Xe ∈ RL×D is the embedded form of X.

Then, a patching function PATCH segments Xe into patches. Specifically, assuming the length of the patch is P and the length of the stride is S, each patch is tokenized stride by stride. The length of the overlap between two adjacent patches is P - S. Therefore, N patches can be segmented from Xe, where N = L-P S + 1. The process is depicted by Equation 5.

where Xs ∈ RN×D×P is the reshaped form of N patches, and each patch is a D × P matrix.

Dimension Fusion

Once the data has been divided into patches, the information of multiple bytes in a patch is critical for attention module. We design a high-level Dimension Fusion (DF) module, which captures complex intra-patch relationships.

As shown in Figure 2 (b), we do a permutation operation to reorganize the patches in Xs and make a position alignment which can maintain the consistency of the channel space. The DF can be modeled as:Xd = DF(Xs) (6)

where Xs is the output of Semantic-Patch Expansion, Xd ∈ RN×F , and F is the fused as D×P.

Adaptive Stride

For convenience, it is a common practice to partition data into patches using a fixed stride (e.g., 4 or 8) [Zhang and Yan, 2022; Nie et al., 2022]. However, the manual setting of hyper-parameters requires careful fine-tuning. Given that the semantic density of byte stream varies, we propose an adaptive stride method. Specifically, we employ a mask matrix to "simulate" changes in stride. If one patch is masked (value being 0), it indicates low semantic density, and the sliding window takes an extra step forward. The design has two advantages: 1) Semantic density distribution is adjusted to be more uniform. 2) Sparse matrix multiplication speeds up the compression process.

Figure 2 (c) shows the operation in detail. The input for the adaptive stride module is defined as H ∈ RB×N×F , which comprises B instances of Xd, where B is the batch size. Then, we design a mask tensor M ∈ RB×N×F . The M's dimensions correspond to the H, since we need to use M to selectively mask patch in different batches. In the initial stage, all elements inMare set to 1, which means that every patch is retained. The initialization process can be expressed as Equation 7:

Through the learning, the elements inMcan be continuously adjusted. Once the element is lower than a threshold, the element will be set to 0. The process is shown in Equation 8:

where Z ∈ RB×N×F is the masked result. Figure 3 shows an example of masked results, the white block represents the masked patch. Compared with the current method where the stride is fixed at 1, our adaptive stride produces a sparser matrix. Furthermore, according to the semantic density distribution of the byte stream, the adaptive stride can guide the backbone network to swiftly focus on important information.

4.3 Multi-StreamPipelines

The Multi-Stream Pipelines method is designed to hide CPUGPU data transfer, arithmetic encoder and disk I/O. A comparison between the PAC pipeline [Mao et al., 2023] and our pipelines is given in Figure 4.

[PAC Pipeline] In the top part of Figure 4, the compression process is shown to be sequential, with inefficient use of GPU and CPU cores. The CPU dispatches tasks to the GPU, but remains blocked waiting for GPU operations to finish. Once the GPU completes tasks like backpropagation, the CPU resumes its work, including arithmetic encoding (AC) and I/O operations, while the GPU waits for the next CPU command. [SEP-based Multi-stream Pipelines] Evident parallelism and time savings are shown in the bottom part of Figure 4. Nowadays, most GPUs are equipped with dual copy engines and a kernel computation engine, such as NVIDIA RTX 4090 or AMD MI250. We design the multi-stream pipelines to

Algorithm 1 Multi-Stream Pipelines

1: // Producer 2: for task in the T do 3: for i = 0 to pool.size do 4: stream = pool[i]; 5: if torch.cuda.stream(stream) == TRUE then 6: task gpu=task.to('gpu', non blocking=True); 7: prob = backbone(train gpu); 8: probability=prob.to('cpu', non blocking=True); 9: queue.put(probability); 10: end if 11: end for 12: end for 13: // Consumer 14: while queue is not empty do 15: probability = queue.pop(); 16: compressed = Arithmetic encoder(probability); 17: compressed.write(); 18: end while

hide H2D and D2H data transfers by a non-blocking strategy. For tasks such as arithmetic encoding and I/O, we build task queues with a producer-consumer model. One CPU core focuses solely on scheduling, the other cores handle computations, which eliminates the idle time for the GPU and CPU. The pseudocode is shown in Algorithm 1. We initialize the stream set as pool, the task set as T, and the producerconsumer queue as queue. The algorithm divides the execution process into producer (Line 2-12) and consumer (Line 14-18). During producer process, the training task is across the different streams in pool (Line 3). DMA operations such as non-blocking H2D and D2H are set for overlapping (Lines 6 and 8). When probability distribution computations are finished, the Arithmetic Encoder and I/O tasks are put in the queue (Line 9). At the same time, the consumer loops to find the tasks in the queue (Line 14). Then the consumer sequentially retrieves tasks from the queue (pop) and performs calculations (Line 15-17).

4.4 GPUMemory Sharing Strategy

To increase GPU memory utilization during multi-stream training, enabling support for larger models and parameters, we design an inter-stream memory sharing strategy on PyTorch 2.0's memory allocator.

As shown in Figure 5, we first use a profiler to analyze the sequence of memory allocation and release to identify memory blocks that can be shared. We focus on memory blocks that are few but occupy a large portion of memory for maximizing memory reuse. Notably, our method preserves the original timing of allocation and deallocation. Next, we set up a shared pool to manage the shared memory blocks between streams. Our method does not alter the allocation and deallocation timing of memory blocks during the training process. For example, when Stream 1 (S1) completes its training, the large continuous memory blocks it used are released back into the shared pool and labeled as reserved blocks. The next blocking Stream 2 (S2) can access these reserved blocks by adjusting its pointer to the address of these blocks. When S2 requests new memory space, it searches the shared pool for available reserved blocks. If suitable blocks are found, malloc reuses them for the next stream, significantly saving memory. Furthermore, the entire training process involves a loop-intensive data flow, where the size of the memory blocks involved in computations is the same. This allows for a match with the memory blocks shared from previous training processes, further reducing memory fragmentation.

5 Experiments

All experiments are performed on a server powered by Intel 5218 CPUs (16 cores) and eight NVIDIA A800 GPUs (80GB memory), using a PCIe Gen 4.0 interface. The storage includes a SAMSUNG SSD PM893 with 1.92 TB capacity via SATA connection. The operation system is Ubuntu 20.04. The software environment is based on PyTorch version 2.0.1 and NVIDIA's CUDA version 12.1 for GPU acceleration.

5.1 Experimental Settings

Datasets. We evaluate the SEP framework on seven real-world datasets, including: Book [Zhu et al., 2015], Enwik9 [Mahoney, 2011], Float [Burtscher and Ratanaworabhan, 2008], Sound, Image [Deng et al., 2009], Backup(heterogeneous) [Mao et al., 2023] and Silesia [Deorowicz, 2007; Piczak, 2015].

Baselines. We select two SOTA compressors for comparison, including TRACE [Mao et al., 2022b], PAC [Mao et al., 2023]. To better illustrate the generalization of SEP, we select time-series forecasting model PatchTST [Nie et al., 2022] as one of the backbone and directly integrate it into SEP.

Parameter Details. To ensure the fairness of the experiment, all model parameters are set to the same. We set history sequence length to 64, the patch length to 4, and the corresponding feature dimension to 64. In all backbones, Adam is applied with a learning rate of 0.001, the threshold is set to 0.5, and the stride is set to 1.

5.2 Main Experiments

Table 2 presents the compression ratios and speeds of SOTA compressors, as well as those of the compressors when integrated with the SEP framework, across various datasets. Overall, our solution achieves an average improvement of 5.1% in compression ratios and an average improvement of 30.2% in compression speed.

[Compression Ratio Comparison] In Table 2, PatchTST naturally has lower compression than TRACE since it is not created to focus on the compression task. However, after combining it with our framework, the compression ratio easily surpasses TRACE. For the SEP+PAC, we observe an improvement in compression ratio, although it is less significant compared to SEP+TRACE and SEP+PatchTST. This difference is largely attributed to the MLP model design of PAC. The results of combining SEP with other backbones prove that the SEP framework can be flexibly integrated with other backbones and exhibit excellent compression performance. We find that models without pre-training show poor performance in the early compression stages (20,000 rounds). By developing specialized pre-training models for each data type, we further improve compression performance significantly, achieving a 12.8% improvement on Enwik9.

[Compression Speed Comparison] In Table 2, once a backbone model is combined with the SEP framework, the compression speed can directly exceed the original model by a wide margin. The utilization of both CPU and GPU to construct pipelines makes the process universally applicable to nearly all deep-learning models. Consequently, SEP consistently performs across various models and datasets, achieving an average speed improvement of 30.0%. This enhancement is vital for compression tasks.

[GPU Memory Optimization] We conduct a comparative analysis of GPU memory footprint between the SEP and the native PyTorch on different batch sizes. Figure 6 illustrates that our memory optimization strategy achieves an average reduction of 21.7% on SEP+PAC, 61.7% on SEP+PatchTST, and 26.3% on SEP+TRACE. Overall, our SEP reduces memory usage by approximately 36.2% compared to the PyTorch framework. Due to the fact that PAC consists of multiple linear layers with small matrices, and PatchTST comprises large patch blocks with large matrices, the optimization of PatchTST shows better results with higher intermediate variables. These results show SEP as an effective solution for GPU memory constraints, with potential for future multistream deep learning applications.

[Adaptive Stride] We use the SEP+TRACE as the baseline and all parameters are consistent with the main experiment. We select the fixed stride value from [1, 2, 3, 4] and compare it with our adaptive stride method. Figure 7 presents the comparison between the adaptive stride and other fixed strides in compression ratio. This result proves that the design of adaptive stride improves the compression ratio due to the dynamic adjustment ability of semantic density. Notably, there is a 4.1% improvement in compression speed due to the sparse matrix. Adaptive stride addresses the issue of excessive redundant information following patching in existing models and offers a novel approach for time series research.

5.3 Ablation Study

[Module Ablation on SEP] We evaluate the impact of different SEP modules on compression ratio and speed (KB/s). The multi-stream pipeline (PIPE) module achieves the highest acceleration in compression speed, while the SE module slightly improves both the compression ratio and speed. The memory sharing (MS) module does not directly accelerate the process but allows for handling larger datasets, enabling SEP to compress more data without exceeding memory limits.

[Ablation on Sparse Matrix and Size Reduction (SE)] In SE module, the speedup is primarily attributed to two factors: matrix size reduction and sparse matrix computation. To measure the impact of each part, we conduct aan blation study in Table 4 on PAC+SEP. The results indicate that the main speedup comes from matrix size reduction when sparsity is low (30-50%). However, the Image dataset sparsity can reach 78% in certain iterations (not every iteration). When sparsity exceeds 70%, the use of sparse matrix operations ('sparse.mm') further accelerates computation.

[Evaluation of SEP Multi-Stream Pipeline] To evaluate the performance of SEP's multi-stream pipeline over CUDA stream pipeline, we conduct an ablation study that excludes the SE module. The results in Table 5 show that SEP outperforms CUDA in both image and text datasets, demonstrating the efficiency of SEP pipeline in multi-GPU settings.

5.4 Scalability and Hardware Compatibility

[Scalability] We adopt multiprocessing and data parallelism to minimize communication overhead as much as possible. To evaluate the scalability of the SEP-based model in a multiGPU environment, we conduct experiments under two, four and eight NVIDIA Tesla A800 GPUs, which demonstrate the SEP's scalability and efficiency for data compression. As shown in Figure 8, under data such as Image and Enwik9, a near-linear acceleration ratio can be achieved, and still exhibits good scalability.

[Hardware Compatibility] To demonstrate the compatibility of SEP, we conduct experiments on low-end devices, including NVIDIA GTX 1060 (6GB), RTX 2080 (8GB) and RTX 3080 (10GB). As shown in Table 6, SEP consistently outperforms baseline models (PAC, TRACE, PatchTST) across all hardware configurations, still achieving up to 30% speedup on low-end GPUs. Notably, the GTX 1060 achieves an 82% speedup on PatchTST, likely due to SEP's memory optimization reducing frequent memory paging caused by PatchTST's high memory usage on devices with limited memory.

6 Conclusion

The SEP is a plug-in framework that easily integrates with various deep learning models and compression algorithms. Meanwhile, SEP supports flexible hardware configurations and offers out-of-the-box functionality for compressing and decompressing data.

Acknowledgements

This work is supported by the National Key Research and Development Program of China (2022ZD0115305). We thank VenusAI Platform (http://data.aicnic.cn) for kindly providing the GPU clusters for training the models.

Contribution Statement

† These authors have equal contribution.