The performance advantage of applying compression to the memory system

ABSTRACT

The memory system stores information comprising primarily instructions and data and secondarily address information, such as cache tag fields. It interacts with the processor by supporting related traffic (again comprising addresses, instructions, and data). Continuing exponential growth in processor performance, combined with technology, architecture, and application trends, place enormous demands on the memory system to permit this information storage and exchange at a high-enough performance (i.e., to provide low latency and high bandwidth access to large amounts of information). This paper comprehensively analyzes the redundancy in the information (addresses, instructions, and data) stored and exchanged between the processor and the memory system and evaluates the potential of compression in improving performance of the memory system. Analysis of traces obtained with Sun Microsystems' Shade simulator simulating SPARC executables of nine integer and six floating-point programs in the SPEC CPU2000 benchmark suite yield impressive results. Well-designed compression schemes may provide benefits in performance that far outweigh the extra time and logic for compression and decompression. This will be more so in the future since the speed and size of logic (which will be used to perform compression/decompression) are improving and are projected to improve at a much higher rate compared to those of interconnect (which will be used to communicate the information), both on-chip and off-chip.

REFERENCES

• 1: Advanced RISC Machines. An Introduction to Thumb, Mar. 1995. Available at: http://www.arm.com.
• 2: Jeffrey C. Becker , Arvin Park , Matthew Farrens, An analysis of the information content of address reference streams, Proceedings of the 24th annual international symposium on Microarchitecture, p.19-24, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123470]
• 3: D. Citron , L. Rudolph, Creating a wider bus using caching techniques, Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture, p.90, January 22-25, 1995
• 4: Bob Cmelik , David Keppel, Shade: a fast instruction-set simulator for execution profiling, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.128-137, May 1994
• 5: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: P. Franaszek and J. Robinson. Design and Analysis of Internal Organizations for Compressed Random Access Memories. Technical Report IBM Research Report RC 21146(94535)20OCT98, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, Oct. 1998.
• 7: M. Game and A. Booker. Codepack{tm}: Code Compression for PowerPC Processors. IBM White Paper available at: http://www.3.ibm.com/chips/techlib/techlib.nsf/products/CodePack, May 2000.
• 8: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 9: K. Kissell. MIPS16: High-density MIPS for the Embedded Market. http://www.mips.com/Documentation/MIPS 16whitepaper.pdf, 1997.
• 10: M. Kjelso, M. Gooch, and S. Jones. Empirical Study of Memory-data: Characteristics and Compressibility. IEE Proceedings on Computers and Digital Techniques, 145(1):63--67, Jan. 1998.
• 11: Michael Kozuch , Andrew Wolfe, Compression of Embedded System Programs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.270-277, October 10-12, 1994
• 12: 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
• 13: C. Lefurgy and T. Mudge. Code Compression for DSP. Technical Report CSE-TR-380-98, EECS Department, University of Michigan, Ann Arbor, MI, 1998.
• 14: Haris Lekatsas , Wayne Wolf, Random Access Decompression using Binary Arithmetic Coding, Proceedings of the Conference on Data Compression, p.306, March 29-31, 1999
• 15: H. Lekatsas and W. Wolf. SAMC: A Code Compression algorithm for Embedded Processors. IEEE Transactions on Computer-aided Design, 18(12):1689--1701, Dec. 1999.
• 16: S. Nystrom, J. Runeson, and J. Sjodin. Code Compression Techniques for Embedded Systems, 2000.
• 17: Arvin Park , Matthew Farrens, Address compression through base register caching, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.193-199, November 27-29, 1990, Orlando, Florida, United States
• 18: David A. Patterson , John L. Hennessy, Computer organization & design: the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 19: Kevin Skadron , Pritpal S. Ahuja , Margaret Martonosi , Douglas W. Clark, Branch Prediction, Instruction-Window Size, and Cache Size: Performance Trade-Offs and Simulation Techniques, IEEE Transactions on Computers, v.48 n.11, p.1260-1281, November 1999 [doi>10.1109/12.811115 ]
• 20: Sun Microsystems. Introduction to Shade Ver5.34, 1997. http://www.sun.com/microelectronics/shade.
• 21: Tremaine, P. Franaszek, J. Robinson, C. Schulz, T. Smith, M. Wazlowski, and P. Bland. Ibm Memory eXpansion Technology (mxt). IBM Journal of Research and Development, 45(2):271--285, Mar. 2001.
• 22: 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]
• 23: Jenlong Wang , Russell W. Quong, The Feasibility of Using Compression to Increase Memory System Performance, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.107-113, January 31-February 02, 1994
• 24: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States
• 25: 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]

INDEX TERMS

Keywords:
Markov models, address compression, bandwidth, cache, data compression, entropy, instruction compression, latency, lossless compression, memory, register file, storage, traffic