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

摘要

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