基于扩展的随机DAG的并行任务调度算法研究  

Parallel Tasks Scheduling Based on Expanded Stochastic DAG

作　　者：姜燕[1] 胡凯[1] 杨志斌[1] 张新宇[1] 

机构地区：[1]北京航空航天大学计算机学院

出　　处：《计算机科学》2008年第7期57-60,共4页Computer Science

基　　金：航空科学基金资助项目(20060151003)

摘　　要：针对并行程序结构产生任务计算量和通信量的随机性,提出了一种扩展的随机DAG模型。基于此模型对DAG调度中常用调度算法关键路径SCP(Static Critical Path)算法进行了详细的分析,提出了相应的扩展的随机DAG的调度方法SSCP(Stochastic Static Critical Path)算法。同时,给出了扩展的随机DAG中节点的EST(Earliest Start Time)计算方法,并以SCP算法为例进行实验模拟。实验结果表明,SSCP算法相对于SCP算法,减少了并行任务执行时间,并能更精确地预测任务调度的平均执行时间。Considering that fact the structure of parallel program can induce the randomcity of tasks＇ computing and communication cost,the definition of stochastic DAG is expanded. Some researches on parallel tasks scheduling algorithms have been done based on this expanded model. The typical algorithms （SCP） are anglicized in detail,SSCP algorithm for the expanded stochastic DAG is presented correspondingly. Then a method to compute the nodes~ EST is provided. And experiments have been done to simulate it. The experiments results indicate that a significant improvement in the average parallel execution times of expanded stochastic DAG can be achieved by the proposed approach and SSCP algorithm is able to more accurately predict the actual performance than the algorithm SCP.

关 键 词：扩展的随机DAG EST SCP算法 SSCP算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O415.5[自动化与计算机技术—计算机科学与技术]