Energy-aware lossless data compression

ABSTRACT

Wireless transmission of a single bit can require over 1000 times more energy than a single computation. It can therefore be beneficial to perform additional computation to reduce the number of bits transmitted. If the energy required to compress data is less than the energy required to send it, there is a net energy savings and an increase in battery life for portable computers. This article presents a study of the energy savings possible by losslessly compressing data prior to transmission. A variety of algorithms were measured on a StrongARM SA-110 processor. This work demonstrates that, with several typical compression algorithms, there is a actually a net energy increase when compression is applied before transmission. Reasons for this increase are explained and suggestions are made to avoid it. One such energy-aware suggestion is asymmetric compression, the use of one compression algorithm on the transmit side and a different algorithm for the receive path. By choosing the lowest-energy compressor and decompressor on the test platform, overall energy to send and receive data can be reduced by 11% compared with a well-chosen symmetric pair, or up to 57% over the default symmetric zlib scheme.

REFERENCES

• 1: Advanced RISC Machines Ltd. (ARM). 1998. Writing Efficient C for ARM. Application note 34. Go online to www.arm.com/pdfs.
• 2: Agilent Technologies. 2000. Agilent 34401A Multimeter: User's Guide, 5th ed. Palo Alto, CA.
• 3: Austin, T. M. and Burger, D. C. 2001. SimpleScalar version 4.0 release (tutorial). In Proceedings of the 34th Annual International Symposium on Microarchitecture.
• 4: Banerjee, S. and Misra, A. 2004. Power adaptation based optimization for energy efficient reliable wireless paths. Tech. rep. Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI.
• 5: Bell, T. and Kulp, D. 1989. Longest match string searching for Ziv-Lempel compression. Tech. Rep. 06/89. Department of Computer Science, University of Canterbury, Christchurch New Zealand.
• 6: Bell, T., Powell, M., Horlor, J., and Arnold, R. 1997. The Canterbury Corpus. Go online to http://www.corpus.canterbury.ac.nz/.
• 7: Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989 [doi>10.1145/76894.76896]
• 8: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 9: Burger, D. C. and Austin, T. M. 1997. The SimpleScalar tool set, version 2.0. Tech. Rep. CS-TR-97-1342. University of Wisconsin, Madison, Madison, WI.
• 10: Burrows, M. and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124. Digital Systems Research Center, Palo Alto, CA.
• 11: Chang, F., Farkas, K., and Ranganathan, P. 2002. Energy-driven statistical profiling: Detecting software hotspots. In Proceedings of the 2nd Workshop on Power-Aware Computer Systems (HPCA-8).
• 12: Chang, J.-H. and Tassiulas, L. 2000. Energy conserving routing in wireless ad-hoc networks. In Proceedings of IEEE INFOCOM. 22--31.
• 13: Cleary, J. G. and Witten, I. H. 1984. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32, 4 (Apr.), 396--402.
• 14: D. J. Craft, A fast hardware data compression algorithm and some algorithmic extensions, IBM Journal of Research and Development, v.42 n.6, p.733-745, November 1998
• 15: Michelle Effros, PPM Performance with BWT Complexity: A New Method for Lossless Data Compression, Proceedings of the Conference on Data Compression, p.203, March 28-30, 2000
• 16: Jason Nelson Flinn , Mahadev Satyanarayanan, Extending mobile computer battery life through energy-aware adaptation, 2001
• 17: Flinn, J., Farkas, K. I., and Anderson, J. 2000. Power and energy characterization of the Itsy pocket computer (version 1.5). Tech. Rep. TN-56. Compaq Computer Corporation, Houston, TX.
• 18: Jason Flinn , M. Satyanarayanan, PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.2, February 25-26, 1999
• 19: Gailly, J. 1999. Go online to comp.compression Internet newsgroup: Frequently Asked Questions.
• 20: Gailly, J. and Adler, M. 2002. zlib. Go online to http://www.gzip.org/zlib.
• 21: Gilchrist, J. 2002. Archive comparison test. Go online to http://compression.ca.
• 22: Havinga, P. J. 1999. Energy efficiency of error correction on wireless systems. In Proceedings of the IEEE Wireless Communications and Networking Conference.
• 23: Hicks, J. 2005. Director, MIT-Quanta T-Party Project. Personal communication.
• 24: Hicks, J. et al. 1999. Compaq personal server project. Go online to http://crl.research.compaq.com/projects/personalserver/default.htm.
• 25: Barbara Hohlt , Lance Doherty , Eric Brewer, Flexible power scheduling for sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984653]
• 26: Barron C. Housel , David B. Lindquist, WebExpress: a system for optimizing Web browsing in a wireless environment, Proceedings of the 2nd annual international conference on Mobile computing and networking, p.108-116, November 1996, Rye, New York, United States [doi>10.1145/236387.236416]
• 27: James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, An Empirical Study of Delta Algorithms, Proceedings of the SCM-6 Workshop on System Configuration Management, p.49-66, March 25-26, 1996
• 28: IBM. 2001. IBM J. Res. Devel. 45, 2. Preface by Richard E. Harper, Guest Editor.
• 29: Intel Corporation. 2000. SA-110 Microprocessor Technical Reference Manual. Intel Corporation, Santa Clara, CA.
• 30: Intel Corporation. 2001. Intel StrongARM SA-1110 Microprocessor Developer's Manual. Intel Corporation, Santa Clara, CA.
• 31: V. Jacobson, Compressing TCP/IP headers for low-speed serial links, RFC Editor, 1990
• 32: Jamieson, K. 2002. Implementation of a power-saving protocol for ad hoc wireless networks. M.S. thesis. Massachusetts Institute of Technology, Cambridge, MA.
• 33: Jannesen, P. et. al 1996. (n)compress. Available, among other places, in Redhat 7.2 distribution of Linux.
• 34: Jung, B. and Burleson, W. P. 1994. A VLSI systolic array architecture for Lempel-Ziv based data compression. In Proceedings of the International Symposium on Circuits and Systems.
• 35: Bongjin Jung , W. P. Burleson, Real-time VLSI compression for high-speed wireless local area networks, Proceedings of the Conference on Data Compression, p.431, March 28-30, 1995
• 36: Krashinsky, R. 2003. Efficient Web browsing for mobile clients using HTTP compression. Tech. Rep. MIT-LCS-TR-882. MIT Laboratory for Computer Science, Combridge, MA.
• 37: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 38: Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987 [doi>10.1145/45072.45074]
• 39: Jeremy Lilley , Jason Yang , Hari Balakrishnan , Srinivasan Seshan, A unified header compression framework for low-bandwidth links, Proceedings of the 6th annual international conference on Mobile computing and networking, p.131-142, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345933]
• 40: Lycos. 2002. Lycos 50. Top 50 searches on Lycos for the week ending September 21, 2002.
• 41: McEliece, R. 1977. The theory of information and coding. In Encyclopedia of Mathematics and Its Application. Vol. 3. Addison-Wesley, Reading, MA.
• 42: Akihiko Miyoshi , Charles Lefurgy , Eric Van Hensbergen , Ram Rajamony , Raj Rajkumar, Critical power slope: understanding the runtime effects of frequency scaling, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514200]
• 43: Mogul, J. C. 1999. Trace-based analysis of duplicate suppression in HTTP. Tech. Rep. 99.2. Compaq Computer Corporation, Houston, TX.
• 44: Mogul, J. C., Douglis, F., Feldmann, A., and Krishnamurthy, B. 1997. Potential benefits of delta encoding and data compression for HTTP. Tech. Rep. 97/4a. Compaq Computer Corporation, Houston, TX.
• 45: Montanaro et al., J. 1996. A 160-MHz, 32-b, 0.5-W CMOS RISC microprocessor. IEEE J. Sol.-State Circ. 31, 11 (Nov.), 1703--1714.
• 46: Network Conscious Text Compression System (NCTCSys), Proceedings of the International Conference on Information Technology: Coding and Computing, p.440, April 02-04, 2001
• 47: Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 48: Nathuji, R. 2000. Characterization of DRAM. MIT Advanced Undergraduate Project. Massachusetts Institute of Technology, Cambridge, MA.
• 49: Nielsen NetRatings Audience Measurement Service. 2002. Top 25 U.S Properties; Week of Sept. 15th. Go online to www.nielsen-netratings.com.
• 50: B. D. Noble , M. Satyanarayanan, Experience with adaptive mobile applications in Odyssey, Mobile Networks and Applications, v.4 n.4, p.245-254, Dec. 1999 [doi>10.1023/A:1019159101405]
• 51: Oberhumer, M. F. 2000. Lzo. Go on line to http://www.oberhumer.com/opensource/lzo/.
• 52: A. Peymandoust , T. Simunic , G. de Micheli, Low Power Embedded Software Optimization Using Symbolic Algebra, Proceedings of the conference on Design, automation and test in Europe, p.1052, March 04-08, 2002
• 53: Santos, J. and Wetherall, D. 1998. Increasing effective link bandwidth by suppressing replicated data. In Proceedings of the USENIX Annual Technical Conference. 213--224.
• 54: Khalid Sayood, Introduction to data compression (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 55: Seward, J. 1999. bzip2. Go online to http://www.spec.org/osg/cpu2000/CINT2000/256.bzip2/docs/256.bzip2.html.
• 56: Seward, J. 2000. e2comp bzip2 library. Go online to http://cvs.bofh.asn.au/e2compr/ index.html.
• 57: A. Shacham , B. Monsour , R. Pereira , M. Thomas, IP Payload Compression Protocol (IPComp), RFC Editor, 2001
• 58: Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423 and 623--656.
• 59: Dmitry Shkarin, PPM: One Step to Practicality, Proceedings of the Data Compression Conference (DCC '02), p.202, April 02-04, 2002
• 60: Shkarin, D. 2002b. PPMd. Go online to ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdi1.rar.
• 61: Tajana Simunic , Luca Benini , Giovanni De Micheli, Energy-efficient design of battery-powered embedded systems, Proceedings of the 1999 international symposium on Low power electronics and design, p.212-217, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313928]
• 62: Tajana Šimunić , Luca Benini , Giovanni De Micheli , Mat Hans, Source code optimization and profiling of energy consumption in embedded systems, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain [doi>10.1145/501790.501831]
• 63: Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
• 64: Amit Sinha , Alice Wang , Anantha P. Chandrakasan, Algorithmic transforms for efficient energy scalable computation, Proceedings of the 2000 international symposium on Low power electronics and design, p.31-36, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344188]
• 65: Standard Performance Evaluation Corporation. 2000. CPU2000. Go online to www.spec.org.
• 66: Taylor, C. N. and Dey, S. 2001. Adaptive image compression for wireless multimedia communication. In Proceedings of the IEEE International Conference on Communication.
• 67: Clark Thomborson, The V.42bis Standard for Data-Compressing Modems, IEEE Micro, v.12 n.5, p.41-53, September 1992 [doi>10.1109/40.166712]
• 68: Tridgell, A. 2000. Efficient algorithms for sorting and synchronization. Ph.D. dissertation. Australian National University, Canberra, Australia.
• 69: Viredaz, M. A. and Wallach, D. A. 2000. Power evaluation of Itsy version 2.3. Tech. Rep. TN-57. Compaq Computer Corporation, Houston, TX.
• 70: Viredaz, M. A. and Wallach, D. A. 2001. Power evaluation of Itsy version 2.4. Tech. Rep. TN-59. Compaq Computer Corporation, Houston, TX.
• 71: Welch, T. A. 1984. A technique for high-performance data compression. IEEE Comput. 17, 6, 8--19.
• 72: 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
• 73: Yang, H., Gao, G. R., Marquez, A., Cai, G., and Hu, Z. 2001. Power and energy impact of loop transformations. In Proceedings of the Workshop on Compilers and Operating Systems for Low Power 2001, Parallel Architecture and Compilation Techniques.
• 74: Ziv, J. and Lempel, A. 1977. A universal algorithm for data compression. IEEE Trans. Inform. Theor. 23, 3 (May), 337--343.
• 75: Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable rate coding. IEEE Trans. Inform. Theor. 24, 5 (Sep.), 530--536.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Measurement, Performance

Keywords:
Compression, energy-aware, lossless, low-power, power-aware