题目：基于扩展随机DAG的任务性能预测与调度的研究与实现

在并行计算领域中，常用有向无环图DAG(Directed Acyclic Graph)模型来表示并行任务及其依赖关系，以支持多处理机并行任务调度。带权值的DAG模型主要定义了各个任务间的前驱后继依赖关系和每个任务的运行时间。但是在早期的研究中，它并没有包含每个任务之间的通信时间。近些年来，由于网络和计算机技术的飞速发展，在网络并行计算环境中任务间的通信延迟越来越成为一个不可忽略的现实影响因素，从而给并行调度领域中启发式DAG调度带来了新的问题。事实上，并行程序结构和分布式计算环境一样，也会使并行任务的计算时间和通信时间产生随机性。基于此，本文引入了一种扩展的随机DAG模型，并通过实验和理论分析验证了此模型的合理性。基于此模型，本文对任务性能预测和任务调度问题进行了研究和分析。在扩展的随机DAG模型生成时，需要量化两个非常重要的输入参数：任务节点的计算时间和通信时间。过去国内外大部分学者的研究均集中在DAG调度算法上的优化和改进，很少关注这方面的研究。针对此问题，本文提出了通过基于源码和系统负载分析的任务性能预测方法来获得任务节点的计算时间和通信时间，从而生成对应并行程序的扩展随机DAG模型。最后，基于扩展的随机DAG模型，实现了三种调度算法：SETF算法、SSCP算法和SSTL算法，采用平均值和偏移量之和来表示任务的计算时间和通信时间。实验结果表明，基于此模型进行任务调度，相对于采用平均值表示任务的计算时间和通信时间的任务调度算法，可以减少并行任务执行时间，提高并行程序的执行效率，并且更好地实现并行计算负载平衡。