USENIX AssociationProceedings of MobiSys 2003:The First International Conference onMobile Systems, Applications, and ServicesSan Francisco, CA, USAMay 5-8, 2003© 2003 by The USENIX Association All Rights Reserved For more information about the USENIX Association:Phone: 1 510 528 8649 FAX: 1 510 548 5738 Email: [email protected] WWW: http://www.usenix.orgRights to individual papers remain with the author or the author's employer. Permission is granted for noncommercial reproduction of the work for educational or research purposes.This copyright notice must be included in the reproduced paper. USENIX acknowledges all trademarks herein.MobiSys 2003: The First International Conference on Mobile Systems, Applications, and Services USENIX Association231Energy Aware Lossless Data CompressionKenneth Barr and Krste Asanovi´cMIT Laboratory for Computer Science200 Technology Square, Cambridge, MA 02139E-mail: {kbarr,krste}@lcs.mit.eduAbstractWireless transmission of a bit can require over 1000 times more energy than a single 32-bit computation. It wouldtherefore seem desirable to perform significant computation to reduce the number of bits transmitted. If the energyrequired 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 mea-sured on a StrongARM SA-110 system. We show that with several typical compression tools, there is a net energyincrease 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 improveenergy efficiency by 51%. We also explore the fact that, for many usage models, compression and decompressionneed not be performed by the same algorithm. By choosing the lowest-energy compressor and decompressor on thetest platform, rather than using default levels of compression, overall energy to send compressible web data can bereduced 31%. Energy to send harder-to-compress English text can be reduced 57%. Compared with a system using asingle optimized application for both compression and decompression, the asymmetric scheme saves 11% or 12% ofthe total energy depending on the dataset.1 IntroductionWireless communication is an essential component ofmobile computing, but the energy required for transmis-sion of a single bit has been measured to be over 1000times greater than a single 32-bit computation. Thus, if1000 computation operations can compress data by evenone bit, energy should be saved. However, accessingmemory can be over 200 times more costly than compu-tation on our test platform, and it is memory access thatdominates most lossless data compression algorithms. Infact, even moderate compression (e.g. gzip -6) canrequire so many memory accesses that one observes anincrease in the overall energy required to send certaindata.While some types of data (e.g., audio and video) mayaccept some degradation in quality, other data must betransmitted faithfully with no loss of information. Fi-delity can not be sacrificed to reduce energy as is donein related work on lossy compression. Fortunately, anunderstanding of a program’s behavior and the energyrequired by major hardware components can be used toreduce energy. The ability to efficiently perform efficientlossless compression also provides second-order benefitssuch as reduction in packet loss and less contention forthe fixed wireless bandwidth. Concretely, if n bits havebeen compressed to m bits (n>m); c is the cost ofcompression and decompression; and w is the cost perbit of transmission and reception; compression is energyefficient ifcnm<w. This paper examines the elementsof this inequality and their relationships.We measure the energy requirements of several loss-less data compression schemes using the “Skiff” plat-form developed by Compaq Cambridge Research Labs.The Skiff is a StrongARM-based system designed withenergy measurement in mind. Energy usage for CPU,memory, network card, and peripherals can be measuredindividually. The platform is similar to the popular Com-paq iPAQ handheld computer, so the results are relevantto handheld hardware and developers of embedded soft-ware. Several families of compression algorithms are an-alyzed and characterized, and it is shown that carelesslyapplying compression prior to transmission may cause anoverall energy increase. Behaviors and resource-usagepatterns are highlighted which allow for energy-efficientlossless compression of data by applications or networkdrivers. We focus on situations in which the mixture ofhigh energy network operations and low energy proces-sor operations can be adjusted so that overall energy islower. This is possible even if the number of total opera-MobiSys 2003: The First International Conference on Mobile Systems, Applications, and Services USENIX Association232tions, or time to complete them, increases. Finally, a newenergy-aware data compression strategy composed of anasymmetric compressor and decompressor is presentedand measured.Section 2 describes the experimental setup includingequipment, workloads, and the choice of compressionapplications. Section 3 begins with the measurementof an encouraging communication-computation gap, butshows that modern compression tools do not exploitthe the low relative energy of computation versus com-munication. Factors which limit energy reduction arepresented. Section 4 applies an understanding of thesefactors to reduce overall energy of transmission thoughhardware-conscious optimizations and asymmetric com-pression choices. Section 5 discusses related work, andSection 6 concludes.2 Experimental setupWhile simulators may be tuned to provide reason-ably accurate estimations of a particular system’s energy,observing real hardware ensures that complex interac-tions of components are not overlooked or oversimpli-fied. This section gives a brief description of our hard-ware and software platform, the measurement methodol-ogy, and benchmarks.2.1 EquipmentThe Compaq Personal Server, codenamed “Skiff,” isessentially an initial, “spread-out” version of the Com-paq iPAQ built for research purposes [13]. Powered by a233 MHz StrongARM SA-110 [29, 17], the Skiff is com-putationally similar to the popular Compaq iPAQ hand-held (an SA-1110 [18] based device). For wireless net-working, we add a five volt