Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Increasing cache capacity via compression enables designers to improve performance of existing designs for small incremental cost, further leveraging the large die area invested in last level caches. This paper explores the compressed cache design space with focus on implementation feasibility.

Our compression schemes use companion line pairs -- cache lines whose addresses differ by a single bit -- as candidates for compression. We propose two novel compressed cache organizations: the companion bit remapped cache and the pseudoassociative cache. Our cache organizations use fixed-width physical cache line implementation while providing a variablelength logical cache line organization, without changing the number of sets or ways and with minimal increase in state per tag. We evaluate banked and pairwise schemes as two alternatives for storing compressed companion pairs within a physical cache line. We evaluate companion line prefetching (CLP), a simple yet effective prefetching mechanism that works in conjunction with our compression scheme. CLP is nearly pollution free since it only prefetches lines that are compression candidates.

Using a detailed cycle accurate IA-32 simulator, we measure the performance of several third-level compressed cache designs simulating a representative collection of workloads. Our experiments show that our cache compression designs improve IPC for all cache-sensitive workloads, even those with modest data compressibility. The pairwise pseudo-associative compressed cache organization with companion line prefetching is the best configuration, providing a mean IPC improvement of 19% for cache-sensitive workloads, and a best-case IPC improvement of 84%. Finally, our cache designs exhibit negligible overall IPC degradation for cache-insensitive workloads.

REFERENCES

• 1: http://www.itrs.net/Common/2004Update/2004Update.htm International Technology Roadmap for Semiconductors, 2004 update. Semiconductor Industry Association, 2004.
• 2: http://www.intel.com/products/processor/itanium2/index.htm, Intel® Itanium® 2 Processor.
• 3: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 4: Tien-Fu Chen , Jean-Loup Baer, Reducing memory latency via non-blocking and prefetching caches, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.51-61, October 12-15, 1992, Boston, Massachusetts, United States
• 5: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 6: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 7: Paul R. Wilson , Scott F. Kaplan , Yannis Smaragdakis, The case for compressed caching in virtual memory systems, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.8-8, June 06-11, 1999, Monterey, California
• 8: Tremaine R., Fanaszek P., Robinson J., Schulz C., Smith T., Wazlowski, M., and Bland, P., "IBM Memory Expansion Technology (MXT)", in IBM Journal of Research and Development, Vol. 45, No. 2, March 2001.
• 9: Design and Evaluation of a Selective Compressed Memory System, Proceedings of the 1999 IEEE International Conference on Computer Design, p.184, October 10-13, 1999
• 10: Youtao Zhang , Jun Yang , Rajiv Gupta, Frequent value locality and value-centric data cache design, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.150-159, November 2000, Cambridge, Massachusetts, United States
• 11: Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States [doi>10.1145/360128.360154]
• 12: Kjelso, M., Gooch, M., Jones, S., "Main memory hardware data compression", 22^nd Euromicro Conference, IEEE Computer Society Press, September 1996.
• 13: Alaa R. Alameldeen , David A. Wood, Adaptive Cache Compression for High-Performance Processors, Proceedings of the 31st annual international symposium on Computer architecture, p.212, June 19-23, 2004, München, Germany
• 14: Erik G. Hallnor , Steven K. Reinhardt, A Unified Compressed Memory Hierarchy, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.201-212, February 12-16, 2005 [doi>10.1109/HPCA.2005.4]
• 15: Magnus Ekman , Per Stenstrom, A Robust Main-Memory Compression Scheme, Proceedings of the 32nd annual international symposium on Computer Architecture, p.74-85, June 04-08, 2005
• 16: Singhal, R.; Venkatraman, K. S.; Cohn, E.; Holm, J. G.; Koufaty, D; Lin, M-.J.; Madhav, M.; Mattwandel, M.; Nidhi, N.; Pearce, J.; Seshadri, M. "Performance Analysis and Validation of the Intel® Pentium® 4 Processor on 90nm Technology." Intel Technology Journal. http://developer.intel.com/technology/itj/2004/volume08issue01/(February 2004).
• 17: Gochman, S.; Ronen, R.; Anati, I.; Berkovits, A.; Kurts, T.; Naveh, A.; Saeed, A.;Sperber, Z.; and Valentine, R. "The Intel® Pentium® M Processor: Microarchitecture and Performance.", Intel Technology Journal, http://developer.intel.com/technology/itj/2003/volume07issue02/ (May 2003).
• 18: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 19: Anant Agarwal , Stephen D. Pudar, Column-associative caches: a technique for reducing the miss rate of direct-mapped caches, Proceedings of the 20th annual international symposium on Computer architecture, p.179-190, May 16-19, 1993, San Diego, California, United States
• 20: http://www.intel.com/products/server/processors/index.htm Intel Xeon Processor Family.
• 21: Y. Zhang and R. Gupta, "Enabling Partial Cache Line Prefetching Through Data Compression", International Conference on Parallel Processing, pages 277--285, Kaohsiung, Taiwan, October 2003
• 22: Gailly, J. and Adler, M., "Zlib general purpose compression library", User manual for zlib version 1.0.4, URL: http://quest.jpl.nasa.gov/zlib/, July 1996
• 23: Erik G. Hallnor , Steven K. Reinhardt, A compressed memory hierarchy using an indirect index cache, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.9-15, June 20-20, 2004, Munich, Germany [doi>10.1145/1054943.1054945]
• 24: A. Alameldeen, D. Wood, "Interactions Between Compression and Prefetching in Chip Multiprocessors", in proceeding of 13^th International Symposium on High-Performance Computer Architecture, 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles

General Terms:
Design, Performance

Keywords:
cache compression, cache design, prefetching