|Table of Contents|

[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 Ruiqi1;  2;  Zhu Chenyan1;  Cai Hailin1;  Zhou Jiawei1;  Jiang Junqiang1
1School of Information Science and Engineering, Hunan Institute of Science and Technology, Yueyang 414006, China
2College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
鲁睿其1;  2;  朱晨妍1;  蔡海林1;  周嘉伟1;  蒋军强1
1湖南理工学院信息科学与工程学院, 岳阳 414006; 2湖南大学信息科学与工程学院, 长沙 410082
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.
为了缩短工作流调度完工时间, 提出3种列表调度算法:分级和出度最早完成时间算法(LOEFT)、分级异构选择值算法(LHSV)和异构优先最早完成时间算法(HPEFT).主要思想是利用任务深度, 融合任务出度来准确分析任务优先级, 精确分配处理器, 实现时间优化.算法均分为3个阶段:任务分级、任务排序和处理器分配.任务分级阶段, 依据任务深度将工作流划分为若干独立的任务集;任务排序阶段, 利用任务出度计算出任务的异构优先排序值(HPRV), 并据其降序生成任务队列;处理器分配阶段, 将排序排列任务逐一分配至使其完工时间最小的处理器, 完成任务-处理器的映射.通过实际应用和随机工作流仿真, 证实3种算法可以有效地缩短工作流的完工时间, 且LOEFT表现最好.任务深度结合出度是缩短工作流调度完工时间的有效手段.

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.
Last Update: 2020-12-20