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

针对并行程序结构产生任务计算量和通信量的随机性，提出了一种扩展的随机dag模型。基于此模型对dag调度中常用调度算法关键路径scp（staticcriticalpath）算法进行了详细的分析，提出了相应的扩展的随机dag的调度方法sscp（stochasticstaticcriticalpath）算法。同时，给出了扩展的随机dag中节点的est（earlieststarttime）计算方法，并以scp算法为例进行实验模拟。实验结果表明，sscp算法相对于scp算法，减少了并行任务执行时间，并能