research-article

Reducing Energy Consumption Using Genetic Improvement

Authors:

Bobby R. Bruce,

Mark HarmanAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1327 - 1334

https://doi.org/10.1145/2739480.2754752

Published: 11 July 2015 Publication History

Abstract

Genetic Improvement (GI) is an area of Search Based Software Engineering which seeks to improve software's non-functional properties by treating program code as if it were genetic material which is then evolved to produce more optimal solutions. Hitherto, the majority of focus has been on optimising program's execution time which, though important, is only one of many non-functional targets. The growth in mobile computing, cloud computing infrastructure, and ecological concerns are forcing developers to focus on the energy their software consumes. We report on investigations into using GI to automatically find more energy efficient versions of the MiniSAT Boolean satisfiability solver when specialising for three downstream applications. Our results find that GI can successfully be used to reduce energy consumption by up to 25%

References

[1]

M. Banbara, H. Matsunaka, N. Tamura, and K. Inoue. Generating combinatorial test cases by efficient SAT encodings suitable for CDCL SAT solvers. In Logic for Programming, Artificial Intelligence, and Reasoning, pages 112--126. Springer, 2010.

Digital Library

[2]

A. Banerjee, L. K. Chong, S. Chattopadhyay, and A. Roychoudhury. Detecting energy bugs and hotspots in mobile apps. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering - FSE 2014, pages 588--598, New York, New York, USA, Nov. 2014. ACM Press.

Digital Library

[3]

E. T. Barr, M. Harman, P. McMinn, M. Shahbaz, and S. Yoo. The oracle problem in software testing: A survey. IEEE Transactions on Software Engineering, 2015.

[4]

A. Biere, M. Heule, and H. van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009.

Digital Library

[5]

Boston Consulting Group. GeSI SMARTer2020: The role of ICT in driving a sustainable future. http://gesi.org/SMARTer2020, 2012. {Online; accessed 10-January-2015}.

[6]

A. R. Bradley, Z. Manna, and H. B. Sipma. Termination analysis of integer linear loops. In CONCUR 2005--Concurrency Theory, pages 488--502. Springer, 2005.

Digital Library

[7]

D. J. Brown and C. Reams. Toward energy-efficient computing. Communications of the ACM, 53(3):50--58, 2010.

Digital Library

[8]

C. Bunse, H. Höpfner, S. Roychoudhury, and E. Mansour. Choosing the" best" sorting algorithm for optimal energy consumption. ICSOFT, 2009.

[9]

P. Chen and K. Keutzer. Towards true crosstalk noise analysis. In Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, pages 132--138. IEEE Press, 1999.

Digital Library

[10]

M. Codish, I. Gonopolskiy, A. M. Ben-Amram, C. Fuhs, and J. Giesl. SAT-based termination analysis using monotonicity constraints over the integers. Theory and Practice of Logic Programming, 11(4--5):503--520, 2011.

[11]

H. David, E. Gorbatov, U. R. Hanebutte, R. Khanna, and C. Le. RAPL: Memory power estimation and capping. In Low-Power Electronics and Design (ISLPED), 2010 ACM/IEEE International Symposium on, pages 189--194, 2010.

Digital Library

[12]

N. Dershowitz, N. Lindenstrauss, Y. Sagiv, and A. Serebrenik. A general framework for automatic termination analysis of logic programs. Applicable Algebra in Engineering, Communication and Computing, 12(1--2):117--156, 2001.

[13]

C. Fuhs, J. Giesl, A. Middeldorp, P. Schneider-Kamp, R. Thiemann, and H. Zankl. SAT solving for termination analysis with polynomial interpretations. Springer, 2007.

[14]

M. Gabel and Z. Su. A study of the uniqueness of source code. In Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering - FSE '10, pages 147--156, New York, New York, USA, Nov. 2010. ACM Press.

Digital Library

[15]

J. Giesl. Termination analysis for functional programs using term orderings. In Static Analysis, pages 154--171. Springer, 1995.

Digital Library

[16]

