Kenneth C. Barr
Skip Abstract Section
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.
- Advanced RISC Machines Ltd. (ARM). 1998. Writing Efficient C for ARM. Application note 34. Go online to www.arm.com/pdfs.]]Google Scholar
- Agilent Technologies. 2000. Agilent 34401A Multimeter: User's Guide, 5th ed. Palo Alto, CA.]]Google Scholar
- Austin, T. M. and Burger, D. C. 2001. SimpleScalar version 4.0 release (tutorial). In Proceedings of the 34th Annual International Symposium on Microarchitecture.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- Bell, T., Powell, M., Horlor, J., and Arnold, R. 1997. The Canterbury Corpus. Go online to http://www.corpus.canterbury.ac.nz/.]]Google Scholar
- Bell, T., Witten, I. H., and Cleary, J. G. 1989. Modeling for text compression. ACM Comput. Surv. 21, 4, 557--591.]] Google Scholar
- Bilmes, J., Asanović, K., Chin, C.-W., and Demmel, J. 1997. Optimizing matrix multiply using PHiPAC: A portable, high-performance, ANSI C coding methodology. In Proceedings of the 11th ACM International Conference on Supercomputing.]] Google Scholar
- 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.]]Google Scholar
- Burrows, M. and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124. Digital Systems Research Center, Palo Alto, CA.]]Google Scholar
- 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).]]Google Scholar
- Chang, J.-H. and Tassiulas, L. 2000. Energy conserving routing in wireless ad-hoc networks. In Proceedings of IEEE INFOCOM. 22--31.]]Google Scholar
- 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.]]Google Scholar
- Craft, D. J. 1998. Data compression in ASIC cores. IBM J. Res. Devel. 42, 6.]] Google Scholar
- Effros, M. 2000. PPM performance with BWT complexity: A new method for lossless data compression. In Proceedings of the Data Compression Conference.]] Google Scholar
- Flinn, J. 2001. Extending mobile computer battery life through energy-aware adaptation. Ph.D. dissetation. Carnegie Mellon University, Pittsburgh, PA. Also Tech. rep. TR No. CMU-CS-01-171, Computer Science Depatment, Carnegie Mellan University.]] Google Scholar
- 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.]]Google Scholar
- Flinn, J. and Satyanarayanan, M. 1999. Powerscope: A tool for profiling the energy usage of mobile applications. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.]] Google Scholar
- Gailly, J. 1999. Go online to comp.compression Internet newsgroup: Frequently Asked Questions.]]Google Scholar
- Gailly, J. and Adler, M. 2002. zlib. Go online to http://www.gzip.org/zlib.]]Google Scholar
- Gilchrist, J. 2002. Archive comparison test. Go online to http://compression.ca.]]Google Scholar
- Havinga, P. J. 1999. Energy efficiency of error correction on wireless systems. In Proceedings of the IEEE Wireless Communications and Networking Conference.]]Google Scholar
- Hicks, J. 2005. Director, MIT-Quanta T-Party Project. Personal communication.]]Google Scholar
- Hicks, J. et al. 1999. Compaq personal server project. Go online to http://crl.research.compaq.com/projects/personalserver/default.htm.]]Google Scholar
- Hohlt, B., Doherty, L., and Brewer, E. 2004. Flexible power scheduling for sensor networks. In Proceedings of the IEEE and ACM Third International Symposium on Information Processing in Sensor Networks.]] Google Scholar
- Housel, B. C. and Lindquist, D. B. 1996. Webexpress: A system for optimizing Web browsing in a wireless environment. In Proceedings of the Second Annual International Conference on Mobile Computing and Networking. 108--116.]] Google Scholar
- Hunt, J. J., Vo, K.-P., and Tichy, W. F. 1996. An empirical study of delta algorithms. In Software Configuration Management: ICSE 96 SCM-6 Workshop. Springer, Berlin, Germany, 49--66.]] Google Scholar
- IBM. 2001. IBM J. Res. Devel. 45, 2. Preface by Richard E. Harper, Guest Editor.]]Google Scholar
- Intel Corporation. 2000. SA-110 Microprocessor Technical Reference Manual. Intel Corporation, Santa Clara, CA.]]Google Scholar
- Intel Corporation. 2001. Intel StrongARM SA-1110 Microprocessor Developer's Manual. Intel Corporation, Santa Clara, CA.]]Google Scholar
- Jacobson, V. 1990. RFC 1144: Compressing TCP/IP headers for low-speed serial links. Available online at www.rfe-editer.org.]] Google Scholar
- Jamieson, K. 2002. Implementation of a power-saving protocol for ad hoc wireless networks. M.S. thesis. Massachusetts Institute of Technology, Cambridge, MA.]]Google Scholar
- Jannesen, P. et. al 1996. (n)compress. Available, among other places, in Redhat 7.2 distribution of Linux.]]Google Scholar
- 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.]]Google Scholar
- Jung, B. and Burleson, W. P. 1995. Real-time VLSI compression for high-speed wireless local area networks. In Proceedings of the Data Compression Conference.]] Google Scholar
- 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.]]Google Scholar
- Lekatsas, H., Henkel, J., and Wolf, W. 2000. Low-power techniques for code compression in embedded systems. In Proceedings of the Design Automation Conference.]] Google Scholar
- Lelewer, D. A. and Hirschberg, D. S. 1987. Data compression. ACM Comput. Serv. 19, 3, 261--297.]] Google Scholar
- Lilley, J., Yang, J., Balakrishnan, H., and Seshan, S. 2000. A unified header compression framework for low-bandwidth links. In Proceedings of the 6th ACM MOBICOM.]] Google Scholar
- Lycos. 2002. Lycos 50. Top 50 searches on Lycos for the week ending September 21, 2002.]]Google Scholar
- McEliece, R. 1977. The theory of information and coding. In Encyclopedia of Mathematics and Its Application. Vol. 3. Addison-Wesley, Reading, MA.]]Google Scholar
- Miyoshi, A., Lefurgy, C., Hensbergen, E. V., Rajamony, R., and Rajkumar, R. 2002. Critical power slope: Understanding the runtime effects of frequency scaling. In Proceedings of the International Conference on Supercomputing.]] Google Scholar
- Mogul, J. C. 1999. Trace-based analysis of duplicate suppression in HTTP. Tech. Rep. 99.2. Compaq Computer Corporation, Houston, TX.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- Motgi, N. and Mukherjee, A. 2001. Network conscious text compression systems (NCTCSys). In Proceedings of the International Conference on Information and Theory: Coding and Computing.]] Google Scholar
- Muthitacharoen, A., Chen, B., and Mazières, D. 2001. A low-bandwidth network file system. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01, Chateau Lake Louise, Banff, Alta., Canada). 174--187.]] Google Scholar
- Nathuji, R. 2000. Characterization of DRAM. MIT Advanced Undergraduate Project. Massachusetts Institute of Technology, Cambridge, MA.]]Google Scholar
- Nielsen NetRatings Audience Measurement Service. 2002. Top 25 U.S Properties; Week of Sept. 15th. Go online to www.nielsen-netratings.com.]]Google Scholar
- Noble, B. D. and Satyanarayanan, M. 1999. Experience with adaptive mobile applications in odyssey. Mobile Netw. Appl. 4, 4, 245--254.]] Google Scholar
- Oberhumer, M. F. 2000. Lzo. Go on line to http://www.oberhumer.com/opensource/lzo/.]]Google Scholar
- Peymandoust, A., Simunić, T., and Micheli, G. D. 2002. Low power embedded software optimization using symbolic algebra. In Proceedings of the Conference on Design, Automation and Test in Europe.]] Google Scholar
- Santos, J. and Wetherall, D. 1998. Increasing effective link bandwidth by suppressing replicated data. In Proceedings of the USENIX Annual Technical Conference. 213--224.]] Google Scholar
- Sayood, K. 2002. Introduction to Data Compression, 2nd ed. Morgan Kaufman San Francisco, CA.]] Google Scholar
- Seward, J. 1999. bzip2. Go online to http://www.spec.org/osg/cpu2000/CINT2000/256.bzip2/docs/256.bzip2.html.]]Google Scholar
- Seward, J. 2000. e2comp bzip2 library. Go online to http://cvs.bofh.asn.au/e2compr/ index.html.]]Google Scholar
- Shacham, A., Monsour, B., Pereira, R., and Thomas, M. 2001. RFC 3173: IP payload compression protocol. Available online at www.rfc-editor.org/.]] Google Scholar
- Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423 and 623--656.]]Google Scholar
- Shkarin, D. 2002a. PPM: One step to practicality. In Proceedings of the Data Compression Conference.]] Google Scholar
- Shkarin, D. 2002b. PPMd. Go online to ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdi1.rar.]]Google Scholar
- Simunić, T., Benini, L., and Micheli, G. D. 1999. Energy-efficient design of battery-powered embedded systems. In Proceedings of the IEEE International Symposium on Low Power Electronics and Design.]] Google Scholar
- Simunić, T., Benini, L., Micheli, G. D., and Hans, M. 2000. Source code optimization and profiling of energy consumption in embedded systems. In Proceedings of the International Symposium on System Synthesis.]] Google Scholar
- Sinha, A. and Chandrakasan, A. 2001. Jouletrack---a Web based tool for software energy profiling. In Proceedings of the 38th Design Automation Conference.]] Google Scholar
- Sinha, A., Wang, A., and Chandrakasan, A. 2000. Algorithmic transforms for efficient energy scalable computation. In Proceedings of the IEEE International Symposium on Low Power Electronics and Design.]] Google Scholar
- Standard Performance Evaluation Corporation. 2000. CPU2000. Go online to www.spec.org.]]Google Scholar
- Taylor, C. N. and Dey, S. 2001. Adaptive image compression for wireless multimedia communication. In Proceedings of the IEEE International Conference on Communication.]]Google Scholar
- Thomborson, C. 1992. The V.42bis standard for data-compressing modems. IEEE Micro 12, 5.]] Google Scholar
- Tridgell, A. 2000. Efficient algorithms for sorting and synchronization. Ph.D. dissertation. Australian National University, Canberra, Australia.]]Google Scholar
- Viredaz, M. A. and Wallach, D. A. 2000. Power evaluation of Itsy version 2.3. Tech. Rep. TN-57. Compaq Computer Corporation, Houston, TX.]]Google Scholar
- Viredaz, M. A. and Wallach, D. A. 2001. Power evaluation of Itsy version 2.4. Tech. Rep. TN-59. Compaq Computer Corporation, Houston, TX.]]Google Scholar
- Welch, T. A. 1984. A technique for high-performance data compression. IEEE Comput. 17, 6, 8--19.]]Google Scholar
- Wolfe, A. and Chanin, A. 1992. Executing compressed programs on an embedded RISC architecture. In Proceedings of the 25th Annual International Symposium on Microarchitecture.]] Google Scholar
- 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.]]Google Scholar
- Ziv, J. and Lempel, A. 1977. A universal algorithm for data compression. IEEE Trans. Inform. Theor. 23, 3 (May), 337--343.]]Google Scholar
- Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable rate coding. IEEE Trans. Inform. Theor. 24, 5 (Sep.), 530--536.]]Google Scholar
Index Terms
- Energy-aware lossless data compression
Recommendations
Energy aware lossless data compression
MobiSys '03: Proceedings of the 1st international conference on Mobile systems, applications and servicesWireless 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 ...
Lossless compression of VLSI layout image data
We present a novel lossless compression algorithm called Context Copy Combinatorial Code (C4), which integrates the advantages of two very disparate compression techniques: context-based modeling and Lempel-Ziv (LZ) style copying. While the algorithm ...
Comments