On Effective Slack Reclamation in Task Scheduling for Energy Reduction
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Power consumed by modern computer systems, particularly servers in data centers has almost reached an unacceptable level. However, their energy consumption is often not justifiable when their utilization is considered; that is, they tend to consume more energy than needed for their computing related jobs. Task scheduling in distributed computing systems (DCSs) can play a crucial role in increasing utilization; this will lead to the reduction in energy consumption. In this paper, we address the problem of scheduling precedence-constrained parallel applications in DCSs, and present two energy- conscious scheduling algorithms. Our scheduling algorithms adopt dynamic voltage and frequency scaling (DVFS) to minimize energy consumption. DVFS, as an efficient power management technology, has been increasingly integrated into many recent commodity processors. DVFS enables these processors to operate with different voltage supply levels at the expense of sacrificing clock frequencies. In the context of scheduling, this multiple voltage facility implies that there is a trade-off between the quality of schedules and energy consumption. Our algorithms effectively balance these two performance goals using a novel objective function and its variant, which take into account both goals; this claim is verified by the results obtained from our extensive comparative evaluation study.
Abstract
Power consumed by modern computer systems, particularly servers in data centers has almost reached an unacceptable level. However, their energy consumption is often not justifiable when their utilization is considered; that is, they tend to consume more energy than needed for their computing related jobs. Task scheduling in distributed computing systems (DCSs) can play a crucial role in increasing utilization; this will lead to the reduction in energy consumption. In this paper, we address the problem of scheduling precedence-constrained parallel applications in DCSs, and present two energy- conscious scheduling algorithms. Our scheduling algorithms adopt dynamic voltage and frequency scaling (DVFS) to minimize energy consumption. DVFS, as an efficient power management technology, has been increasingly integrated into many recent commodity processors. DVFS enables these processors to operate with different voltage supply levels at the expense of sacrificing clock frequencies. In the context of scheduling, this multiple voltage facility implies that there is a trade-off between the quality of schedules and energy consumption. Our algorithms effectively balance these two performance goals using a novel objective function and its variant, which take into account both goals; this claim is verified by the results obtained from our extensive comparative evaluation study.
참고문헌 (27)
- Venkatachalam, V, "Power reduction techniques for microprocessor systems", ACM Computing Surveys, 37(3), pp.195~237 (2005)
- Kim, K. H, "Power aware scheduling of bag-oftasks applications with deadline constraints on DVSenabled clusters", Proc.of the 7th IEEE International Symposium on Cluster Computing and the Grid, pp.541~548 (2007)
- Zhu, D, "Scheduling with dynamic voltage", speed adjustment using slack reclamation in multiprocessor real-time systems, 2003, pp.14(7), 686~700
- Ge, R, "Performance-constrained distributed DVS scheduling for scientific applications on poweraware clusters", Proc.of the ACM, 2005, 34~44
- Chen, J. J, "Multiprocessor energyefficient scheduling for real-time tasks with different power characteristics", Proc.of International Conference on Parallel Processing, pp.13~20 (2005)
- Zhong, X, "Energy-aware modeling and scheduling for dynamic voltage scaling with statistical real-time guarantee", IEEE Trans.Computers, 56(3), pp.358~372 (2007)
- J. G. Koomey, "Estimating total power consumption by servers in the U.S. and the world", ~
- "Discovering multi-core: extending the benefits of Moore’s law" (2005)[URL]
- D. P. Bunde, "Power-aware scheduling for makespan and flow", Proc. the eighteenth annual ACM symposium on Parallelism in algorithms and architectures (2006)
- S. Darbha, "Optimal scheduling algorithm for distributed-memory machines", IEEE Trans. Parallel and Distributed System, 9(1), pp.87~95 (1998)
- A. Y. Zomaya, "Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues", IEEE Trans. Parallel Distrib. Syst., 10(8), pp.795~812 (1999)
- H. Topcuouglu, "Performance- Effective and Low-Complexity Task Scheduling for Heterogeneous Computing", IEEE Trans. Parallel Distrib. Syst., 13(3), pp.260~274 (2002)
- Y. C. Lee, "A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems", IEEE Trans. Parallel Distrib. Syst., 19(9), pp.1215~1223 (2008)
- Y. C. Lee, "Minimizing Energy Consumption for Precedence-constrained Applications Using Dynamic Voltage Scaling", Proceedings of the International Symposium on Cluster Computing and the Grid (CCGRID), pp.92~99 (2009)
- Intel, "Intel Pentium M Processor datasheet", ~ (2004)
- R. Min, "Dynamic Voltage Scaling Techniques for Distributed Microsensor Networks", Proc. IEEE Workshop on VLSI, pp.43~46 (2000)
- M.R. Garey, "Computers and Intractability: A Guide to the Theory of NP-Completeness", pp.238~239 (1979), W.H. Freeman and Co.
- Y. K. Kwok, "Benchmarking the Task Graph Scheduling Algorithms", Proc. First Merged Int’l Parallel Symposium, SPDP ‘98), pp.1998[DOI]
- D. Bozdag, "A task duplication based bottom-up scheduling algorithm for heterogeneous environments", Proc. Int’l Parallel and Distributed Processing Symp. (2005)
- AMD, "AMD Athlon™ 64 Processor Power and Thermal Data Sheet", ~ (2006)
- C. Pyron, "DFT advances in the Motorola's MPC7400, a PowerPCTM microprocessor", Proc. Int’l Test Conference, pp.137~146 (1999)
- D. R. Ditzel, "Power Reduction using LongRun2 in Transmeta's Efficeon Processor", Spring processor forum (2006)
- D. Zhu, "Power-aware scheduling for AND", OR graphs in real-time systems, 2004, pp.15(9), 849~864
- B. Rountree, "Bounding energy consumption in large-scale MPI programs", Proc. the ACM, 2007, ~
- M.-Y. Wu, "Hypertool: A Programming Aid for Message-Passing Systems", IEEE Trans. Parallel and Distributed Systems, 1(3), pp.330~343 (1990)
- R.E. Lord, "Solving Linear Algebraic Equations on an MIMD Computer", J. ACM, 30(1), pp.103~117 (1983)
- T.H. Cormen, "Introduction to Algorithms" (1990), MIT Press