J. Giesl, M. Brockschmidt, F. Emmes, F. Frohn, C. Fuhs, C. Otto, M. Plücker, P. Schneider-Kamp, T. Ströder, S. Swiderski, et al. Proving termination of programs automatically with AProVE. In IJCAR, volume 14, 2014.

[17]

J. Giesl, P. Schneider-Kamp, and R. Thiemann. AProVE 1.2: Automatic termination proofs in the dependency pair framework. In Automated Reasoning, pages 281--286. Springer, 2006.

Digital Library

[18]

J. Giesl, R. Thiemann, P. Schneider-Kamp, and S. Falke. Automated termination proofs with AProVE. In Rewriting Techniques and Applications, pages 210--220. Springer, 2004.

[19]

S. Hao, D. Li, W. G. J. Halfond, and R. Govindan. Estimating mobile application energy consumption using program analysis. In 2013 35th International Conference on Software Engineering (ICSE), pages 92--101. IEEE, May 2013.

Digital Library

[20]

M. Harman, W. B. Langdon, Y. Jia, D. R. White, A. Arcuri, and J. A. Clark. The GISMOE challenge: constructing the pareto program surface using genetic programming to find better programs. In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering - ASE 2012, pages 1--14, New York, New York, USA, Sept. 2012. ACM.

Digital Library

[21]

M. Harman, P. McMinn, J. T. De Souza, and S. Yoo. Search based software engineering: Techniques, taxonomy, tutorial. In Empirical software engineering and verification, pages 1--59. Springer, 2012.

[22]

J. Heggestuen. Business Insider: One In Every 5 People IN The World Own A Smartphone, One in Every 17 Own A Tablet. http://www.businessinsider.com/smartphone-and-tablet-penetration-2013--10, 2013. {Online; accessed 9-January-2015}.

[23]

M. J\"arvisalo, P. Kaski, M. Koivisto, and J. H. Korhonen. Finding efficient circuits for ensemble computation. In Theory and Applications of Satisfiability Testing--SAT 2012, pages 369--382. Springer, 2012.

Digital Library

[24]

H. Kautz and B. Selman. Planning as satisfiability. In Proceedings of the 10th European Conference on Artificial Intelligence (ECAI 92), pages 359--363, Vienna, Austria, 1992.

Digital Library

[25]

Z. Kocsis, G. Neumann, J. Swan, M. Epitropakis, A. E. Brownlee, S. O. Haraldsson, and E. Bowles. Repairing and optimizing Hadoop hashCode implementations. Search-Based Software Engineering, pages 259--264, 2014.

[26]

J. Koomey. Growth in data center electricity use from 2005 to 2010, Aug. 2011.

[27]

W. B. Langdon and M. Harman. Evolving a CUDA kernel from an nVidia template. In IEEE Congress on Evolutionary Computation, pages 1--8. IEEE, July 2010.

[28]

W. B. Langdon and M. Harman. Optimising existing software with genetic programming. IEEE Transactions on Evolutionary Computation, 2013.

[29]

C. Le Goues, S. Forrest, and W. Weimer. Current challenges in automatic software repair. Software Quality Journal, 21(3):421--443, 2013.

Digital Library

[30]

D. Li, S. Hao, W. G. J. Halfond, and R. Govindan. Calculating source line level energy information for android applications. In Proceedings of the 2013 International Symposium on Software Testing and Analysis - ISSTA 2013, pages 78 -- 89, New York, New York, USA, July 2013. ACM Press.

Digital Library

[31]

N. Lindenstrauss and Y. Sagiv. Automatic termination analysis of logic systems. In Logic Programming: Proceedings of the Fourteenth International Conference on Logic Programming, page 63. MIT Press, 1997.

[32]

S. Malik and L. Zhang. Boolean satisfiability: from theoretical hardness to practical success. Communications of the ACM, 52(8):76--82, 2009.

Digital Library

[33]

I. Manotas, L. Pollock, and J. Clause. SEEDS: a software engineer's energy-optimization decision support framework. In Proceedings of the 36th International Conference on Software Engineering - ICSE 2014, pages 503--514, New York, New York, USA, May 2014. ACM Press.

Digital Library

[34]

