A static task scheduling algorithm for heterogeneous systems based on merging tasks and critical tasks

作者：Zhou, Naqin^*; Qi, Deyu; Wang, Xinyang; Zheng, Zhishuo

来源：Journal of Computational Methods in Sciences and Engineering, 2017, 17(4): 715-732.

DOI：10.3233/JCM-170755

• DAG scheduling
• Heterogeneous systems
• Static scheduling
• Task graph
• Task-scheduling

A novel task scheduling algorithm called Merge Tasks and Predict Earliest Finish Time (MTPEFT) has been proposed for static task scheduling in a heterogeneous computing environment. The algorithm merges tasks satisfying constraints and assigns the best processor for the node that has at least one immediate successor as the critical node, thereby effectively reducing the schedule length without increasing the algorithm time complexity. Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed, and comparisons are made based on the scheduling length ratio, robustness and frequency of the best result. The results show that the MTPEFT algorithm outperforms the PEFT, CPOP and HEFT algorithms in terms of the schedule length ratio, frequency of the best result and robustness while maintaining the same time complexity.

• 出版日期2017
• 单位华南理工大学