Article

Article title APPLICATION OF GENETIC ALGORITHM, IMPLEMENTED IN COMPILER FOR OPTIMIZATION OF APPLICATIONS ENERGY-EFFICIENCY
Authors I.P. Tocar
Section SECTION III. MODELING AND DESIGN
Month, Year 02, 2015 @en
Index UDC 004.4`422
DOI
Abstract Purpose of this paper is to find a compilation techniques that improve energy-efficiency of programs. This problem is formulated as a multiple criteria (performance, energy-consumption) optimization problem, with constraints on compile time increase and performance decrease, where acceptable performance degradation is specified by user. Program is separated into a number of regions (at most one region per subroutine), running at different CPU frequencies, and due to difference in frequency and voltage consuming lower amount of energy, but having lower performance. A NSGA2-based genetic algorithm of finding frequencies for each region which provide maximal amount of energy-saving while maintaining performance within user provided range is proposed. It was implemented as compiler pass in GCC (GNU COMPILER COLLECTION), which consumed profiling data at different frequencies and instrumented code to run at frequencies provided by algorithm. Result of application of this algorithm are measured and provided. Namely 13.5% energy-efficiency increase in archived on tests from SPEC2000 testsuite (in particular 183.equake). This result is archived when acceptable performance degradation is selected to be less than 7%. Archived result is higher than 9%, which is current state-of-the-art, obtained by integer linear programming based approach. On EEMBC benchmark suite no improvement or degradation is found. Main disadvantage of this algorithm is inability to cooperate with operating system and other processes in multicore environment.

Download PDF

Keywords Compilers; energy-efficiency; genetic algorithms.
References 1. Brown R. Report to congress on server and data center energy efficiency, USA Public law 109-431, 2008, pp. 8-37.
2. JD Power. US Wireless Traditional Mobile Phone Satisfaction Study, JD Power studies 2012, pp. 134-156.
3. Intel Corporation and Microsoft Corporation, Advanced Power Management (APM), BIOS interface specification revision 1.0, 1992, pp. 7-87.
4. Available at: http://www.acpi.info (Accessed 09 February 2015).
5. Albers S., Antoniadis A. Race to idle: new algorithms for speed scaling with a sleep state, Antoniadis, In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 1266-1285.
6. Hsu C.H., Kremer U. The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, U. ACM SIGPLAN Notices, 2003, Vol. 38 (5), pp. 38-48.
7. Zhurikhin D., Belevantsev A., Avetisyan A., Batuzov K., Lee S. Evaluating power-aware optimizations within GCC compiler, GCC Research Opportunities workshop, GROW, 2009, pp. 1-7.
8. Sihara T., Yasuura H. Voltage scheduling problem for dynamically variable voltage processors, In Low Power Electronics and Design, 1998. Proceedings IEEE, 1998, pp. 197-202.
9. Kandemir M., Vijaykrishnan N., Irwin M.J. Compiler optimizations for low power systems, Power Aware Computing textbook, 2002, pp. 191-210. 10. Zhang W., Vijaykrishnan N., Kandemir M., Irwin M.J., Duarte D., Tsai Y.F. Exploiting VLIW schedule slacks for dynamic and leakage energy reduction. In Microarchitecture, MICRO-34. Proceedings. 34th ACM/IEEE International Symposium, 2011, pp. 102-113.
11. Esmaeilzadeh H., Cao T., Yang X., Blackburn S. M., McKinley K.S. Looking back and looking forward: power, performance, and upheaval, Communications of the Acm., 2012, Vol. 55 (7), pp. 105-114.
12. Li L., Xue J. Trace-based leakage energy optimizations at link time, Journal of Systems Architecture, 2007, Vol. 53 (1), pp. 1-20.
13. Goldberg David E. Genetic algorithms in search, optimization, and machine learning. Moscow: Addison-Wesley, 1989.
14. Melik-Adamyan A.F. Application of genetic algorithms in problems of optimization of the physical design in microelectronics, Automatic Documentation and Mathematical Linguistics, 2009, Vol. 43, Issue 4, pp. 244-250.
15. Pallipadi V., Starikovskiy A. The ondemand governor, In Proceedings of the Linux Symposium, 2006, Vol. 2, pp. 215-230.
16. Deb K., Pratap A., Agarwal S., Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II, Evolutionary Computation, IEEE Transactions on, 2002, No. 6 (2), pp. 182-197.
17. Martin T.L., Siewiorek D.P. Balancing batteries, power, and performance: system issues in cpu speed-setting for mobile computing, Doctoral dissertation, PhD thesis, 1999, pp. 34-43.
18. Jones T.M., O’Boyle M.F., Abella J., Gonzбlez A. Compiler directed issue queue energy reduction, In Transactions on High-Performance Embedded Architectures and Compilers. Moscow: Springer Berlin Heidelberg, 2011, pp. 42-62.
19. Tokar' I.P. Geneticheskiy algoritm optimizatsii energoeffektivnosti v kompilyatore dlya mobil'nykh ustroystv [Genetic algorithm optimization of energy efficiency in the compiler for mobile devices], Trudy 55-y Vserossiyskoy nauchnoy konferentsii problemy fundamental'nykh
i prikladnykh estestvennykh i tekhnicheskikh nauk v sovremennom in-formatsionnom obshchestve [Proceedings of the 55th all-Russian scientific conference problems of fundamental and applied natural Sciences and engineering in the modern information society]. Dolgoprudnyy 2013, pp. 88.

Comments are closed.