C. Nie and H. Leung. A survey of combinatorial testing. ACM Computing Surveys (CSUR), 43(2):11, 2011.

Digital Library

[35]

A. Pathak, Y. C. Hu, and M. Zhang. Where is the energy spent inside my app?: fine grained energy accounting on smartphones with eprof. In Proceedings of the 7th ACM european conference on Computer Systems - EuroSys '12, pages 29--42, New York, New York, USA, Apr. 2012. ACM Press.

Digital Library

[36]

J. Petke, W. B. Langdon, and M. Harman. Applying genetic improvement to MiniSAT. In Search Based Software Engineering, pages 257--262. Springer, 2013.

Digital Library

[37]

J. Petke, W. B. Langdon, M. Harman, and W. Weimer. Using genetic improvement & code transplants to specialise a C

[38]

program to a problem class. In M. Nicolau, K. Krawiec, and M. Heywood, editors, Proceedings of the 17th European Conference on Genetic Programming (EuroGP), Granada, Spain, 2014.

[39]

C. Sahin, L. Pollock, and J. Clause. How do code refactorings affect energy usage? In Proceedings of the 8th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement, page 36. ACM, 2014.

Digital Library

[40]

P. Schneider-Kamp, R. Thiemann, E. Annov, M. Codish, and J. Giesl. Proving termination using recursive path orders and SAT solving. In Frontiers of Combining Systems, pages 267--282. Springer, 2007.

Digital Library

[41]

E. Schulte, J. Dorn, S. Harding, S. Forrest, and W. Weimer. Post-compiler software optimization for reducing energy. Proceedings of the 19th international conference on Architectural support for programming languages and operating systems - ASPLOS '14, pages 639--652, 2014.

Digital Library

[42]

W. G. P. Silva, L. Brisolara, U. B. Corrêa, and L. Carro. Evaluation of the impact of code refactoring on embedded software efficiency. In Proceedings of the 1st Workshop de Sistemas Embarcados, pages 145--150, 2010.

[43]

The World Bank. http://data.worldbank.org/indicator/EN.ATM.CO2E.KT/countries. {Online; accessed 10-January-2015}.

[44]

C. Tucker, D. Shuffelton, R. Jhala, and S. Lerner. Opium: Optimal package install/uninstall manager. In Software Engineering, 2007. ICSE 2007. 29th International Conference on, pages 178--188. IEEE, 2007.

Digital Library

[45]

D. R. White, A. Arcuri, and J. A. Clark. Evolutionary improvement of programs. IEEE Transactions on Evolutionary Computation, 15(4):515--538, Aug. 2011.

Digital Library

[46]

D. R. White, J. Clark, J. Jacob, and S. M. Poulding. Searching for resource-efficient programs: Low-power pseudorandom number generators. In Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 1775--1782. ACM, 2008.

Digital Library

[47]

L. Zhang, B. Tiwana, Z. Qian, Z. Wang, R. P. Dick, Z. M. Mao, and L. Yang. Accurate online power estimation and automatic battery behavior based power model generation for smartphones. In Proceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis - CODES/ISSS '10, page 105, New York, New York, USA, Oct. 2010. ACM Press.

Digital Library

Cited By

Aragón-Jurado Jde la Torre JRuiz PDorronsoro B(2025)Automatic software tailoring for Green Internet of ThingsInternet of Things10.1016/j.iot.2025.10152130(101521)Online publication date: Mar-2025
https://doi.org/10.1016/j.iot.2025.101521
Liou JAwan MLeyba KŠulc PHofmeyr SWu CForrest S(2024)Evolving to Find Optimizations Humans Miss: Using Evolutionary Computation to Improve GPU Code for Bioinformatics ApplicationsACM Transactions on Evolutionary Learning and Optimization10.1145/37039204:4(1-29)Online publication date: 15-Nov-2024
https://dl.acm.org/doi/10.1145/3703920
Rani PZellweger JKousadianos VCruz LKehrer TBacchelli ARoychoudhury PPaiva AAbreu RStorey MSharif BXia X(2024)Energy Patterns for Web: An Exploratory StudyProceedings of the 46th International Conference on Software Engineering: Software Engineering in Society10.1145/3639475.3640110(12-22)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639475.3640110
Show More Cited By

