Energy-aware stochastic scheduling model with precedence constraints on DVFS-enabled processors

The stochastic scheduling of precedence-constrained jobs on a heterogeneous processor is a challenging problem that requires solutions with one or more optimized QoS parameters. In this work, an energy-aware stochastic algorithm is proposed to schedule the batch of precedence-constrained jobs on heterogeneous DVFS-enabled processors with the objective of optimizing turnaround time and energy consumption. The processing time of tasks in all jobs and their precedence-constraint times are governed by independent probability distributions. The performance of the proposed stochastic algorithm is compared with SHEFT and ECS based on randomly generated batches of different sizes. The experimental study reveals that the proposed algorithm significantly outperforms the SHEFT and ECS algorithms in terms of turnaround time and energy consumption.

PDF

___

[1] TOP 500 Supercomputers, TIANHE-2 November 2014 List. URL: http://www.top500.org/lists/2014/11/. Accessed on 8 May 2015.
[2] Venkatachalam V, Franz M. Power reduction techniques for microprocessor systems. ACM Comput Surv 2005; 37: 195-237.
[3] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1990.
[4] Leung JYT. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. New York, NY, USA: Chapman & Hall/CRC, 2004.
[5] Kwok YK, Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 1999; 31: 406-471.
[6] Topcuoglu H, Hariri S, Wu M. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE T Parall Distr 2002; 13: 260-274.
[7] Zhu D, Melhem R, Childers B. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems. IEEE T Parall Distr 2003; 14: 686-700.
[8] Zhang S, Chatha KS. Approximation algorithm for the temperature-aware scheduling problem. In: IEEE/ACM 2007 Computer-Aided Design Conference; 48 November 2007; San Jose, CA. Piscataway, NJ, USA: IEEE/ACM. pp. 281-288.
[9] Lee YC, Zomaya A. Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE T Parall Distr 2011; 22: 1374-1381.
[10] Li K. Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers. IEEE T Comput 2012; 61: 1668-1681.
[11] Zhuravlev S, Saez JC, Blagodurov S, Fedorova A, Prieto M. Survey of energy-cognizant scheduling techniques. IEEE T Parall Distr 2013; 24: 1447-1464.
[12] Chekuri C, Motwani R, Natarajan B, Stein C. Approximation techniques for average completion time scheduling. SIAM J Comput 2001; 31: 146-166
[13] Skutella M, Uetz M. Stochastic machine scheduling with precedence constraints. SIAM J Comput 2005; 34: 788-802.
[14] Tang X, Li K, Liao G, Fang K, Wu F. A stochastic scheduling algorithm for precedence constrained tasks on grid. Future Gener Comp Sys 2011; 27: 1083-1091.
[15] Li K, Tang X, Veeravalli B, Li K. Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems. IEEE T Comput 2015; 64: 191-204.
[16] Moring RH, Schulz AS, Uetz M. Approximation in stochastic scheduling: the power of LP-based priority policies. J ACM 1999; 46: 924-942.
[17] Scharbrodt M, Schickingera T, Steger A. A new average case analysis for completion time scheduling. J ACM 2006; 53: 121-146.
[18] Kasahara H. STG: Standard Task Graph Set. Kasahara Laboratory, Waseda University, Tokyo, Japan. URL: http://www.kasahara.elec.waseda.ac.jp/schedule/. Accessed on 2 May 2015.