Energy aware lossless data compression

ABSTRACT

Wireless transmission of a bit can require over 1000 times more energy than a single 32-bit computation. It would therefore seem desirable to perform significant 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 consequently, a longer battery life for portable computers. This paper reports on the energy of lossless data compressors as measured on a StrongARM SA-110 system. We show that with several typical compression tools, there is a net energy increase when compression is applied before transmission. Reasons for this increase are explained, and hardware-aware programming optimizations are demonstrated. When applied to Unix compress, these optimizations improve energy efficiency by 51%. We also explore the fact that, for many usage models, compression and decompression need not be performed by the same algorithm. By choosing the lowest-energy compressor and decompressor on the test platform, rather than using default levels of compression, overall energy to send compressible web data can be reduced 31%. Energy to send harder-to-compress English text can be reduced 57%. Compared with a system using a single optimized application for both compression and decompression, the asymmetric scheme saves 11% or 12% of the total energy depending on the dataset.

REFERENCES

• 1: Advanced RISC Machines Ltd (ARM). Writing Efficient C for ARM, Jan. 1998. Application Note 34.
• 2: T.M. Austin and D. C. Burger. SimpleScalar version 4.0 release. Tutorial in conjunction with 34th Annual International Symposium on Microarchitecture, Dec. 2001.
• 3: T. Bell and D. Kulp. Longest match string searching for Ziv-Lempel compression. Technical Report 06/89, Department of Computer Science, University of Canterbury, New Zealand, 1989.
• 4: T. Bell, M. Powell, J. Horlor, and R. Arnold. The Canterbury Corpus. http://www.corpus.canterbury.ac.nz/.
• 5: 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]
• 6: 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]
• 7: D. C. Burger and T. M. Austin. The SimpleScalar tool set, version 2.0. Technical Report CS-TR-97-1342, University of Wisconsin, Madison, June 1997.
• 8: M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, Digital Systems Research Center, May 1994.
• 9: J. Gailly and M. Adler. zlib. http://www.gzip.org/zlib.
• 10: J. Gailly, Maintainer. comp. compression Internet newsgroup: Frequently Asked Questions, Sept. 1999.
• 11: J. Gilchrist. Archive comparison test. http://compression.ca.
• 12: P. J. Havinga. Energy efficiency of error correction on wireless systems. In IEEE Wireless Communications and Networking Conference, Sept. 1999.
• 13: J. Hicks et al. Compaq personal server project, 1999. http://crl.research.compaq.com/projects/personalserver/default.htm.
• 14: 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]
• 15: 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
• 16: Hyperspace Communications, Inc. Mod-gzip. http://www.ehyperspace.com /htmlonly/products/mod_gzip.html.
• 17: Intel Corporation. SA-110 Microprocessor Technical Reference Manual, December 2000.
• 18: Intel Corporation. Intel StrongARM SA-1110 Microprocessor Developer's Manual, October 2001.
• 19: V. Jacobson. RFC 1144: Compressing TCP/IP headers for low-speed serial links, Feb. 1990.
• 20: K. Jamieson. Implementation of a power-saving protocol for ad hoc wireless networks. Master's thesis, Massachusetts Institute of Technology, Feb. 2002.
• 21: P. Jannesen et. al. (n)compress. available, among other places, in Redhat 7.2 distribution of Linux.
• 22: K. Koskelin, K. Barr, and K. Asanović. Eprof: An energy profiler for the iPaq. In 2nd Annual Student Oxygen Workshop. MIT Project Oxygen, 2002.
• 23: R. Krashinsky. Efficient web browsing for mobile clients using HTTP compression. Technical Report MIT-LCS-TR-882, MIT Lab for Computer Science, Jan. 2003.
• 24: 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]
• 25: Lycos. Lycos 50, Sept. 2002. Top 50 searches on Lycos for the week ending September 21, 2002.
• 26: 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]
• 27: J. C. Mogul. Trace-based analysis of duplicate suppression in HTTP. Technical Report 99.2, Compaq Computer Corporation, Nov. 1999.
• 28: J. C. Mogul, F. Douglis, A. Feldmann, and B. Krishnamurthy. Potential benefits of delta encoding and data compression for HTTP. Technical Report 97/4a, Compaq Computer Corporation, Dec. 1997.
• 29: J. Montanaro et al. A 160-mhz, 32-b, 0.5-w CMOS RISC microprocessor. IEEE Journal of Solid-State Circuits, 31(11), Nov. 1996.
• 30: Network Conscious Text Compression System (NCTCSys), Proceedings of the International Conference on Information Technology: Coding and Computing, p.440, April 02-04, 2001
• 31: 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
• 32: Nielsen NetRatings Audience Measurement Service. Top 25 U.S Properties; Week of Sept 15th., Sept. 2002.
• 33: M. F. Oberhumer. LZO. http://www.oberhumer.com/opensource/lzo/.
• 34: 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
• 35: J. Santos and D. Wetherall. Increasing effective link bandwidth by suppressing replicated data. In USENIX Annual Technical Conference, June 1998.
• 36: Khalid Sayood, Introduction to data compression (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 37: J. Seward. bzip2. http://www.spec.org/osg/cpu2000/CINT2000/256.bzip2/docs/256.bzip2.html.
• 38: J. Seward. e2comp bzip2 library. http://cvs.bofh.asn.au/e2compr/index.html.
• 39: A. Shacham, B. Monsour, R. Pereira, and M. Thomas. RFC 3173: IP payload compression protocol, Sept. 2001.
• 40: D. Shkarin. PPMd. ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdi1.rar.
• 41: 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]
• 42: Standard Performance Evaluation Corporation. CPU2000, 2000.
• 43: C. N. Taylor and S. Dey. Adaptive image compression for wireless multimedia communication. In IEEE International Conference on Communication, June 2001.
• 44: A. Tridgell. Efficient Algorithms for Sorting and Synchronization. PhD thesis, Australian National University, Apr. 2000.
• 45: 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]
• 46: 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]
• 47: M. A. Viredaz and D. A. Wallach. Power evaluation of Itsy version 2.4. Technical Report TN-59, Compaq Computer Corporation, February 2001.
• 48: H. Yang, G. R. Gao, A. Marquez, G. Cai, and Z. Hu. Power and energy impact of loop transformations. In Workshop on Compilers and Operating Systems for Low Power 2001, Parallel Architecture and Compilation Techniques, Sept. 2001.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design