Index Terms

Reducing Energy Consumption Using Genetic Improvement
1. Software and its engineering

Recommendations

Energy Optimisation via Genetic Improvement: A SBSE technique for a new era in Software Development
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

The discipline of Software Engineering has arisen during a time in which developers rarely concerned themselves with the energy efficiency of their software. Due to the growth in both mobile devices and large server clusters this period is undoubtedly ...
GI4GI: Improving Genetic Improvement Fitness Functions
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Genetic improvement (GI) has been successfully used to optimise non-functional properties of software, such as execution time, by automatically manipulating program's source code. Measurement of non-functional properties, however, is a non-trivial task; ...
Optimising Energy Consumption Heuristically on Android Mobile Phones
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

In this paper we outline our proposed framework for optimising energy consumption on Android mobile phones. To model the power usage, we use an event-based modelling technique. The internal battery fuel gauge chip is used to measure the amount of energy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
621
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)7

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aragón-Jurado Jde la Torre JRuiz PDorronsoro B(2025)Automatic software tailoring for Green Internet of ThingsInternet of Things10.1016/j.iot.2025.10152130(101521)Online publication date: Mar-2025
https://doi.org/10.1016/j.iot.2025.101521
Liou JAwan MLeyba KŠulc PHofmeyr SWu CForrest S(2024)Evolving to Find Optimizations Humans Miss: Using Evolutionary Computation to Improve GPU Code for Bioinformatics ApplicationsACM Transactions on Evolutionary Learning and Optimization10.1145/37039204:4(1-29)Online publication date: 15-Nov-2024
https://dl.acm.org/doi/10.1145/3703920
Rani PZellweger JKousadianos VCruz LKehrer TBacchelli ARoychoudhury PPaiva AAbreu RStorey MSharif BXia X(2024)Energy Patterns for Web: An Exploratory StudyProceedings of the 46th International Conference on Software Engineering: Software Engineering in Society10.1145/3639475.3640110(12-22)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639475.3640110
Aragón-Jurado Jde la Torre JRuiz PGalindo PZomaya ADorronsoro B(2024)Automatic Software Tailoring for Optimal PerformanceIEEE Transactions on Sustainable Computing10.1109/TSUSC.2023.33306719:3(464-481)Online publication date: May-2024
https://doi.org/10.1109/TSUSC.2023.3330671
Dorronsoro BAragón-Jurado JJareño Jde la Torre JRuiz P(2024)A Survey on Automatic Source Code Transformation for Green Software GenerationEncyclopedia of Sustainable Technologies10.1016/B978-0-323-90386-8.00122-4(765-779)Online publication date: 2024
https://doi.org/10.1016/B978-0-323-90386-8.00122-4
Callan JPetke J(2024)Multi-objective improvement of Android applicationsAutomated Software Engineering10.1007/s10515-024-00472-732:1Online publication date: 4-Nov-2024
https://doi.org/10.1007/s10515-024-00472-7
Fredericks EMoore JDiller A(2024)GenerativeGI: creating generative art with genetic improvementAutomated Software Engineering10.1007/s10515-024-00414-331:1Online publication date: 1-Mar-2024
https://doi.org/10.1007/s10515-024-00414-3
Biau JCussat-Blanc SLuga H(2024)Improving Image Filter Efficiency: A Multi-objective Genetic Algorithm Approach to Optimize Computing EfficiencyApplications of Evolutionary Computation10.1007/978-3-031-56852-7_2(19-34)Online publication date: 3-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-56852-7_2
Li XChen JLiu YWu KGallagher J(2023)Combatting Energy Issues for Mobile ApplicationsACM Transactions on Software Engineering and Methodology10.1145/352785132:1(1-44)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3527851
Wedyan FMorrison RAbuomar O(2023)Integration and Unit Testing of Software Energy Consumption2023 Tenth International Conference on Software Defined Systems (SDS)10.1109/SDS59856.2023.10329262(60-64)Online publication date: 23-Oct-2023
https://doi.org/10.1109/SDS59856.2023.10329262
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten