[1] Lu Ruiqi, Zhu Chenyan, Cai Hailin, et al. Time optimization for workflow schedulingbased on the combination of task attributes [J]. Journal of Southeast University (English Edition), 2020, 36 (4): 399-406. [doi:10.3969/j.issn.1003-7985.2020.04.005]

Copy

Time optimization for workflow schedulingbased on the combination of task attributes()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

36

Issue:

2020 4

Page:

399-406

Research Field:

Computer Science and Engineering

Publishing date:

2020-12-20

Info

Title:

Time optimization for workflow schedulingbased on the combination of task attributes

Author(s):

Lu Ruiqi¹;  2;  Zhu Chenyan¹;  Cai Hailin¹;  Zhou Jiawei¹;  Jiang Junqiang¹

¹School of Information Science and Engineering, Hunan Institute of Science and Technology, Yueyang 414006, China
²College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China

Keywords:

directed acyclic graph;  workflow scheduling;  task depth;  task out-degree;  list heuristic

PACS:

TP393

DOI:

10.3969/j.issn.1003-7985.2020.04.005

Abstract:

In order to reduce the scheduling makespan of a workflow, three list scheduling algorithms, namely, level and out-degree earliest-finish-time(LOEFT), level heterogeneous selection value(LHSV), and heterogeneous priority earliest-finish-time(HPEFT)are proposed. The main idea hidden behind these algorithms is to adopt task depth, combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization. Each algorithm is divided into three stages: task levelization, task prioritization, and processor allocation. In task levelization, the workflow is divided into several independent task sets on the basis of task depth. In task prioritization, the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree, and a non-increasing ranking queue is generated on the basis of HPRV. In processor allocation, the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping. Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan, and the LOEFT algorithm performs the best, and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.

References:

[1] Li K L, Tang X Y, Li K Q. Energy-efficient stochastic task scheduling on heterogeneous computing systems[J].IEEE Transactions on Parallel and Distributed Systems, 2014, 25(11): 2867-2876. DOI:10.1109/TPDS.2013.270.
[2] Jiang J, Lin Y, Xie G, et al. Energy optimization heuristic for deadline-constrained workflows in heterogeneous distributed systems[J].Journal of Computer Research and Development, 2016, 53(7): 1503-1516.(in Chinese)
[3] Tanenbaum A. Modern operating systems[M]. Beijing: China Machine Press, 2009.
[4] Yang G W, Jin H, Li M L, et al. Grid computing in China[J].Journal of Grid Computing, 2004, 2(2): 193-206. DOI:10.1007/s10723-004-4201-2.
[5] To W M, Lai L S L, Chung A W L. Cloud computing in China: Barriers and potential[J].IT Professional, 2013, 15(3): 48-53. DOI:10.1109/mitp.2012.64.
[6] Shi W S, Cao J, Zhang Q, et al. Edge computing: Vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5): 637-646. DOI:10.1109/jiot.2016.2579198.
[7] Huang B, Xia W, Zhang Y, et al. Dependent task assignment algorithm based on particle swarm optimization and simulated annealing in ad-hoc mobile cloud[J]. Journal of Southeast University(English Edition), 2018, 34(4):430-438.
[8] Deelman E, Gannon D, Shields M, et al. Workflows and e-Science: An overview of workflow system features and capabilities[J].Future Generation Computer Systems, 2009, 25(5): 528-540. DOI:10.1016/j.future.2008.06.012.
[9] Bharathi S, Chervenak A, Deelman E, et al. Characterization of scientific workflows[C]// Third Workshop on Workflows in Support of Large-Scale Science. Austin, TX, USA, 2008: 1-10.
[10] Jiang J Q, Lin Y P, Xie G Q, et al. Time and energy optimization algorithms for the static scheduling of multiple workflows in heterogeneous computing system[J].Journal of Grid Computing, 2017, 15(4): 435-456. DOI:10.1007/s10723-017-9391-5.
[11] Oliveira D, Brinkmann A, Rosa N, et al. Performability evaluation and optimization of workflow applications in cloud environments[J].Journal of Grid Computing, 2019, 17(4): 749-770. DOI:10.1007/s10723-019-09476-0.
[12] Jia Y H, Chen W N, Yuan H Q, et al. An intelligent cloud workflow scheduling system with time estimation and adaptive ant colony optimization[J].IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, pp(99): 1-16. DOI:10.1109/tsmc.2018.2881018.
[13] Zhou J L, Wang T, Cong P J, et al. Cost and makespan-aware workflow scheduling in hybrid clouds[J].Journal of Systems Architecture, 2019, 100: 101631. DOI:10.1016/j.sysarc.2019.08.004.
[14] Zhao L P, Ren Y Z, Sakurai K. Reliable workflow scheduling with less resource redundancy[J].Parallel Computing, 2013, 39(10): 567-585. DOI:10.1016/j.parco.2013.06.003.
[15] Garg R, Mittal M, Son L H. Reliability and energy efficient workflow scheduling in cloud environment[J].Cluster Computing, 2019, 22(4): 1283-1297. DOI:10.1007/s10586-019-02911-7.
[16] Zhou J L, Zhang M, Sun J, et al. DRHEFT: Deadline-constrained reliability-aware HEFT algorithm for real-time heterogeneous MPSoC systems[J/OL]. IEEE Transactions on Reliability, 2020.http://ieeexplore.ieee.org/abstract/document/9063674. DOI: 10.1109/TR.2020.2981419.
[17] Topcuoglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274. DOI:10.1109/71.993206.
[18] Bittencourt L F, Sakellariou R, Madeira E R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[C]// Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing. IEEE Computer Society, 2010: 27-34.
[19] Wang X L, Huang H B, Deng S. List scheduling algorithm for static task with precedence constraints for cyber-physical systems[J]. Acta Automatica Sinica, 2012, 38(11): 1870. DOI:10.3724/sp.j.1004.2012.01870.
[20] Xie G Q, Li R F, Li K Q. Heterogeneity-driven end-to-end synchronized scheduling for precedence constrained tasks and messages on networked embedded systems[J]. Journal of Parallel and Distributed Computing, 2015, 83: 1-12. DOI:10.1016/j.jpdc.2015.04.005.
[21] Canon L C, Jeannot E, Sakellariou R, et al. Comparative evaluation of the robustness of DAG scheduling heuristics[M]//Grid Computing. Boston, MA, USA: Springer US, 2008: 73-84. DOI:10.1007/978-0-387-09457-1_7.
[22] Sih G C, Lee E A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures[J]. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(2): 175-187. DOI:10.1109/71.207593.
[23] Daoud M I, Kharma N. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems[J]. Journal of Parallel and Distributed Computing, 2008, 68(4): 399-409. DOI:10.1016/j.jpdc.2007.05.015.
[24] Sun J, Yin L, Zou M H, et al. Makespan-minimization workflow scheduling for complex networks with social groups in edge computing[J]. Journal of Systems Architecture, 2020, 108: 101799. DOI:10.1016/j.sysarc.2020.101799.
[25] Huang K C, Gu D S, Liu H C, et al. Task clustering heuristics for efficient execution time reduction in workflow scheduling[J]. Journal of Computers, 2017, 28(1): 43-56.
[26] Gupta I, Kumar M S, Jana P K. Task duplication-based workflow scheduling for heterogeneous cloud environment[C]// 2016 Ninth International Conference on Contemporary Computing(IC3). Noida, India, 2016: 1-7. DOI: 10.1109/IC3.2016.7880207.
[27] TGGTCE. Task graph generator[EB/OL].(2020-05-28)[2020-08-10]. http://sourceforge.net/projects/taskgraphgen/.
[28] Tang Z, Qi L, Cheng Z Z, et al. An energy-efficient task scheduling algorithm in DVFS-enabled cloud environment[J]. Journal of Grid Computing, 2016, 14(1): 55-74. DOI:10.1007/s10723-015-9334-y.
[29] Mei J, Li K L, Zhou X, et al. Fault-tolerant dynamic rescheduling for heterogeneous computing systems[J]. Journal of Grid Computing, 2015, 13(4): 507-525. DOI:10.1007/s10723-015-9331-1.

Memo

Memo:

Biographies: Lu Ruiqi(1988—), female, Ph.D. candidate;Jiang Junqiang(corresponding author), male, doctor, associate professor, jqjiang@hnist.edu.cn.
Foundation items: The Natural Science Foundation of Hunan Province(No.2018JJ2153), the Scientific Research Fund of Hunan Provincial Education Department(No.18B356), the Foundation of the Research Center of Hunan Emergency Communication Engineering Technology(No.2018TP2022), the Innovation Foundation for Postgraduate of the Hunan Institute of Science and Technology(No.YCX2018A06).
Citation: Lu Ruiqi, Zhu Chenyan, Cai Hailin, et al.Time optimization for workflow scheduling based on the combination of task attributes[J].Journal of Southeast University(English Edition), 2020, 36(4):399-406.DOI:10.3969/j.issn.1003-7985.2020.04.005.

Common functions