A compressed memory hierarchy using an indirect index cache

ABSTRACT

The large and growing impact of memory hierarchies on overall system performance compels designers to investigate innovative techniques to improve memory-system efficiency. We propose and analyze a memory hierarchy that increases both the effective capacity of memory structures and the effective bandwidth of interconnects by storing and transmitting data in compressed form.Caches play a key role in hiding memory latencies. However, cache sizes are constrained by die area and cost. A cache's effective size can be increased by storing compressed data, if the storage unused by a compressed block can be allocated to other blocks. We use a modified Indirect Index Cache to allocate variable amounts of storage to different blocks, depending on their compressibility.By coupling our compressed cache design with a similarly compressed main memory, we can easily transfer data between these structures in a compressed state, increasing the effective memory bus bandwidth. This optimization further improves performance when bus bandwidth is critical.Our simulation results, using the SPEC CPU2000 benchmarks, show that our design increases performance by up to 225% on some benchmarks while degrading performance in general by no more than 2%, other than a 12% decrease on a single benchmark. Compressed bus transfers alone account for up to 80% of this improvement, with the remainder coming from increased effective cache capacity. As memory latencies increase, our design becomes even more beneficial.

REFERENCES

• 1: Bulent Abali , Hubertus Franke , Xiaowei Shen , Dan E. Poff , T. Basil Smith, Performance of Hardware Compressed Main Memory, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.73, January 20-24, 2001
• 2: 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
• 3: S. Arramreddy, D. Har, K. Mak, et al, "IBM X-Press Memory Compression Technology Debuts in a ServerWorks NorthBridge", HOT Chips 12 Symposium, Aug. 2000
• 4: N. Binkert, E. Hallnor, S. Reinhardt, "Network-Oriented Full-System Simulation using M5", Sixth Workshop on Computer Architecture Evaluation using Commercial Workloads (CAECW), February 2003
• 5: Erik G. Hallnor , Steven K. Reinhardt, A fully associative software-managed cache design, Proceedings of the 27th annual international symposium on Computer architecture, p.107-116, June 2000, Vancouver, British Columbia, Canada
• 6: G. Hammond, S. Naffziger, "Next Generation Itanium Process Overview", Intel Developers Forum, 2001
• 7: P. Franaszek , J. Robinson , J. Thomas, Parallel compression with cooperative dictionary construction, Proceedings of the Conference on Data Compression, p.200, March 31-April 03, 1996
• 8: N. Kim, T. Austin, T. Mudge, "Low-Energy Data Cache using Sign Compression and Cache Line Bisection", 2nd Annual Workshop on Memory Performance Issues, May 2002
• 9: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: M. Kjelso, M. Gooch, S. Jones, "Design and Performance of a Main Memory Hardware Data Compressor", In the proceedings of the 22nd EUROMICRO Conference, Beyond 2000: Hardware and Software Design Strategies, 1995, pp. 423--430.
• 11: Jang-Soo Lee , Won-Kee Hong , Shin-Dug Kim, An on-chip cache compression technique to reduce decompression overhead and design complexity, Journal of Systems Architecture: the EUROMICRO Journal, v.46 n.15, p.1365-1382, Dec. 31 2000 [doi>10.1016/S1383-7621(00)00030-8]
• 12: Charles Lefurgy , Eva Piccininni , Trevor Mudge, Evaluation of a high performance code compression method, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.93-102, November 16-18, 1999, Haifa, Israel
• 13: Haris Lekatsas , Wayne Wolf, Code compression for embedded systems, Proceedings of the 35th annual conference on Design automation, p.516-521, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277185]
• 14: Sumit Roy , Raj Kumar , Milos Prvulovic, Improving System Performance with Compressed Memory, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.66, April 23-27, 2001
• 15: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 16: Luis Villa , Michael Zhang , Krste Asanović, Dynamic zero compression for cache energy reduction, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.214-220, December 2000, Monterey, California, United States [doi>10.1145/360128.360150]
• 17: P. R. Wilson, S. F. Kaplan, Y. Smaragdakis, "The Case for Compressed Caching in Virtual Memory Systems", In the proceedings of USENIX 1999.
• 18: Jun Yang , Rajiv Gupta, Energy efficient frequent value data cache design, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 19: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.0 General