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

计算机工程与科学

• 高性能计算 • 上一篇    下一篇

并行任务图的优化调度算法

李于锋1,2,莫则尧2,肖永浩1,熊敏1   

  1. (1.中国工程物理研究院计算机应用研究所,四川 绵阳 621900;
    2.北京应用物理与计算数学研究所,北京 100094)

     
  • 收稿日期:2018-10-17 修回日期:2018-12-12 出版日期:2019-06-25 发布日期:2019-06-25
  • 基金资助:

    国家重点研发项目(2016YFB0201504,2018YFB0703903)

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

摘要:

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对ForkJoin类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。
 
 

关键词: 并行任务图, 调度算法, 优化调度

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