计算机工程 ›› 2008, Vol. 34 ›› Issue (24): 52-54.doi: 10.3969/j.issn.1000-3428.2008.24.018

• 软件技术与数据库 • 上一篇    下一篇

基于扩展的随机DAG的EST估算与任务调度

胡 凯,姜 燕,杨志斌,张新宇   

  1. (北京航空航天大学计算机学院,北京 100083)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-12-20 发布日期:2008-12-20

EST Estimation and Tasks Scheduling Based on Expanded Stochastic DAG

HU Kai, JIANG Yan, YANG Zhi-bing, ZHANG Xin-yu   

  1. (School of Computer, Beijing University of Aeronautics and Astronautics, Beijing 100083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-12-20 Published:2008-12-20

摘要: 针对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

中图分类号: