High-performance operating system controlled online memory compression

Abstract

Online memory compression is a technology that increases the amount of memory available to applications by dynamically compressing and decompressing their working datasets on demand. It has proven extremely useful in embedded systems with tight physical RAM constraints. The technology can be used to increase functionality, reduce size, and reduce cost, without modifying applications or hardware. This article presents a new software-based online memory compression algorithm for embedded systems. In comparison with the best algorithms used in online memory compression, our new algorithm has a competitive compression ratio but is twice as fast. In addition, we describe several practical problems encountered in developing an online memory compression infrastructure and present solutions. We present a method of adaptively managing the uncompressed and compressed memory regions during application execution. This memory management scheme adapts to the predicted memory requirements of applications. It permits efficient compression for a wide range of applications. We have evaluated our techniques on a portable embedded device and have found that the memory available to applications can be increased by 2.5× with negligible performance and power consumption penalties, and with no changes to hardware or applications. Our techniques allow existing applications to execute with less physical memory. They also allow applications with larger working datasets to execute on unchanged embedded system hardware, thereby increasing functionality.

References

1. Benini, L., Bruni, D., Macii, A., and Macii, E. 2002. Hardware-Assisted data compression for energy minimization in systems with embedded processors. In Proceedings of the Design, Automation and Test in Europe Conference.
2. Benini, L., Bruni, D., Macii, A., and Macii, E. 2004. Memory energy minimization by data compression: Algorithms, architectures and implementation. IEEE Trans. VLSI Syst. 12, 3, 255--267.
3. Compressed Caching. Compressed caching in Linux virtual memory. http://linuxcompressed.sourceforge.net.
4. Cortes, T., Becerra, Y., and Cervera, R. 2000. Swap compression: Resurrecting old ideas. Softw. Pract. Exper. J. 30, 567--587.
5. Douglis, F. 1993. The compression cache: Using on-line compression to extend physical memory. In Proceedings of the USENIX Conference. 519--529.
6. Kjelso, M., Gooch, M., and Jones, S. 1996. Design and performance of a main memory hardware data compressor. In Proceedings of the Euromicro Conference. 423--430.
7. Kjelso, M., Gooch, M., and Jones, S. 1999. Performance evaluation of computer architectures with main memory data compression. J. Syst. Archit. 45, 571--590.
8. Lee, C., Potkonjak, M., and Smith, W. H. M. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems. http://cares.icsl.ucla.edu/MediaBench.
9. Lefurgy, C., Piccininni, E., and Mudge, T. N. 2000. Reducing code size with run-time decompression. In Proceedings of the International Symposium on High-Performance Computer Architecture. 218.
10. Lekatsas, H., Henkel, J., and Wolf, W. 2000. Code compression for low power embedded system design. In Proceedings of the Design Automation Conference. 294--299.
11. Leon-Garcia, A. 1989. Probability and Random Processes for Electrical Engineering. Addison-Wesley.
12. Moore, K. E. 2003. Compressing memory management in a device. U.S. patent, Hewlett-Packard Development Company, LP. May.
13. Oberhumer, M. F. LZO real-time data compression library. http://www.oberhumer.com/opensource/lzo.
14. Rizzo, L. 1997. A very fast algorithm for RAM compression. Oper. Syst. Rev. 31, 2, 36--45.
15. Roy, S., Kumar, R., and Prvulovic, M. 2001. Improving system performance with compressed memory. In Proceedings of the Parallel and Distributed Processing Symposium.
16. Russinovich, M. and Cogswell, B. 1996. RAM compression analysis. http://ftp.uni-mannheim.de/info/OReilly/windows/win95.update/model.html.
17. Shaw, C., Chatterji, D., Sen, P. M. S., Roy, B. N., and Chauduri, P. P. 2003. A pipeline architecture for encompression (encryption + compression) technology. In Proceedings of the International Conference on VLSI Design.
18. Tremaine, B., Franaszek, P. A., Robinson, J. T., Schulz, C. O., Smith, T. B., Wazlowski, M., and Bland, P. M. 2001. IBM memory expansion technology. IBM J. Res. Devel. 45, 2, 271--285.
19. Tuduce, I. C. and Gross, T. 2005. Adaptive main memory compression. In Proceedings of the USENIX Conference 237--250.
20. Vahalia, U. 1996. UNIX Internals: The New Frontiers. Prentice-Hall, NJ.
21. Wilson, P. R., Kaplan, S. F., and Smaragdakis, Y. 1999. The case for compressed caching in virtual memory systems. In Proceedings of the USENIX Conference. 101--116.
22. Xu, X. H., Clarke, C. T., and Jones, S. R. 2004. High performance code compression architecture for the embedded ARM/Thumb processor. In Proceedings of the Conference on Computing Frontiers. 451--456.
23. Yang, L., Dick, R. P., Lekatsas, H., and Chakradhar, S. 2005. CRAMES: Compressed RAM for embedded systems. In Proceedings of the International Conference Hardware/Software Codesign and System Synthesis.
24. Yang, L., Lekatsas, H., and Dick, R. P. 2006. High-performance operating system controlled memory compression. In Proceedings of the Design Automation Conference. 701--704.
25. Ziv, J. and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 3, 337--343.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Virtual memory