• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Optimized scheduling algorithms for parallel task graphs

LI Yufeng1,2,MO Zeyao2,XIAO Yonghao1,XIONG Min1   

  1. (1.Institute of Computer Application,Chinese Academy of Engineering Physics,Mianyang 621900;
    2.Institute of Applied Physics and Computational Mathematics,Beijing 100094,China)
     
  • Received:2018-10-17 Revised:2018-12-12 Online:2019-06-25 Published:2019-06-25

Abstract:

Many complex application problems in scientific and engineering computing can be solved through scientific workflow technology, and these scientific workflows in supercomputing domain are modeled by parallel task graphs. Effective scheduling of parallel task graphs is significant for efficient execution of applications. We propose a scheduling  model of parallel task graphs under resource constraints. Some optimal scheduling conclusions are given for ForkJoin type parallel task graphs. In addition, we propose a new scheduling algorithm for general parallel task graphs. This algorithm considers the effect of data communication overhead on resource allocation and scheduling performance. We also improve the CPA algorithm under specific conditions. Our algorithms are compared with the commonly used CPR and CPA algorithms. Experimental results show that our new algorithms can achieve good scheduling results. The proposed scheduling algorithm and the optimal conclusions have reference significance for the development of high performance scheduling function for workflow application systems.
 

Key words: parallel task graph, scheduling algorithm, optimal scheduling