论文部分内容阅读
并行与分布式系统代表着计算机技术的发展方向,与其相关的研究工作引起了人们广泛的关注与重视。长期以来,并行与分布式系统面临的一个主要问题是计算效率不高。而对多处理机上的作业调度的研究是发掘并行与分布式系统的计算效率的一个重要途径,因此对多处理机任务调度算法的研究就具有了十分重要的意义。 由于多处理机调度问题的NP完全性,启发式算法的研究在理论与应用上具有明显的现实意义。本文对具有高通讯延迟的多处理机系统(机群系统)上的任务调度的启发式算法进行了研究,提出了新的基于偶图匹配的启发策略,讨论了偶图匹配与调度的关系,给出了基于该启发策略的调度算法。通过对比分析与实验,表明该算法是简洁和高效的,并进一步拓宽了解决问题的途径。本文的主要工作如下: 1.讨论并论述了与多处理机任务调度有关的基本概念和已有的一些 启发策略与相关算法; 2.提出并论证了“处理机数量的合理性”的概念; 3.建立并论述了任务图(DAG)的调度与其偶图匹配的对应关系; 4.提出了基于偶图匹配的启发策略的新的调度算法; 5.给出了该算法的解算示例以及与其他算法的分析对比与实验。