  In this thesis, we describe a new, practical approach to integrating
hardware-based data compression within the memory hierarchy, including on-chip
caches, main memory, and both on-chip and off-chip interconnects. This new
approach is fast, simple, and effective in saving storage space. A key insight
in our approach is that access time (including decompression latency) is
critical in modern memory hierarchies. By combining inexpensive hardware
support with modest OS support, our holistic approach to compression achieves
substantial improvements in performance and energy efficiency across the memory
hierarchy. Using this new approach, we make several major contributions in this
thesis. First, we propose a new compression algorithm, Base-Delta-Immediate
Compression (BDI), that achieves high compression ratio with very low
compression/decompression latency. BDI exploits the existing low dynamic range
of values present in many cache lines to compress them to smaller sizes using
Base+Delta encoding. Second, we observe that the compressed size of a cache
block can be indicative of its reuse. We use this observation to develop a new
cache insertion policy for compressed caches, the Size-based Insertion Policy
(SIP), which uses the size of a compressed block as one of the metrics to
predict its potential future reuse. Third, we propose a new main memory
compression framework, Linearly Compressed Pages (LCP), that significantly
reduces the complexity and power cost of supporting main memory compression. We
demonstrate that any compression algorithm can be adapted to fit the
requirements of LCP, and that LCP can be efficiently integrated with the
existing cache compression designs, avoiding extra compression/decompression.
