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

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