基于偶图匹配的多处理机任务调度启发算法

来源 :郑州大学 | 被引量 : 0次 | 上传用户:WZY86512
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
并行与分布式系统代表着计算机技术的发展方向,与其相关的研究工作引起了人们广泛的关注与重视。长期以来,并行与分布式系统面临的一个主要问题是计算效率不高。而对多处理机上的作业调度的研究是发掘并行与分布式系统的计算效率的一个重要途径,因此对多处理机任务调度算法的研究就具有了十分重要的意义。 由于多处理机调度问题的NP完全性,启发式算法的研究在理论与应用上具有明显的现实意义。本文对具有高通讯延迟的多处理机系统(机群系统)上的任务调度的启发式算法进行了研究,提出了新的基于偶图匹配的启发策略,讨论了偶图匹配与调度的关系,给出了基于该启发策略的调度算法。通过对比分析与实验,表明该算法是简洁和高效的,并进一步拓宽了解决问题的途径。本文的主要工作如下: 1.讨论并论述了与多处理机任务调度有关的基本概念和已有的一些 启发策略与相关算法; 2.提出并论证了“处理机数量的合理性”的概念; 3.建立并论述了任务图(DAG)的调度与其偶图匹配的对应关系; 4.提出了基于偶图匹配的启发策略的新的调度算法; 5.给出了该算法的解算示例以及与其他算法的分析对比与实验。
其他文献
无线自组网是一个无中心自组织的临时多跳无线网络。与传统的无线网络相比,无线自组网不需要固定基础设施的支持,可以随时随地动态部署,为军事通信、灾难恢复等需要临时通信
塞拉利昂和平学校(Sierra Leone School of Peace)是塞拉里昂一所著名的国立中学。自1990年以来,每学期新生入学人数逐年增加,而且近年来出现大幅度增长趋势。由于学生人数的过
信任管理是一项用来实现开放网络环境下实体间授权的重要技术。它通过凭证来描述网络中实体之间的信任关系,在实现授权算法时,通过搜索信任网络中的凭证,构建凭证链来建立起