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

来源 :郑州大学 | 被引量 : 0次 | 上传用户:WZY86512
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
并行与分布式系统代表着计算机技术的发展方向,与其相关的研究工作引起了人们广泛的关注与重视。长期以来,并行与分布式系统面临的一个主要问题是计算效率不高。而对多处理机上的作业调度的研究是发掘并行与分布式系统的计算效率的一个重要途径,因此对多处理机任务调度算法的研究就具有了十分重要的意义。 由于多处理机调度问题的NP完全性,启发式算法的研究在理论与应用上具有明显的现实意义。本文对具有高通讯延迟的多处理机系统(机群系统)上的任务调度的启发式算法进行了研究,提出了新的基于偶图匹配的启发策略,讨论了偶图匹配与调度的关系,给出了基于该启发策略的调度算法。通过对比分析与实验,表明该算法是简洁和高效的,并进一步拓宽了解决问题的途径。本文的主要工作如下: 1.讨论并论述了与多处理机任务调度有关的基本概念和已有的一些 启发策略与相关算法; 2.提出并论证了“处理机数量的合理性”的概念; 3.建立并论述了任务图(DAG)的调度与其偶图匹配的对应关系; 4.提出了基于偶图匹配的启发策略的新的调度算法; 5.给出了该算法的解算示例以及与其他算法的分析对比与实验。
其他文献
该文在综述了人体生物特征识别系统的基础上,对面向中医诊断的自动舌像处理系统做了研究,并对其中部分功能的实现进行分析和试验.该文重点论述了舌像库的建立,舌苔的分割以及
无线自组网是一个无中心自组织的临时多跳无线网络。与传统的无线网络相比,无线自组网不需要固定基础设施的支持,可以随时随地动态部署,为军事通信、灾难恢复等需要临时通信
塞拉利昂和平学校(Sierra Leone School of Peace)是塞拉里昂一所著名的国立中学。自1990年以来,每学期新生入学人数逐年增加,而且近年来出现大幅度增长趋势。由于学生人数的过
该论文主要论述在IPv4协议中加入网络层安全机制.在论文中,分析了安全机制在网络各层的实现代价,并着重分析了在网络层实现相应安全机制的可行性;然后提出了一种可移植性、开
P2P网络作为一种构建于底层通讯网络之上的应用层网络,具有分布式、互操作性、自组织性等特性,已经成为一种互联网上重要的资源组织方式。同时,随着服务计算的不断发展,Web服务作
该文首先从分布式数据库及其安全的有关概念入手,分析了分布式数据库的优点,客户/服务器体系结构,数据库安全存在的问题,对数据库安全的威胁,以及数据库安全的主要防卫措施.
软件分布共享存储系统是分布式存储系统和共享存储系统的体系结构的融合和发展,兼具了两类系统的优点,克服了各自的缺点,以其易编程性和易构造性成为了高性能计算技术的研究
该文就网络安全技术的管理和入侵检测两个方面进行了研究和探讨,设计并实现一个分布式网络安全管理框架DNSMF(Distributed Network Security Management Framework).该文首先
信任管理是一项用来实现开放网络环境下实体间授权的重要技术。它通过凭证来描述网络中实体之间的信任关系,在实现授权算法时,通过搜索信任网络中的凭证,构建凭证链来建立起
该文结合哈工大探索一号小卫星(TS-1)星载计算机系统的研制,对小卫星星载计算机系统的结构和功能进行了介绍,并对系统可靠度进行了计算,证明是能满足两年内可靠度达到0.95的