论文部分内容阅读
异构机群系统利用工作站和个人计算机进行分布式并行处理,以较低的成本完成大规模、复杂问题的计算处理。相对于单一的并行计算机,异构机群系统具有较高的性价比,并且非常具有发展前景,但是同时也提出了许多富有挑战性的问题,任务调度就是其中的一个重要问题。如果任务调度问题得不到有效解决,那么可能导致异构机群系统效率低下,甚至可能不如单个计算机,严重的可能导致计算失效。可分负载调度具有广泛的应用背景,且相对简单和易于分析,近几年得到了比较广泛的研究与应用。现有的异构机群系统调度算法大多是针对同构全互连机群系统设计的,很少考虑到处理机具有不同的通信、存储和计算能力等实际因素。对于处理机具有不同的计算速率、通信速率、通信延迟和存储能力的异构机群系统,本文研究可分负载调度算法及其性能。在均匀多轮调度算法UMR的基础上,本文充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性,通过允许计算和通信操作重叠执行,采取多次并行分配计算任务的方法,提出一种可分负载多轮调度算法UMRLM。算法分析与实验结果表明,一方面,UMRLM算法在调度时间上仍能取得与UMR算法相当的近似最优的调度时间长度;另一方面,实验结果表明当负载量较大,使得某一轮调度分配给某个处理机的负载超出了该处理机的实际可用内存容量时,UMR算法无法继续执行,而本文提出的算法由于考虑了实际可用内存的有限性而不受此限制,能够处理更大规模的应用负载、实用性更强。针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题计算处理完毕后需要向主处理机节点返回大量结果信息的实际情况,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出了一种带返回信息的调度轮数可变的可分负载多轮调度算法。算法分析与实验结果表明,该算法处理具有返回结果信息的应用的调度性能明显优于已有的可分负载多轮调度算法UMR,并获得近似最优的调度轮数,能够适应更为广泛的应用的调度问题。