Efficient Data Compression with Multi-Level Cell Memory

Modern applications are becoming more data-intensive especially with the progress in AI technologies, thus, increasing the demand for larger data storage. This necessitates better compression strategies. Emerging non-volatile Multi-Level Cell (MLC) memories have recently been studied for their capability of storing multiple bits per cell. These MLCs are typically utilized by data encoding schemes that pack maximum allowable data into each cell to maximize storage efficiency. However, this approach of seemingly maximizing MLC utilization instead limits flexibility, forcing all physical states in an MLC to be used for raw data storage leaving no room for alternative use. In this paper, we propose a novel data compression technique that leverages the additional states available in MLC devices—beyond the two states of traditional Single-Level Cell (SLC) devices as special indicators to encode runs of bit patterns. This approach builds on the principles of Run-Length Encoding (RLE), a classic compression scheme. However, conventional RLE suffers from a fundamental limitation of flexibility in binary storage systems, requiring each run block to be fixed sized. Our proposed approach eliminates this limitation by leveraging additional MLC states, significantly reducing data expansion on non-repeating bit patterns, as well as achieving exponential gains in compressibility for longer runs of repeating bit patterns. Experimental comparisons against state-of-the-art RLE schemes demonstrate that our method achieves an average of 20× improvement in compression ratios across all evaluated benchmarks on 4KB data blocks. Unlike RLE, our approach reduces the possibility of data expansion on irregular data to a negligible amount. In addition, we perform characterization of our proposed scheme showing the behavior and performance with increasing run block size for both same bit and alternating bit runs.