Jeffrey Bosboom's Blog

[blog] [projects] [about]

Papers: compressed virtual memory

The Case for Compressed Caching in Virtual Memory Systems (Wilson, Kaplan, Smaragdakis; gratis PDF)

Earlier papers in compressed virtual memory (CVM) found mixed performance benefits and penalties depending on the program, concluding CVM was mostly useful for diskless systems that had to swap over a network. This paper argues that different compression schemes and better adaptive CVM tuning, combined with faster processors, make CVM practical even for systems with fast disks.

This paper observes that general-purpose Lempel-Ziv compression algorithms are unable to exploit special properties of program data: word-aligned object fields, pointers that often point nearby or to small distant regions, small integer values, etc.. The authors propose a compression scheme based on a dictionary of 16 recently-seen 32-bit words. Each input word is encoded with a 2-bit tag denoting an all-zero word (a special case), a word not in the dictionary (followed by the word), a dictionary entry matching in the top 22 bits (followed by the index and the remaining 10 bits), or a dictionary match (followed by the index). Partial matching exploits small integers (top bits zero) and pointers pointing to small regions (differing only in bottom 10 bits). On the programs used in this study, this scheme achieved comparable compression to LZO at a lower cost. (Note that current CVM implementations often use LZO, though processors are even faster today than they were in 1999.)

MemZip: Exploring Unconventional Benefits from Memory Compression (Shafiee, Taassori, Balasubramonian, Davis; gratis PDF)

Most compressed memory systems use compression to increase memory capacity (and avoid page faults). This paper instead targets reduced memory bandwidth, leading to decreased energy consumption. This is mostly a matter of not packing compressed data as tightly as possible (leaving the data at its original start address) and exploiting some DDR3 protocol features; the remaining space in each cache line can be used for free ECC or special power-saving coding.