A Survey on Data Compression in Cache and Main Memory Systems

[sparsh]

https://www.academia.edu/12429529/A_...Memory_Systems Accepted in IEEE TPDS 2015.


It highlights motivation for using compression in HPC systems (especially next-generation extreme-scale systems) and also presents challenges in use of compression. It discusses compression in CPUs and GPUs, conventional (SRAM and DRAM) and non-volatile memory (NVM) systems, and 2D and 3D memory systems. It also discusses interaction of compression with prefetching, error-correction and thermal and power management techniques.

[Paul W.]

sparsh,

You may be interested in

(1) a couple of my early papers (1991) that talk about compressed caching for virtual memory; so far as I know, I invented it, though others probably invented it independently. (I think I may have talked about it in earlier tech reports I don't have handy.) When Fred Douglis published his 1993 paper, I immediately thought that he missed a few tricks IIRC---(1) he was keeping the compressed version of a page in RAM after it was uncompressed, wasting precious space; you need a fast compression algorithm so that you can re-compress the page instead, (2) his adaptation couldn't really work right without noticing the cost of hitting recently-evicted pages, and (3) he didn't scale his results to show it'd work okay anyway if the processor was fast enough, as processors soon would be.

(2) Cdr-coding systems in some Lisp systems, which compressed linear linked lists into a vector representation at garbage-collection time. At least on the Symbolics Lisp Machines, there was hardware tag support, with most of the tag-checking done in parallel with the normal hash tag check. That was what got me thinking about how to exploit a stock TLB similarly-but-differently, and how very compressible pointers can be.

(3) The Apple Newton, which used our WKdm algorithm years before we got around to publishing it (and years and years before OS X), and did so largely to conserve power rather than increase speed. (That was before Lithium-Ion batteries, and battery life was critical.)

---

These are the two old papers I mentioned. They talk about the compressibility of pointers, and the increasing attractiveness of compressed caching given technology trends (now clearly true), among many other things.

Some Issues and Strategies in Heap Management and Memory Hierarchies:

http://dl.acm.org/citation.cfm?id=12...reflayout=tabs

Operating System Support for Small Objects

http://ieeexplore.ieee.org/xpl/login...5%26index%3D11