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

摘要：

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

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

所属期刊栏目：35

分类号：TP3;C96

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

在线出版日期：2008-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：57-60