Bounding energy consumption in large-scale MPI programs

ABSTRACT

Power is now a first-order design constraint in large-scale parallel computing. Used carefully, dynamic voltage scaling can execute parts of a program at a slower CPU speed to achieve energy savings with a relatively small (possibly zero) time delay. However, the problem of when to change frequencies in order to optimize energy savings is NP-complete, which has led to many heuristic energy-saving algorithms. To determine how closely these algorithms approach optimal savings, we developed a system that determines a bound on the energy savings for an application. Our system uses a linear programming solver that takes as inputs the application communication trace and the cluster power characteristics and then outputs a schedule that realizes this bound. We apply our system to three scientific programs, two of which exhibit load imbalance---particle simulation and UMT2K. Results from our bounding technique show particle simulation is more amenable to energy savings than UMT2K.

REFERENCES

• 1: Rong Ge , Xizhou Feng , Kirk W. Cameron, Performance-constrained Distributed DVS Scheduling for Scientific Applications on Power-aware Clusters, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.34, November 12-18, 2005 [doi>10.1109/SC.2005.57]
• 2: E. Elnozahy, M. Kistler, and R. Rajamony. Energy-efficient server clusters. In Workshop on Power-Aware Computing Systems, February 2002.
• 3: Krisztián Flautner , Steve Reinhardt , Trevor Mudge, Automatic performance setting for dynamic voltage scaling, Proceedings of the 7th annual international conference on Mobile computing and networking, p.260-271, July 2001, Rome, Italy [doi>10.1145/381677.381702]
• 4: R. Ge and K. W. Cameron. Power-aware speedup. In In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS 07), March 2007.
• 5: D. Grunwald, P. Levis, K. Farkas, C. Morrey, and M. Neufeld. Policies for dynamic clock scheduling. In Operating System Design and Implementation, October 2000.
• 6: Wayne A. Haga and Tim O'Keefe. Crashing pert networks: A simulation approach. In 4th International Conference of the Academy of Business and Administrative Sciences Conference, July 2001.
• 7: C. Hsu, W. Feng, and J. S. Archuleta. Towards efficient supercomputing: A quest for the right metric. In Workshop on High-Performance, Power-Aware Computing, April 2005.
• 8: Chung-Hsing Hsu , Ulrich Kremer, The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 9: Chung-hsing Hsu , Wu-chun Feng, A Power-Aware Run-Time System for High-Performance Computing, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.1, November 12-18, 2005 [doi>10.1109/SC.2005.3]
• 10: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 11: Nandini Kappiah , Vincent W. Freeh , David K. Lowenthal, Just In Time Dynamic Voltage Scaling: Exploiting Inter-Node Slack to Save Energy in MPI Programs, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.33, November 12-18, 2005 [doi>10.1109/SC.2005.39]
• 12: Lawrence Livermore National Laboratory. The ASCI Purple Benchmarks. http://www.llnl.gov/asci/platforms/purple/rfp/benchmarks, 2001.
• 13: Lawrence Livermore National Laboratory. The UMT Benchmark Code. http://www.llnl.gov/asci/platforms/purple/rfp/benchmarks/limited/umt/, January 2002.
• 14: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 15: Andrew Makhorin. GNU Linear Programming Kit. http://www.gnu.org/software/glpk/glpk.html, January 2005.
• 16: Bren Mochocki , Xiaobo Sharon Hu , Gang Quan, A realistic variable voltage scheduling model for real-time applications, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.726-731, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774679]
• 17: Bren Mochocki , Xiaobo Sharon Hu , Gang Quan, Practical On-line DVS Scheduling for Fixed-Priority Real-Time Systems, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.224-233, March 07-10, 2005 [doi>10.1109/RTAS.2005.40]
• 18: B. Mohr and F. Wolf. KOJAK - a tool set for automatic performance analysis of parallel applications. In Proc. of the European Conference on Parallel Computing (EuroPar), August 2003.
• 19: M. Angels Moncusi, Alex Arenas, and Jesus Labarta. Energy aware EDF scheduling in distributed hard real time systems. In Real-Time Systems Symposium, December 2003.
• 20: Brian D. Noble , M. Satyanarayanan , Dushyanth Narayanan , James Eric Tilton , Jason Flinn , Kevin R. Walker, Agile application-aware adaptation for mobility, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.276-287, October 05-08, 1997, Saint Malo, France
• 21: M. Noeth, F. Mueller, M. Schulz, and B. de Supinski. Scalable compression and replay of communication traces in massively parallel environments. In International Parallel and Distributed Processing Symposium (IPDPS), April 2007.
• 22: Andrei Radulescu , Cristina Nicolescu , Arjan J. C. van Gemund , Pieter Jonker, CPR: Mixed Task and Data Parallel Scheduling for Distributed Systems, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.39, April 23-27, 2001
• 23: Barry Render and Ralph M. Stair Jr. Quantitative Analysis for Management. Prentice-Hall, seventh edition, 2000.
• 24: H. Saputra , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , J. S. Hu , C-H. Hsu , U. Kremer, Energy-conscious compilation based on voltage scaling, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 25: Vivek Sharma , Arun Thomas , Tarek Abdelzaher , Kevin Skadron , Zhijian Lu, Power-aware QoS Management in Web Servers, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.63, December 03-05, 2003
• 26: Jaswinder P Singh , Wolf Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory*, Stanford University, Stanford, CA, 1992
• 27: Allan Snavely , Laura Carrington , Nicole Wolter , Jesus Labarta , Rosa Badia , Avi Purkayastha, A framework for performance modeling and prediction, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 28: Robert Springer , David K. Lowenthal , Barry Rountree , Vincent W. Freeh, Minimizing execution time in MPI programs on an energy-constrained, power-scalable cluster, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123006]
• 29: Vishu Swaminathan , Krishnendu Chakrabarty, Investigating the effect of voltage-switching on low-energy task scheduling in hard real-time systems, Proceedings of the 2001 conference on Asia South Pacific design automation, p.251, January 2001, Yokohama, Japan [doi>10.1145/370155.370337]
• 30: Vishnu Swaminathan and Krshnendu Chakrabarty. Real-time task scheduling for energy-aware embedded systems. In IEEE Real-Time Systems Symposium, November 2000.
• 31: OpenMPI Development Team. OpenMPI. http://www.open-mpi.org, 2006.
• 32: Jeffrey S. Vetter , Andy Yoo, An empirical performance evaluation of scalable scientific applications, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 33: Mark Weiser , Brent Welch , Alan Demers , Scott Shenker, Scheduling for reduced CPU energy, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.2-es, November 14-17, 1994, Monterey, California
• 34: Qiang Wu , Philo Juang , Margaret Martonosi , Li-Shiuan Peh , Douglas W. Clark, Formal Control Techniques for Power-Performance Management, IEEE Micro, v.25 n.5, p.52-62, September 2005 [doi>10.1109/MM.2005.87]
• 35: Fen Xie , Margaret Martonosi , Sharad Malik, Compile-time dynamic voltage scaling settings: opportunities and limits, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 36: Fen Xie , Margaret Martonosi , Sharad Malik, Intraprogram dynamic voltage scaling: Bounding opportunities with analytic modeling, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.323-367, September 2004 [doi>10.1145/1022969.1022973]
• 37: Fen Xie , Margaret Martonosi , Sharad Malik, Bounds on power savings using runtime dynamic voltage scaling: an exact algorithm and a linear-time heuristic approximation, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077670]
• 38: Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513966]
• 39: Dakai Zhu , Rami Melhem , Bruce R. Childers, Scheduling with Dynamic Voltage/Speed Adjustment Using Slack Reclamation in Multiprocessor Real-Time Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.686-700, July 2003 [doi>10.1109/TPDS.2003.1214320]