Energy-efficient deadline scheduling for heterogeneous systems. (English) Zbl 1270.68053
Summary: Energy efficiency is a major concern in modern high performance computing (HPC) systems and a power-aware scheduling approach is a promising way to achieve that. While there are a number of studies in power-aware scheduling by means of dynamic power management (DPM) and/or dynamic voltage and frequency scaling (DVFS) techniques, most of them only consider scheduling at a steady state. However, HPC applications like scientific visualization often need deadline constraints to guarantee timely completion. In this paper we present power-aware scheduling algorithms with deadline constraints for heterogeneous systems. We formulate the problem by extending the traditional multiprocessor scheduling and design approximation algorithms with analysis on the worst-case performance. We also present a pricing scheme for tasks in the way that the price of a task varies as its energy usage as well as largely depending on the tightness of its deadline. Last we extend the proposed algorithm to the control dependence graph and the online case which is more realistic. Through the extensive experiments, we demonstrate that the proposed algorithm achieves near-optimal energy efficiency, on average 16.4% better for synthetic workload and 12.9% better for realistic workload than the EDD (Earliest Due Date)-based algorithm; The extended online algorithm also outperforms the EDF (Earliest Deadline First)-based algorithm with an average up to 26% of energy saving and 22% of deadline satisfaction. It is experimentally shown as well that the pricing scheme provides a flexible trade-off between deadline tightness and price.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Software:
MCELLReferences:
| [1] | Faraz Ahmad, T.N. Vijaykumar, Joint optimization of idle and cooling power in data centers while maintaining response time, in: Proc. of 14th Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS, 2010, pp. 243–256. |
| [2] | Anglano, Cosimo; Canonico, Massimo: Fault-tolerant scheduling for bag-of-tasks grid applications, Lecture notes in computer science, 630 (2005) |
| [3] | Hakan Aydin, Qi Yang, Energy-aware partitioning for multiprocessor real-time systems, in: Proc. of Parallel and Distributed Processing Symposium, IPDPS, 2003. |
| [4] | Aziz, Abdul; El-Rewini, Hesham: Power efficient scheduling heuristics for energy conservation in computational grids, J. supercomput. 57, No. 1, 65-80 (2011) |
| [5] | Beaumont, Olivier; Carter, Larry; Ferrante, Jeanne; Legrand, Arnaud; Marchal, Loris; Robert, Yves: Centralized versus distributed schedulers for multiple bag-of-task applications, IEEE trans. Parallel distrib. Syst. 19, No. 5, 698-709 (2008) |
| [6] | Bogliolo, Alessandro; Benini, Luca; Bogliolo, Ro; De Micheli, Giovanni: A survey of design techniques for system-level dynamic power management, IEEE trans. Very large scale integr. (VLSI) syst. 8, No. 3, 299-316 (2000) |
| [7] | Bratley, Paul; Florian, Michael; Robillard, Pierre: Scheduling with earliest start and due date constraints, Nav. res. Logist. Q. 18, No. 4, 511-519 (1971) · Zbl 0272.90031 |
| [8] | Tom Budnik, Brant Knudson, Mark Megerian, Sam Miller, Mike Mundy, Will Stockdell, Blue Gene/Q resource management architecture, 2010. http://www.green500.org/lists/2010/11/little/list.php. |
| [9] | Jennifer Burge, Partha Ranganathan, Janet L. Wiener, Cost-aware scheduling for heterogeneous enterprise machines (cash’em), in: Proc. of 1st International Workshop on Green Computing, GreenCom, 2007. |
| [10] | Cameron, Kirk W.; Ge, Rong; Feng, Xizhou: High-performance, power-aware distributed computing for scientific applications, Computer 38, No. 11, 40-47 (2005) |
| [11] | Chan, Ho Leung; Chan, Joseph Wun Tat; Lam, Tak Wah; Lee, Lap Kei; Mak, Kin Sum; Wong, Prudence W. H.: Optimizing throughput and energy in online deadline scheduling, ACM trans. Algorithms 6, No. 1, 1-10 (2009) · Zbl 1300.90013 |
| [12] | Chen, Hua; Cheng, Albert Mo Kim; Kuo, Ying Wei: Assigning real-time tasks to heterogeneous processors by applying ant colony optimization, J. parallel distrib. Comput. 71, No. 1, 132-142 (2011) · Zbl 1219.68068 · doi:10.1016/j.jpdc.2010.09.011 |
| [13] | Chu, Edward T. H.; Huang, Tai Yi; Tsai, Yu Che: An optimal solution for the heterogeneous multiprocessor single-level voltage-setup problem, IEEE trans. Comput.-aided des. Integr. circuits syst. 28, No. 11, 1705-1718 (2009) |
| [14] | Walfredo Cirne, Francisco Brasileiro, Jacques Sauvé, Nazareno Andrade, Daniel Paranhos, Elizeu Santos-neto, Raissa Medeiros, Federal Campina Gr., Grid computing for bag of tasks applications, in: Proc. of 3rd IFIP Conference on E-Commerce, E-Business and E-Government, 2003. |
| [15] | Da Silva, Fabrício A. B.; Carvalho, Sílvia; Hruschka, Eduardo R.: A scheduling algorithm for running bag-of-tasks data mining applications on the grid, Lecture notes in comput. Sci. 3149, No. 1, 254-262 (2004) · Zbl 1096.68579 · doi:10.1007/b99409 |
| [16] | Da Silva, Fabrício A. B.; Cirne, Walfredo; Brasileiro, Francisco Vilar: Trading cycles for information: using replication to schedule bag-of-tasks applications on computational grids, Lecture notes in comput. Sci. 2790, No. 1, 169-180 (2003) |
| [17] | Da Silva, Daniel Fabrício; Senger, Hermes: Improving scalability of bag-of-tasks applications running on master–slave platforms, J. parallel comput. 35, No. 1, 57-71 (2009) |
| [18] | Deelman, Ewa; Gannon, Dennis; Shields, Matthew; Taylor, Ian: Workflows and e-science: an overview of workflow system features and capabilities, Future gener. Comput. syst. 25, No. 5, 528-540 (2009) |
| [19] | Michael L. Dertouzos, Control robotics: the procedural control of physical process, in: Proc. of IFIP Congress, 1974, pp. 807–813. |
| [20] | Doulamis, Nikolaos D.; Doulamis, Anastasios D.; Varvarigos, Emmanouel A.; Varvarigou, Theodora A.: Fair scheduling algorithms in grids, IEEE trans. Parallel distrib. Syst. 18, No. 11, 1030-1048 (2007) |
| [21] | Dror Feitelson. Parallel workloads archive, http://www.cs.huji.ac.il/labs/parallel/workload/, 2009. |
| [22] | Du, Bing; Ruan, Chun: Robust performance modelling and scheduling of distributed real-time systems, J. supercomput. 53, No. 1, 122-137 (2010) |
| [23] | Electricity price, http://money.163.com/11/0404/08/70PJ2AOE002526O3.html, 2011. |
| [24] | Xiaobo Fan, Wolf Dietrich Weber, Luiz Andre Barroso, Power provisioning for a warehouse-sized computer, in: Proc. of 34th International Symposium on Computer Architecture, ISCA, 2007. |
| [25] | Wuchun Feng, ChungHsing Hsu, The origin and evolution of green destiny, in: IEEE Cool Chips VII: An International Symposium on Low-Power and High-Speed Chips, 2004. |
| [26] | Fernandez, Jose Jesus; Gordon, Dan; Gordon, Rachel: Efficient parallel implementation of iterative reconstruction algorithms for electron tomography, J. parallel distrib. Comput. 68, No. 5, 626-640 (2008) |
| [27] | Freeh, Vincent W.; Kappiah, Nandini; Lowenthal, David K.; Bletsch, Tyler K.: Just-in-time dynamic voltage scaling: exploiting inter-node slack to save energy in mpi programs, J. parallel distrib. Comput. 68, No. 9, 1175-1185 (2008) |
| [28] | Garey, Michael R.; Johnson, David S.: Computers and intractability: A guide to the theory of NP-completeness, (1979) · Zbl 0411.68039 |
| [29] | Garg, Saurabh Kumar; Yeo, Chee Shin; Anandasivam, Arun; Buyya, Rajkumar: Environment-conscious scheduling of HPC applications on distributed cloud-oriented data centers, J. parallel distrib. Comput. 71, No. 1, 732-749 (2011) · Zbl 1219.68070 · doi:10.1016/j.jpdc.2010.04.004 |
| [30] | Rong Ge, Xizhou Feng, Wuchun Feng, Kirk W. Cameron, CPU MISER: a performance-directed, run-time system for power-aware clusters, in: Proc. of International Conference on Parallel Processing, ICPP, 2007, pp. 18–25. |
| [31] | Grid workloads archive, http://gwa.ewi.tudelft.nl/pmwiki/pmwiki.php?n=Workloads.Overview, 2007. |
| [32] | Jianjun Han, Qinghua Li, Dynamic power-aware scheduling algorithms for real-time task sets with fault-tolerance in parallel and distributed computing environment, in: Proc. of 19th International Parallel and Distributed Processing Symposium, IPDPS, 2005, pp. 41–46. |
| [33] | Han, Xin; Lam, Tak Wah; Lee, Lap Kei; To, Isaac K. K.; Wong, Prudence W. H.: Deadline scheduling and power management for speed bounded processors, Theor. comput. Sci. 411, No. 40–42, 3587-3600 (2010) · Zbl 1214.68094 · doi:10.1016/j.tcs.2010.05.035 |
| [34] | He, Cheng; Lin, Yixun; Yuan, Jinjiang: A note on the single machine scheduling to minimize the number of tardy jobs with deadlines, European J. Oper. res. 201, No. 3, 966-970 (2010) · Zbl 1176.90220 · doi:10.1016/j.ejor.2009.05.013 |
| [35] | Hu, Fengping; Evans, Jeffrey J.: Power and environment aware control of beowulf clusters, Cluster comput. 12, No. 3, 299-308 (2009) |
| [36] | Team, Ibm Blue Gene: Overview of the IBM blue gene/P project, IBM J. Res. dev. 52, No. 1, 199-220 (2008) |
| [37] | Alexandru Iosup, Ozan Sonmez, Shanny Anoep, D. Epema, The performance of bags-of-tasks in large-scale distributed systems, in: Proc. of 17th International Symp on High Performance Distributed HPDC, 2008, pp. 97–108. |
| [38] | Irani, Sandy; Shukla, Sandeep; Gupta, Rajesh: Algorithms for power savings, ACM trans. Algorithms 3, No. 4, 1-41 (2007) · Zbl 1094.68696 |
| [39] | David E. Irwin, Laura E. Grit, Jeffrey S. Chase, Balancing risk and reward in a market-based task service, in: Proc. of 13th IEEE International Symp on High Performance Distributed Computing, HPDC, 2004. |
| [40] | James R. Jackson, Scheduling a production line to minimize maximum tardiness, Technical Report, Management Science Research Project, Univ. of Calif., Los Angeles, 1955. |
| [41] | Jha, Niraj K.: Low power system scheduling, synthesis and displays, IEE Proceedings of computers digital techniques 152, No. 3, 344-352 (2005) |
| [42] | Kalantari, Mohammad; Akbari, Mohammad Kazem: A parallel solution for scheduling of real time applications on grid environments, Future gener. Comput. syst. 25, No. 7, 704-716 (2009) |
| [43] | A. Karabuto, Hdd diet: power consumption and heat dissipation, 9, 2007. http://ixbtlabs.com/articles2/storage/hddpower.html. |
| [44] | Kyong Hoon Kim, Rajkumar Buyya, Jong Kim, Power aware scheduling of bag-of-tasks applications with deadline constraints on DVS-enabled clusters, in: Proc. of 7th International Cluster Computing and the Grid, CCGRID, 2007, pp. 541–548. |
| [45] | Cynthia B. Lee, Allan E. Snavely, Precise and realistic utility functions for user-centric performance analysis of schedulers, in: Proc. of 16th International Symp on High Performance Distributed Computing, HPDC, 2007, pp. 107–116. |
| [46] | Lee, Young Choon; Zomaya, Albert Y.: Practical scheduling of bag-of-tasks applications on grids with dynamic resilience, IEEE trans. Comput. 56, No. 6, 815-825 (2007) · Zbl 1390.68135 |
| [47] | Young Choon Lee, Albert Y. Zomaya, Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling, in: Proc. of 9th IEEE/ACM International Cluster Computing and the Grid, CCGRID, 2009, pp. 92–99. |
| [48] | Charles Lefurgy, Xiaorui Wang, Malcolm Ware, Server-level power control, in: Proc. of International Conference on Autonomic Computing, ICAC, 2007, pp. 11–15. |
| [49] | Li, Keqin: Performance analysis of power-aware task scheduling algorithms on multiprocessor computers with dynamic voltage and speed, IEEE trans. Parallel distrib. Syst. 19, No. 11, 1484-1497 (2008) |
| [50] | Li, Chunlin; Li, Layuan: Joint optimisation of application QoS and energy conservation in grid environment, Internat. J. Systems sci. 41, No. 9, 1027-1041 (2010) · Zbl 1202.90053 · doi:10.1080/00207720903199580 |
| [51] | Li, Minming; Liu, Becky J.; Yao, Frances F.: MIN-energy voltage allocation for tree-structured tasks, J. comb. Optim. 11, No. 3, 305-319 (2006) · Zbl 1255.90063 |
| [52] | Li, Minming; Yao, Frances F.: An efficient algorithm for computing optimal discrete voltage schedules, SIAM J. Comput. 35, No. 3, 658-671 (2005) · Zbl 1122.90041 · doi:10.1137/050629434 |
| [53] | Ming Hong Lin, Adam Wierman, Lachlan L.H. Andrew, Eno Thereska, Dynamic right-sizing for power-proportional data centers, in: Proc. of 30th IEEE International Conference on Computer Communications, IEEE INFOCOM, 2011. |
| [54] | Liu, Cong; Baskiyar, Sanjeev: A general distributed scalable grid scheduler for independent tasks, J. parallel distrib. Comput. 69, No. 3, 307-314 (2009) |
| [55] | Yan Ma, Bin Gong, Lida Zou, Marginal pricing based scheduling strategy of scientific workflow using cost-gradient metric, in: Proc. of 8th International Conference on Grid and Cooperative Computing, GCC, 2009, pp. 136–143. |
| [56] | Yan Ma, Bin Gong, Lida Zou, Energy-optimization scheduling of task dependent graph on DVS-enabled cluster system, in: Proc. of ChinaGrid Annual Conference, 2010, pp. 183–190. |
| [57] | David Meisner, Brian T. Gold, Thomas F. Wenisch, PowerNap: eliminating server idle power, in: Proc. of 14th Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS, 2009, pp. 205–216. |
| [58] | Mukherjee, Tridib; Banerjee, Ayan; Varsamopoulos, Georgios; Gupta, Sandeep K. S.; Rungta, Sanjay: Spatio-temporal thermal-aware job scheduling to minimize energy consumption in virtualized heterogeneous data centers, Comput. netw. 53, No. 17, 2888-2904 (2009) · Zbl 1187.68098 · doi:10.1016/j.comnet.2009.06.008 |
| [59] | Marco A.S. Netto, Rajkumar Buyya, Coordinated rescheduling of bag-of-tasks for executions on multiple resource providers, Technical Report, 2010. |
| [60] | Xiaojun Ruan, Xiao Qin, Ziliang Zong, Kiranmai Bellam, Mais Nijim, An energy-efficient scheduling algorithm using dynamic voltage scaling for parallel applications on clusters, in: Proc. of 16th International Conference on Computer Communications and Networks, ICCCN, 2007, pp. 735–740. |
| [61] | Stankovic, John A.; Spuri, Marco; Di Natale, Marco; Buttazzo, Giorgio: Implications of classical scheduling results for real-time systems, Computer 28, No. 6, 16-25 (1995) |
| [62] | Stiles, J. R.; Bartol, T. M.; Salpeter, E. E.; Salpeter, M. M.: Monte Carlo simulation of neuromuscular transmitter release using mcell, a general simulator of cellular physiological processes, Comput. neurosci., 279-284 (1998) |
| [63] | Subrata, Riky; Zomaya, Albert Y.; Landfeldt, Bjorn: Cooperative power-aware scheduling in grid computing environments, J. parallel distrib. Comput. 70, No. 2, 84-91 (2010) · Zbl 1233.68118 · doi:10.1016/j.jpdc.2009.09.003 |
| [64] | Top 500, http://www.top500.org/lists/2010/11/press-release, 2010. |
| [65] | Tseng, Li Ya; Chin, Yeh Hao; Wang, Shu Ching: A minimized makespan scheduler with multiple factors for grid computing systems, Expert syst. Appl. 36, No. 8, 11118-11130 (2009) |
| [66] | Mark Weiser, Brent Welch, Alan Demers, Scott Shenker, Scheduling for reduced CPU energy, in: Proc. of 1st USENIX Symp. Operating Systems Design and Implementation, OSDI, 1994, pp. 13–23. |
| [67] | Weng, Chu Liang; Da Lu, Xin: Heuristic scheduling for bag-of-tasks applications in combination with QoS in the computational grid, Future gener. Comput. syst. 21, No. 1, 271-280 (2005) |
| [68] | Adianto Wibisono, Zhiming Zhao, Adam Belloum, Marian Bubak, A framework for interactive parameter sweep applications, in: Proc. of 8th Symp Cluster Computing and the Grid, CCGRID, 2008, pp. 481–490. |
| [69] | Wu, Guowei; Xu, Zichuan: Temperature-aware task scheduling algorithm for soft real-time multi-core systems, J. syst. Softw. 83, No. 12, 2579-2590 (2010) |
| [70] | Frances Yao, Alan Demers, Scott Shenker, A scheduling model for reduced CPU energy, in: Proc. of 36th IEEE Symp on Foundations of Computer Science, FOCS, 1995, pp. 374–382. · Zbl 0938.68533 |
| [71] | Ziliang Zong, Energy-efficient resource management for high-performance computing platforms, Ph.D. Thesis, Department of Computer Science and Software Engineering, Auburn University, 2008. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
