性能是应用的关键问题,调度又是性能之根本所在。计算机系统体系结构的发展以及对计算需求的持续增长,也不断给调度问题赋予新的内涵并且提出新的挑战,调度一直是并行与分布式计算研究的热点问题。按照划分方式,大致上可以将并行应用分成任务并行和数据并行两类。有向无环图(DAG)是表达任务并行应用的最常用模型。在数据并行应用中有一种重要类型,称为负载可任意划分的应用(DLA),这种应用所处理的负载可以被划分成任意多个负载片,每个负载片的尺寸也可以是任意,且每个负载片都可以被独立地处理。本文研究DAG和DLA在集群计算环境下的调度问题。经典的DAG调度模型是以传统意义上的并行机为目标平台的,因此其一些基本假设不适合于基于消息传递的集群环境。例如独立的通信子系统、异步且并发的通信等等。集群环境不象传统意义上的并行机那样可靠,而且有些集群系统没有一个独立的通信子系统。因此,有时需要用以同步模式进行通信的高层接口来隐藏异构性以及提高消息传输的可靠性。人们对基于异步模式通信的经典DAG调度问题进行了广泛而深入的研究并且提出了很多启发式算法,但是这些算法所产生的调度结果不能用于以同步模式通信的并行程序。本文分析了同步通信模式给DAG的调度带来的问题,并提出了一个基于参数关系图的调度算法PRGSC。该算法通过在调度的过程中维护任务的时间参数之间的关系来检测死锁,该方法不增加调度算法的复杂度并可以用于其他算法。PRGSC算法在调度一个节点时既考虑了对未调度部分的影响也考虑了对已调度部分的影响,因此能降低重要节点的运行时间而降低整个应用的运行时间。实验表明,本文所提出的PRGSC算法比以往的算法有更好的调度质量。以往关于DLA调度的研究,都是基于应用对负载的划分是没有交叉的、完全的前提,但现实中的一些应用可能要求划分是重叠的或者是每个处理器还需要一些辅助信息。本文用控制信息表示除了要处理的负载之外为了完成计算所必须的重叠的或辅助的信息。本文研究了这种有控制信息的DLA的调度问题,分别在主处理器(拥有负载的处理器)有前端和没有前端两种平台上,分析了平均划分、LIFO和FIFO三种调度策略,得到了它们的解析解。讨论了三种策略的可用处理器数目的范围,并得到了使处理时间最小的最优处理器数目。基于这些解析解,分析了在这个新模型下三种策略各自所具有的性质,并在此基础上对这三种策略的调度性能进行了严格的比较分析。我们的研究结果表明,与忽略控制信息的情况不同,无论主处理器是否有前端,在考虑控制信息的情况下,FIFO总是能获得这三种调度策略中的最好解。这一结论也说明了在模型中引入控制信息的重要性。负载可任意划分应用的调度问题中,有两种分配负载的策略。一种是一个处理器在开始处理负载之前得到全部数据,被称为一次分配策略。另外一种是分成多次向处理器发送负载。这种被称为多次分配的调度策略能更好地重叠通信和计算而最终降低整个应用的响应时间。基于多次分配的调度比一次分配更难分析,以往的研究中忽略了对处理结果的传输。本文提出了一个基于多次通信策略的算法,称为CAMR算法,它通过交替地传输输入数据和接收处理结果,更好地重叠计算和通信而降低整个应用的响应时间。仿真结果表明,与广泛采用的LIFO和FIFO算法相比,CAMR算法可以通过增加分配的次数而使用更少的资源获得更好的调度质量。