×

Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments. (English) Zbl 1459.68025

Summary: Data centers for cloud computing must accommodate numerous parallel task executions simultaneously. Therefore, data centers have many virtual machines (VMs). Minimizing the scheduling length of parallel task sets becomes a critical requirement in cloud computing systems. In this study, we propose an efficient priority and relative distance (EPRD) algorithm to minimize the task scheduling length for precedence constrained workflow applications without violating the end-to-end deadline constraint. This algorithm consists of two processes. First, a task priority queue is established. Then, a VM is mapped for a task in accordance with its relative distance. The proposed method can effectively improve VM utilization and scheduling performance. Extensive rigorous experiments based on randomly generated and real-world workflow applications demonstrate that the resource reduction rate and scheduling length of the EPRD algorithm significantly surpass those of existing algorithms.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68M11 Internet topics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [Online], Available. (http://marketresearchmedia.com/?p=839, Jan. 2014).
[2] Ghemawat, S.; Gobioff, H.; Leung, S.-T., The google file system, ACM SIGOPS Oper. Syst. Rev., 37, 5, 29-43 (2003)
[3] Dean, J.; Ghemawat, S., MapReduce: simplified data processing on large clusters, Commun. ACM, 51, 1, 107-113 (2008)
[4] Shvachko, K.; Kuang, H.; Radia, S.; Chansler, R., The hadoop distributed file system., MSST, vol. 10, 1-10 (2010)
[5] Zaharia, M.; Chowdhury, M.; Franklin, M. J.; Shenker, S.; Stoica, I., Spark: cluster computing with working sets., HotCloud, 10, 10-10, 95 (2010)
[6] Garey, M. R.; Johnson, D. S., Computers and intractability (1979) · Zbl 0411.68039
[7] Arunarani, A.; Manjula, D.; Sugumaran, V., Task scheduling techniques in cloud computing: aliterature survey, Future Gener. Comput. Syst., 91, 407-415 (2019)
[8] Chen, Y.; Li, K.; Yang, W.; Xiao, G.; Xie, X.; Li, T., Performance-aware model for sparse matrix-matrix multiplication on the sunway TaihuLight supercomputer, IEEE Trans. Parallel Distrib. Syst., 30, 4, 923-938 (2019)
[9] Chen, C.; Li, K.; Ouyang, A.; Li, K., FlinkCL: an OpenCL-based in-memory computing architecture on heterogeneous CPU-GPU clusters for big data, IEEE Trans. Comput., 67, 12, 1765-1779 (2018) · Zbl 07033438
[10] Li, K., Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environment, Future Gener. Comput. Syst., 82, 591-605 (2018)
[11] Maqsood, T.; Tziritas, N.; Loukopoulos, T.; Madani, S. A.; Khan, S. U.; Xu, C.-Z.; Zomaya, A. Y., Energy and communication aware task mapping for MPSoCs, J. Parallel Distrib. Comput., 121, 71-89 (2018)
[12] Chen, J.; Li, K.; Bilal, K.; Li, K.; Philip, S. Y., A bi-layered parallel training architecture for large-scale convolutional neural networks, IEEE Trans. Parallel Distrib. Syst., 30, 5, 965-976 (2018)
[13] Wang, B.; Song, Y.; Cao, J.; Cui, X.; Zhang, L., Improving task scheduling with parallelism awareness in heterogeneous computational environments, Future Gener. Comput. Syst., 94, 419-429 (2019)
[14] ul Islam, F. M.M.; Lin, M.; Yang, L. T.; Choo, K.-K. R., Task aware hybrid DVFS for multi-core real-time systems using machine learning, Inf. Sci., 433, 315-332 (2018)
[15] Chen, J.; Li, K.; Rong, H.; Bilal, K.; Li, K.; Philip, S. Y., A periodicity-based parallel time series prediction algorithm in cloud computing environments, Inf. Sci., 496, 506-537 (2019)
[16] Qureshi, B., Profile-based power-aware workflow scheduling framework for energy-efficient data centers, Future Gener. Comput. Syst., 94, 453-467 (2019)
[17] Selvitopi, O.; Demirci, G. V.; Turk, A.; Aykanat, C., Locality-aware and load-balanced static task scheduling for mapreduce, Future Gener. Comput. Syst., 90, 49-61 (2019)
[18] Huang, X.; Zhang, L.; Li, R.; Wan, L.; Li, K., Novel heuristic speculative execution strategies in heterogeneous distributed environments, Comput. Electr. Eng., 50, 166-179 (2016)
[19] Chen, C.; Li, K.; Ouyang, A.; Zeng, Z.; Li, K., GFlink: an in-memory computing architecture on heterogeneous CPU-GPU clusters for big data, IEEE Trans. Parallel Distrib. Syst., 29, 6, 1275-1288 (2018)
[20] Zhang, P.; Zhou, M., Dynamic cloud task scheduling based on a two-stage strategy, IEEE Trans. Autom. Sci. Eng., 15, 2, 772-783 (2017)
[21] Chen, H.; Zhu, X.; Qiu, D.; Liu, L.; Du, Z., Scheduling for workflows with security-sensitive intermediate data by selective tasks duplication in clouds, IEEE Trans. Parallel Distrib. Syst., 28, 9, 2674-2688 (2017)
[22] Zhang, L.; Li, K.; Li, C.; Li, K., Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems, Inf. Sci., 379, 241-256 (2017)
[23] Tong, Z.; Chen, H.; Deng, X.; Li, K.; Li, K., A novel task scheduling scheme in a cloud computing environment using hybrid biogeography-based optimization, Soft Comput., 1-20 (2018)
[24] Xu, Y.; Li, K.; He, L.; Zhang, L.; Li, K., A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems, IEEE Trans. Parallel Distrib. Syst., 26, 12, 3208-3222 (2015)
[25] Ali, H.; Tariq, U. U.; Zheng, Y.; Zhai, X.; Liu, L., Contention & energy-aware real-time task mapping on NoC based heterogeneous MPSoCs, IEEE Access, 6, 75110-75123 (2018)
[26] Zhang, L.; Li, K.; Zheng, W.; Li, K., Contention-aware reliability efficient scheduling on heterogeneous computing systems, IEEE Trans. Sustain. Comput., 3, 182-194 (2018)
[27] Topcuoglu, H. R.; Hariri, S.; Wu, M., Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE Trans. Parallel Distrib. Syst., 13, 3, 260-274 (2002)
[28] Mezmaz, M.; Melab, N.; Kessaci, Y.; Lee, Y. C.; Talbi, E.-G.; Zomaya, A. Y.; Tuyttens, D., A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, J. Parallel Distrib. Comput., 71, 11, 1497-1508 (2011)
[29] Ramakrishnan, L.; Chase, J. S.; Gannon, D.; Nurmi, D.; Wolski, R., Deadline-sensitive workflow orchestration without explicit resource control, J. Parallel Distrib. Comput., 71, 3, 343-353 (2011)
[30] Durillo, J. J.; Nae, V.; Prodan, R., Multi-objective energy-efficient workflow scheduling using list-based heuristics, Future Gener. Comput. Syst., 36, 221-236 (2014)
[31] Xiaoyong, T.; Li, K.; Zeng, Z.; Veeravalli, B., A novel security-driven scheduling algorithm for precedence-constrained tasks in heterogeneous distributed systems, IEEE Trans. Comput., 60, 7, 1017-1029 (2011) · Zbl 1368.68160
[32] Van den Bossche, R.; Vanmechelen, K.; Broeckhove, J., Online cost-efficient scheduling of deadline-constrained workloads on hybrid clouds, Future Gener. Comput. Syst., 29, 4, 973-985 (2013)
[33] Xiao, G.; Li, K.; Chen, Y.; He, W.; Zomaya, A.; Li, T., CASpMV: a customized and accelerative SpMV framework for the Sunway TaihuLight, IEEE Trans. Parallel Distrib. Syst. (2019)
[34] Woodley, A.; Tang, L.-X.; Geva, S.; Nayak, R.; Chappell, T., Parallel k-tree: a multicore, multinode solution to extreme clustering, Future Gener. Comput. Syst., 99, 333-345 (2019)
[35] Peng, H.; Wen, W.-S.; Tseng, M.-L.; Li, L.-L., Joint optimization method for task scheduling time and energy consumption in mobile cloud computing environment, Appl. Soft Comput., 80, 534-545 (2019)
[36] Wu, H.; Hua, X.; Li, Z.; Ren, S., Resource and instance hour minimization for deadline constrained DAG applications using computer clouds, IEEE Trans. Parallel Distrib. Syst., 27, 3, 885-899 (2015)
[37] [Online] Available. (https://confluence.pegasus.isi.edu/display/pegasus/workflowgenerator, 2014).
[38] Bharathi, S.; Chervenak, A.; Deelman, E.; Mehta, G.; Su, M.-H.; Vahi, K., Characterization of scientific workflows, 2008 Third Workshop on Workflows in Support of Large-Scale Science, 1-10 (2008), IEEE
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.