A Probabilistic Graphical Model-based Approach for Minimizing Energy Under Performance Constraints

Abstract

In many deployments, computer systems are underutilized -- meaning that applications have performance requirements that demand less than full system capacity. Ideally, we would take advantage of this under-utilization by allocating system resources so that the performance requirements are met and energy is minimized. This optimization problem is complicated by the fact that the performance and power consumption of various system configurations are often application -- or even input -- dependent. Thus, practically, minimizing energy for a performance constraint requires fast, accurate estimations of application-dependent performance and power tradeoffs. This paper investigates machine learning techniques that enable energy savings by learning Pareto-optimal power and performance tradeoffs. Specifically, we propose LEO, a probabilistic graphical model-based learning system that provides accurate online estimates of an application's power and performance as a function of system configuration. We compare LEO to (1) offline learning, (2) online learning, (3) a heuristic approach, and (4) the true optimal solution. We find that LEO produces the most accurate estimates and near optimal energy savings.

References

1. Jason Ansel, Maciej Pacula, Yee Lok Wong, Cy Chan, Marek Olszewski, Una-May O'Reilly, and Saman Amarasinghe. Sibling rivalry: online autotuning through local competitions. In CASES, 2012.
2. Jason Ansel, Yee Lok Wong, Cy Chan, Marek Olszewski, Alan Edelman, and Saman Amarasinghe. Language and compiler support for auto-tuning variable-accuracy algorithms. In CGO, 2011.
3. L.A Barroso and U. Holzle. The case for energy-proportional computing. Computer, 40(12):33--37, Dec 2007.
4. C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT, 2008.
5. Ramazan Bitirgen, Engin Ipek, and Jose F. Martinez. Coordinated management of multiple interacting resources in chip multiprocessors: A machine learning approach. In MICRO, 2008.
6. S.P. Bradley, A.C. Hax, and T.L. Magnanti. Applied mathematical programming. Addison-Wesley Pub. Co., 1977.
7. Aaron Carroll and Gernot Heiser. Mobile multicores: Use them or waste them. In Proceedings of the Workshop on Power-Aware Computing and Systems, HotPower '13, pages 12:1--12:5, New York, NY, USA, 2013. ACM.
8. Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W. Sheaffer, Sang-Ha Lee, and Kevin Skadron. Rodinia: A benchmark suite for heterogeneous computing. In IISWC, 2009.
9. Jian Chen and Lizy Kurian John. Predictive coordination of multiple on-chip resources for chip multiprocessors. In ICS, 2011.
10. Jian Chen, Lizy Kurian John, and Dimitris Kaseridis. Modeling program resource demand using inherent program characteristics. SIGMETRICS Perform. Eval. Rev., 39(1):1--12, June 2011.
11. Ryan Cochran, Can Hankendi, Ayse K. Coskun, and Sherief Reda. Pack & cap: adaptive dvfs and thread packing under power caps. In MICRO, 2011.
12. Qingyuan Deng, David Meisner, Abhishek Bhattacharjee, Thomas F Wenisch, and Ricardo Bianchini. Coscale: Coordinating cpu and memory system dvfs in server systems. In Microarchitecture (MICRO), 2012 45th Annual IEEE/ACM International Symposium on, pages 143--154. IEEE, 2012.
13. Petre Dini, Wolfgang Gentzsch, Mark Potts, Alexander Clemm, Mazin Yousif, and Andreas Polze. Internet, GRID, self-adaptability and beyond: Are we ready? Aug 2004.
14. Christophe Dubach, Timothy M. Jones, Edwin V. Bonilla, and Michael F. P. O'Boyle. A predictive model for dynamic microarchitectural adaptivity control. In MICRO, 2010.
15. Bradley Efron and Carl Morris. Data analysis using stein's estimator and its generalizations. Journal of the American Statistical Association, 70(350):311--319, 1975.
16. Antonio Filieri, Henry Hoffmann, and Martina Maggio. Automated design of self-adaptive software with control-theoretical formal guarantees. In ICSE, 2014.
17. J. Flinn and M. Satyanarayanan. Energy-aware adaptation for mobile applications. In SOSP, 1999.
18. Jason Flinn and M. Satyanarayanan. Managing battery lifetime with energy-aware adaptation. ACM Trans. Comp. Syst., 22(2), May 2004.
19. Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin. Bayesian data analysis. CRC press, 2013.
20. W. Gentzsch, K. Iwano, D. Johnston-Watt, M.A. Minhas, and M. Yousif. Self-adaptable autonomic computing systems: An industry view. In Proceedings of the 16th International Workshop on Database and Expert Systems Applications, pages 201--205, Aug 2005.
21. Henry Hoffmann. Racing vs. pacing to idle: A comparison of heuristics for energy-aware resource allocation. In HotPower, 2013.
22. Henry Hoffmann, Jonathan Eastep, Marco D. Santambrogio, Jason E. Miller, and Anant Agarwal. Application heartbeats: a generic interface for specifying program performance and goals in autonomous computing environments. In ICAC, 2010.
23. Henry Hoffmann, Jim Holt, George Kurian, Eric Lau, Martina Maggio, Jason E. Miller, Sabrina M. Neuman, Mahmut Sinangil, Yildiz Sinangil, Anant Agarwal, Anantha P. Chandrakasan, and Srinivas Devadas. Self-aware computing in the angstrom processor. In DAC, 2012.
24. Henry Hoffmann, Martina Maggio, Marco D. Santambrogio, Alberto Leva, and Anant Agarwal. A generalized software framework for accurate and efficient managment of performance goals. In EMSOFT, 2013.
25. Henry Hoffmann, Stelios Sidiroglou, Michael Carbin, Sasa Misailovic, Anant Agarwal, and Martin Rinard. Dynamic knobs for responsive power-aware computing. In ASPLOS, 2011.
26. T. Horvath, T. Abdelzaher, K. Skadron, and Xue Liu. Dynamic voltage scaling in multitier web servers with end-to-end delay control. Computers, IEEE Transactions on, 56(4), 2007.
27. Connor Imes, David H. K. Kim, Martina Maggio, and Henry Hoffmann. Poet: A portable approach to minimizing energy under soft real-time constraints. In RTAS, 2015.
28. Engin Ipek, Onur Mutlu, José F. Martínez, and Rich Caruana. Self-optimizing memory controllers: A reinforcement learning approach. In ISCA, 2008.
29. J.O. Kephart. Research challenges of autonomic computing. In ICSE, 2005.
30. Minyoung Kim, Mark-Oliver Stehr, Carolyn Talcott, Nikil Dutt, and Nalini Venkatasubramanian. xtune: A formal methodology for cross-layer tuning of mobile embedded systems. ACM Trans. Embed. Comput. Syst., 11(4), January 2013.
31. Robert Laddaga. Guest editor's introduction: Creating robust software through self-adaptation. IEEE Intelligent Systems, 14, 1999.
32. Etienne Le Sueur and Gernot Heiser. Slow down or sleep, that is the question. In Proceedings of the 2011 USENIX Annual Technical Conference, Portland, OR, USA, June 2011.
33. B.C. Lee, J. Collins, Hong Wang, and D. Brooks. Cpr: Composable performance regression for scalable multiprocessor models. In MICRO, 2008.
34. Benjamin C. Lee and David Brooks. Efficiency trends and limits from comprehensive microarchitectural adaptivity. In ASPLOS, 2008.
35. Benjamin C. Lee and David M. Brooks. Accurate and efficient regression modeling for microarchitectural performance and power prediction. In ASPLOS, 2006.
36. Baochun Li and K. Nahrstedt. A control-based middleware framework for quality-of-service adaptations. IEEE Journal on Selected Areas in Communications, 17(9), 1999.
37. J. Li and J.F. Martinez. Dynamic power-performance adaptation of parallel computation on chip multiprocessors. In HPCA, 2006.
38. C. Lu, Y. Lu, T.F. Abdelzaher, J.A. Stankovic, and S.H. Son. Feedback control architecture and design methodology for service delay guarantees in web servers. IEEE TPDS, 17(9):1014--1027, September 2006.
39. Martina Maggio, Henry Hoffmann, Marco D. Santambrogio an d Anant Agarwal, and Alberto Leva. Power optimization in embedded systems via feedback control of resource allocation. IEEE Transactions on Control Systems Technology (to appear).
40. Martina Maggio, Henry Hoffmann, Alessandro V. Papadopoulos, Jacopo Panerati, Marco D. Santambrogio, Anant Agarwal, and Alberto Leva. Comparison of decision-making strategies for self-optimization in autonomic computing systems. ACM Trans. Auton. Adapt. Syst., 7(4):36:1--36:32, December 2012.
41. David Meisner, Christopher M. Sadler, Luiz Andre Barroso, Wolf-Dietrich Weber, and Thomas F. Wenisch. Power management of online data-intensive services. ISCA, 2011.
42. Carl N Morris. Parametric empirical bayes inference: theory and applications. Journal of the American Statistical Association, 78(381):47--55, 1983.
43. R. Narayanan, B. Ozisikyilmaz, J. Zambreno, G. Memik, and A. Choudhary. Minebench: A benchmark suite for data mining workloads. In IISWC, 2006.
44. Paula Petrica, Adam M. Izraelevitz, David H. Albonesi, and Christine A. Shoemaker. Flicker: A dynamically adaptive architecture for power limited multicore systems. In ISCA, 2013.
45. Dmitry Ponomarev, Gurhan Kucuk, and Kanad Ghose. Re- ducing power requirements of instruction scheduling through dynamic allocation of multiple datapath resources. In MICRO, 2001.
46. R. Raghavendra, P. Ranganathan, V Talwar, Z. Wang, and X. Zhu. No "power" struggles: coordinated multi-level power management for the data center. In ASPLOS, 2008.
47. R. Rajkumar, C. Lee, J. Lehoczky, and Dan Siewiorek. A resource allocation model for qos management. In RTSS, 1997.
48. Arjun Roy, Stephen M. Rumble, Ryan Stutsman, Philip Levis, David Mazieres, and Nickolai Zeldovich. Energy management in mobile devices with the cinder operating system. In EuroSys, 2011.
49. Mazeiar Salehie and Ladan Tahvildari. Self-adaptive software: Landscape and research challenges. ACM Trans. Auton. Adapt. Syst., 4(2):1--42, 2009.
50. David C. Snowdon, Etienne Le Sueur, Stefan M. Petters, and Gernot Heiser. Koala: A platform for os-level power management. In EuroSys, 2009.
51. Michal Sojka, Pavel Písa, Dario Faggioli, Tommaso Cucinotta, Fabio Checconi, Zdenek Hanzalek, and Giuseppe Lipari. Modular software architecture for flexible reservation mechanisms on heterogeneous resources. Journal of Systems Architecture, 57(4), 2011.
52. Srinath Sridharan, Gagan Gupta, and Gurindar S. Sohi. Holistic run-time parallelism management for time and energy efficiency. In ICS, 2013.
53. Q. Sun, G. Dai, and W. Pan. LPV model and its application in web server performance control. In ICCSSE, 2008.
54. Vibhore Vardhan, Wanghong Yuan, Albert F. Harris III, Sarita V. Adve, Robin Kravets, Klara Nahrstedt, Daniel Grobe Sachs, and Douglas L. Jones. Grace-2: integrating fine-grained application adaptation with global adaptation for saving energy. IJES, 4(2), 2009.
55. Jonathan A. Winter, David H. Albonesi, and Christine A. Shoemaker. Scalable thread scheduling and global power management for heterogeneous many-core architectures. In PACT, 2010.
56. CF Jeff Wu. On the convergence properties of the em algorithm. The Annals of statistics, pages 95--103, 1983.
57. Qiang Wu, Philo Juang, Margaret Martonosi, and Douglas W. Clark. Formal online methods for voltage/frequency control in multiple clock domain microprocessors. In ASPLOS, 2004.
58. Weidan Wu and Benjamin C Lee. Inferred models for dynamic and sparse hardware-software spaces. In Microarchitecture (MICRO), 2012 45th Annual IEEE/ACM International Symposium on, pages 413--424. IEEE, 2012.
59. Joshua J. Yi, David J. Lilja, and Douglas M. Hawkins. A statistically rigorous approach for improving simulation methodology. In HPCA, 2003.
60. Kai Yu, Volker Tresp, and Anton Schwaighofer. Learning gaussian processes from multiple tasks. In Proceedings of the 22nd international conference on Machine learning, pages 1012--1019. ACM, 2005.
61. R. Zhang, C. Lu, T.F. Abdelzaher, and J.A. Stankovic. Controlware: A middleware architecture for feedback control of software performance. In ICDCS, 2002.
62. Xiao Zhang, Rongrong Zhong, Sandhya Dwarkadas, and Kai Shen. A flexible framework for throttling-enabled multicore management (temm). In ICPP, 2012.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies