摘要： 针对DAG调度算法中采取多次执行后的平均值估算任务的EST值问题，通过对DAG调度中常用的调度算法ETF算法进行分析提出基于扩展的随机DAG的调度方法SETF，给出扩展的随机DAG中节点的EST计算方法，以标准方差和平均值之和的数学期望表示，并以ETF算法为例进行实验模拟。实验结果表明，SETF算法相对于ETF算法，减少并行任务执行时间，并能更精确地预测任务调度的平均执行时间。

关键词: 扩展的随机DAG, EST时间, ETF算法, SETF算法

Abstract: Considering the fact that the EST value in scheduling DAG is composed of the means of computation and communication time, some researches on parallel tasks scheduling algorithms are done while one typical algorithm ETF is analyzed, and SETF algorithms for the expanded stochastic DAG is presented correspondingly. Then a method to compute the nodes’ EST is provided. And experiments are done to simulate it. Experimental results indicate that a significant improvement in the average parallel execution times of expanded stochastic DAG can be achieved by the proposed approaches and it is able to more accurately predict the actual performance than the algorithms ETF.

Key words: expanded stochastic DAG, EST, ETF algorithm, SETF algorithm

中图分类号: 

• TP393