Random-Access Hardware Sequence Compression

Memory compression is a promising solution to combat the high and rising DRAM cost in modern data centers. Due to providing high compression ratios, page-level sequence compression (e.g., LZ) has become a part of the industry specification for hardware memory compression. Unfortunately, sequence compression suffers from slow decompression. Decompressing a requested memory block in a page incurs 1) high memory access latency to fetch everything prior to the block and 2) long computation latency due to decompressing all the way from the start of the page to the requested block. This is because to maximize compression ratio, each block is compressed using everything prior to the block as a large dictionary, resulting in high access and computation overhead to fetch and reconstruct the large dictionary when decompressing a needed block. To tackle the high access overhead, we propose a randomlydecompressible compression algorithm that drastically shrinks the total dictionary in each page down to 128 B, without sacrificing compression ratio w.r.t. the state-of-the-art hardware. We also design compression and decompression hardware for the new algorithm; ASIC synthesis reports that total decompression computation latency is reduced to 18 ns per needed block vs. 140 ns average latency under the state-of-the-art.