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

针对并行程序结构产生任务计算量和通信量的随机性,提出了一种扩展的随机DAG模型.基于此模型对DAG调度中常用调度算法关键路径SCP(Static Critical Path)算法进行了详细的分析,提出了相应的扩展的随机DAG的调度方法SSCP(Stochastic Static Critical Path)算法.同时,给出了扩展的随机DAG中节点的EST(Earliest Start Time)计算方法,并以SCP算法为例进行实验模拟.实验结果表明,SSCP算法相对于SCP算法,减少了并行任务执行时间,并能更精确地预测任务调度的平均执行时间.

Parallel Tasks Scheduling Based on Expanded Stochastic DAG

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...