An analytical model for software-only main memory compression

ABSTRACT

Many applications with large data spaces that cannot run on a typical workstation (due to page faults) call for techniques to expand the effective memory size. One such technique is memory compression.Understanding what applications under what conditions can benefit from main memory compression is complicated due to various tradeoffs and the dynamic characteristics of applications. For instance, a large area to store compressed data increases the effective memory size considerably but also decreases the amount of memory that can hold uncompressed data.This paper presents an analytical model that states the conditions for a compressed-memory system to yield performance improvements. Parameters of the model are the compression algorithm efficiency, the amount of data being compressed, and the application memory access pattern. Such a model can be used by an operating system to compute the size of the compressed-memory level that can improve an application's performance.

REFERENCES

• 1: 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
• 2: R. Cervera, T. Cortes, and Y. Becerra. Improving Application Performance through Swap Compression. In Proc. 1999 USENIX Tech. Conf: FREENIX Track, pages 207--218, Monterey, CA, June 1999.
• 3: I. Chihaia and T. Gross. Adaptive Main Memory Compression. Technical report, ETH Zurich, 2004.
• 4: I. Chihaia and T. Gross. Effectiveness of Simple Memory Models for Performance Prediction. In Proc. ISPASS, pages 98--105, Austin, TX, March 2004. IEEE.
• 5: Rodrigo S. de Castro , Alair Pereira do Lago , Dilma Da Silva, Adaptive Compressed Caching: Design and Implementation, Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing, p.10, November 10-12, 2003
• 6: F. Douglis. The Compression Cache: Using On-line Compression to Extend Physical Memory. In Proc. Winter USENIX Conference, pages 519--529, San Diego, CA, Jan. 1993.
• 7: Michael J. Flynn, Computer Architecture: Pipelined and Parallel Processor Design, Jones and Bartlett Publishers, Inc., 1995
• 8: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 9: Scott Frederick Kaplan , Paul R. Wilson , Donald S. Fussell, Compressed caching and modern virtual memory simulation, 1999
• 10: M. Kjelso, M. Gooch, and S. Jones. Design and Performance of a Main Memory Hardware Compressor. In Proc. 22nd Euromicro Conf., pages 423--430. IEEE Computer Society Press, Sept. 1996.
• 11: M. Kjelso, M. Gooch, and S. Jones, Performance Evaluation of Computer Architectures with Main Memory Data Compression. Journal of Systems Architecture, 45:571--590, 1999.
• 12: V. Schuppan and A. Biere. A Simple Verification of the Tree Identify Protocol with SMV. In Proc. IEEE 1394 (FireWire) Workshop, pages 31--34, Berlin, Germany, March 2001.
• 13: The Network Simulator - NS2. http://www.isi.edu/nsnam/ns/.
• 14: Symbolic Model Verifier. http://www-2.cs.cmu.edu/bwolen/software/.
• 15: P. Wilson. Operating System Support for Small Objects. In Workshop on Object Orientation in Operating Systems, pages 80--86, Palo Alto, CA, Oct. 1991. IEEE.
• 16: P. Wilson, S. Kaplan, and Y. Smaragdakis. The Case for Compressed Caching in Virtual Memory Systems. In Proc. 1999 USENIX Tech. Conf., pages 101--116, Monterey, CA, June 1999.
• 17: Bwolen Yang , Randal E. Bryant , David R. O'Hallaron , Armin Biere , Olivier Coudert , Geert Janssen , Rajeev K. Ranjan , Fabio Somenzi, A Performance Study of BDD-Based Model Checking, Proceedings of the Second International Conference on Formal Methods in Computer-Aided Design, p.255-289, November 04-06, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Main memory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Measurement, Performance