Compressed virtual memory systems have been suggested, and in some cases implemented, to improve the effectiveness of use of physical RAM. However, most proposals and/or implementations are based on adaptive compression algorithms which achieve good compression ratios, but are slow compared to a local disk. Hence, they can only give some advantage with very slow (e.g. network-mounted) swap devices. In this paper we show that in many cases memory pages contain highly compressible data, with a very large amount of zero-valued elements. This suggests the replacement of slow, adaptive compression algorithms with very fast ones based on static Huffman codes.We present one such algorithm which, paired with a careful layout of the data, is able to compress 4KB pages at 40MB/s even when implemented in software on an inexpensive Pentium 100 system. We also show that the algorithm can achieve interesting compression ratios despite its simplicity.Since the compression/decompression speed of our algorithms exceeds disk bandwidth, its use in a compressed VM system can lead to both memory savings and speed improvements in servicing page faults. In this paper we discuss some possible applications of the algorithm in a compressed VM system.
A very fast algorithm for RAM compression
RIZZO, LUIGI
1997-01-01
Abstract
Compressed virtual memory systems have been suggested, and in some cases implemented, to improve the effectiveness of use of physical RAM. However, most proposals and/or implementations are based on adaptive compression algorithms which achieve good compression ratios, but are slow compared to a local disk. Hence, they can only give some advantage with very slow (e.g. network-mounted) swap devices. In this paper we show that in many cases memory pages contain highly compressible data, with a very large amount of zero-valued elements. This suggests the replacement of slow, adaptive compression algorithms with very fast ones based on static Huffman codes.We present one such algorithm which, paired with a careful layout of the data, is able to compress 4KB pages at 40MB/s even when implemented in software on an inexpensive Pentium 100 system. We also show that the algorithm can achieve interesting compression ratios despite its simplicity.Since the compression/decompression speed of our algorithms exceeds disk bandwidth, its use in a compressed VM system can lead to both memory savings and speed improvements in servicing page faults. In this paper we discuss some possible applications of the algorithm in a compressed VM system.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
