论文部分内容阅读
随着网格技术的深入研究与发展,地理上分布的异构资源可以通过高速互联网络连接起来,构建成一个完整的计算平台,人们可以利用这些计算资源处理复杂的并行分布式应用,而高效的网格任务调度则成为研究的热点和亟待解决的关键问题。在网格任务调度中,通信延迟不仅会导致任务之间相互等待,而且还会造成处理器结点空闲时间过多,是影响调度算法性能的一个至关重要的因素。除此之外,由于网格是一个异构型的计算环境,相同的任务在不同的计算资源上的执行开销是不可能完全相同的,随着调度过程的推进,任务结点的执行开销与通信开销都会变化,任务结点的权值也会随之变动。然而,静态指定的任务优先级无法反应这种变化,导致指定的任务优先级与实际优先级间存在误差。本文研究了网格环境下的静态任务调度策略,重点考虑通信延迟与任务优先级对调度算法性能的影响。主要工作包括以下两个方面:首先,结合表调度与基于复制的调度思想,提出了STDH(Selected Task-Duplicationfor Heterogeneous system:异构环境下的选择性任务复制)静态任务调度算法,通过冗余调度前驱任务到处理器的空闲时间段来减少任务之间通信延迟。有利于保持任务的并行性,提高处理器的利用率,从而缩短整个任务图的并行完成时间。实验结果表明了STDH算法在减少通信延迟缩短任务完成时间方面的有效性。其次,为确保每一步都能优先调度对整个任务完成时间影响最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法,在任务调度过程中动态更新任务结点的优先级,任务优先级计算过程与资源节点选取过程穿插进行,同时通过有效地利用处理器的空闲时间来复制任务,以减少通信开销,从而缩短整个任务图的执行时间。大量实验结果表明,本文算法优于HEFT算法和基于动态决策路径的任务调度算法。