基于通信代价的网格资源调度算法

针对基于时间和预算限制的资源调度算法在调度数据密集型应用程序时存在的问题,提出一种新的基于通信代价的网格资源调度算法,综合考虑用户的时问限制和预算要求,根据用户作业的计算量与通信量选择具有一定计算能力,且通信代价较小的资源节点作为目标节点,通过减少此类程序提交到目标资源节点的通信代价,达到减少整个应用程序完成时间的目的。实验结果表明,该算法能够获得较好的性能。     

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟,通过任务复制的冗余,可以减少任务之间的通信开销,缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的;而基于任务复制调度算法往往会产生过多的复制任务,增大系统开销,甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题,因此本文提出了一种基于任务复制的网格资源调度算法,以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。     

负载控制的网格资源调度

针对网格环境下的系统负载管理,将网格系统模型描述为节点和通信链路组成的无向图.在此基础上,提出了节点和通信负载的度量方法,给出了相应的阈值定义以及网格负载水平的计算方法.由此构成了资源选择中对节点、通信链路的选择条件,实现节点、通信的负载控制;网格负载水平则是判定拒绝服务的条件,控制系统任务总量.针对该方法,设计了实现管理的体系结构,讨论了模型计算的时间周期,给出了实现控制的调度算法.实验结果表明,该方法在提高系统吞吐量、控制调度失败率等方面表现出良好的性能,特别是在重载情况下,提高了系统的运行效率,增强了系统的健壮性.     

基于网格资源预测的任务优先级调度算法

根据网格工作流中任务的依赖关系和截止时间,以及资源的有效度和MIPS（每秒百万条指令）,提出基于网格资源预测的任务优先级调度算法。把网格任务工作流抽象为有向无环图,找到该工作流的关键路径,计算每个任务的最迟开始执行时间,作为任务的优先级。在算法中考虑用户的要求和资源的类型,以及任务调度失败后重新分配的问题。实验验证了该算法的有效性。     

网格环境下基于信任模型的动态级调度

网格用户、资源和服务的不确定性潜在地影响网格应用任务的正常执行,这样使得设计既能减小应用任务执行时间又能减小欺骗可能性的调度算法十分困难．参考社会学的人际关系信任模型,建立网格节点信任推荐机制,并利用D-S理论对推荐证据进行综合分析,从而定义出基于不确定性推理理论的信任度计算函数．将该函数并入DLS算法得到“可信”动态级调度算法(TDLS),从而在计算调度级别时考虑网格节点的可信程度．仿真结果证实,提出的TDLS算法以小的时间花费为代价,能有效提高任务在信任方面的服务质量需求．     

时间约束下可靠性增强的网格工作流调度算法

如何在动态性极强的网格环境中有效调度工作流应用并满足用户的QoS需求是一个难题.传统的基于资源静态特征的启发式调度算法或预留策略缺乏对资源动态服务能力的有效评估而无法保证工作流应用的截止时间约束.本文采用随机服务模型建模网格资源的动态性能并考虑资源内处理单元失效的情况.利用生灭过程描述资源节点中处理单元数目的变化情况并给出了资源节点在任务截止时间内的可靠性评估方法.在此基础上,提出一种可靠性增强的网格工作流调度算法RSA_TC.实验结果表明RSA_TC算法相对于DSESAW和PFAS算法,能有效保证用户截止时间的要求,对动态网格环境有较好的自适应性.     

适用于应用模式的网格结点选择方法研究

网格环境中的任务调度面临着海量的计算和通信资源环境,所以调度者需要考虑资源的选择问题.传统的资源选择方法一般只考虑计算能力或通信能力的最大化,没有考虑资源的通信模式与应用的匹配问题.本文在Remos研究的基础上,提出了一个完整的基于应用通信模式的网格结点选择算法.算法使用子图同构的辨识方法来判断网格结点的连通关系是否与应用模式相匹配,在满足通信模式约束的前提下,再用贪婪算法来选择计算和通信均较优化的结点.在通用算法的基础上,特别考虑了基于Master-Slave和All-to-All应用模式简化结点选择算法.最后,利用仿真方法,将本文的算法和随机选择法进行了比较,结果表明本文算法选择的网格结点不但满足应用的通信约束,而且性能较优.     

采用遗传-退火算法的网格依赖任务可信调度

针对异构网格环境下的依赖任务调度问题面临的安全性挑战,综合考虑网格资源节点的固有安全性和行为安全性,构建一个网格资源节点身份可靠性度量函数和行为表现信誉度评估策略;同时为了确立任务安全需求与资源节点安全属性之间的隶属关系,定义了安全效益隶属度函数,从而建立了一个网格任务调度的安全可信模型.以此为基础,定义任务需求表示模型和网格资源拓扑模型,提出一种安全可信的网格任务调度新模型.为求解该模型,在遗传算法的基础上,设计新的进化算子即改进的交叉算子、内部交叉算子及作为变异的迁移算子,同时引入模拟退火算法增加搜索精度,从而提出了一种新的遗传-退火算法.仿真实验表明,在相同条件下,该算法比同类算法在调度长度、安全可信值及收敛性等方面具有更好的综合性能.     

基于动态关键路径的仿真网格资源调度算法

从仿真系统工作流的关键路径分析，确定关键路径上的联邦成员节点，使网格资源调度方面优先获得保证。簦于仿真网格系统运行的复杂性和不确定性，引入了随机规划理论，提出了仿真网格的动态关键路径概念以及基于动态关键路径的资源调度算法，共同解决当资源有限以及任务相关情况下仿真网格的资源调度问题。具体实现，主要使用遗传算法以及MCP算法。仿真实验结果表明，基于动态关键路径的资源调度算法能够优化仿真网格资源的调度。     

Wingrid-面向参数扫描应用的网格计算系统

参数扫描应用在计算网格环境下扮演十分重要的角色。在Wingrid项目中,我们提出并实现了一种面向参数扫描的自适应调度机制。客户端,主节点和从节点的调度基础设施,以及基于领导节点的通信系统能够改善调度的效率。同时,我们比较了自适应workqueue算法和标准启发式调度算法。实验结果显示大网络延迟下,启发式调度算法效率高于workqueue算法,在各种启发式算法中,min-min启发式算法的任务完成时间最小。     

基于网格资源超图模型的可信任务调度

网格任务调度是当前重要的研究领域。网格环境具有动态性、异构性等特点,网格资源的处理性能和稳定性都是影响到任务调度顺利完成的重要因素。为了获得更小的任务完成时间,该文根据网格环境的特点,建立了网格资源超图模型,在该模型基础上对资源按性能进行聚类,并提出一种可信任务调度算法GRHTS。模拟实验结果表明,该基于网格资源超图模型的可信任务调度算法优于同类算法,是一种有效的网格任务调度算法。     

网格环境下安全约束的资源调度研究

提出了一个网格信任模型,用主观逻辑理论进行信任值的推导、综合。针对现有网格任务调度算法存在的问题,设计了一种任务和资源安全等级匹配的调度算法。通过安全需求对资源进行筛选,并使它满足最早完成时间。仿真实验表明,与传统经典网格任务调度算法比较,该算法提高了任务成功率,减少了任务完成时间,是网格环境下一种有效的资源调度模型。     

基于网格计算池模型的作业调度策略研究

在现阶段,网格的计算池模型是一种较实用的网格实现方式,其资源的查找和分配机制也相对简单。文章根据计算池模型的特点,参照织女星网格的体系结构,将基于最短路由转发的资源发现机制与任务调度算法相结合,提出了一种新的网格任务调度策略,并给出了简化模型清晰地描述了任务在此策略下全部的执行过程。     

面向可靠性一费用优化的网格任务调度模型及算法研究

网格资源的异构性、动态性等特征使得网格任务调度仍面临着诸多问题。针对传统可靠性评佑模型仅考虑 资源失效的问题,在考虑本地任务会抢占网格任务执行资源的情况下,引入任务执行延期失效,从而建立了一种新的 网格资源可靠性评估模型。该模型使用随机服务系统理论建模网格资源的动态负载压力,给出了任务在资源上的执 行可靠性的计算方法及证明。基于建立的网格资源可靠性模型,建立了面向可靠性和费用的多目标任务优化调度模 型,以获得最大化任务执行可靠性、最小化任务执行费用的任务调度策略。针对该NP问题,采用化学反应优化算法 对该优化问题进行求解,并给出了算法4种操作的具体实施方法。仿真实验表明,所提出的可靠性评估模型更符合真 实的网格系统,与遗传算法、粒子群算法相比,化学反应优化算法能更好地解决可靠性一费用双目标优化的网格任务调 度问题。     

基于QoS参数综合模型的网格资源选择优化

QoS是网格任务执行的基本保证,针对网格资源选择中复杂的QoS参数处理过程,将QoS参数按照用户的关心程度进行分类,提出了一种简化的参数处理模型,设计了支撑该模型的QoS体系结构,给出了优化资源调度过程的算法。实验表明,该模型提高了系统吞吐量和资源匹配成功率,缩短了任务的平均完成时间,最终实现了整个系统资源利用率的提高。     

计算网格中的资源选择与调度算法

针对文中描述的计算网格资源环境模型,构造了一种分布式的层次型任务调度模型,任务调度分为计算资源站点的选择以及资源站点内部的本地调度两层进行。通过研究该调度模型,提出了一种基于双目标衡量函数的资源选择算法,该算法可以通过设置相关参数动态调节响应时间和价格在总目标中所占比重。试验结果表明能够选择综合满足响应时间和价格这两个目标的计算资源,以适应用户的不同需求。     

一种应用于网格计算环境的任务调度模式*

提出了一种新的网格任务调度模式,针对网格计算资源有组织、松耦合、自治等特性,建立基于多层次虚拟组织形式的计算资源模型;根据网格环境中应用任务粗粒度、特定资源依赖等特点,建立了网格任务的描述模型;提出并实现了相应的子任务生成算法、任务初始调度算法及自动调整算法。设计实现了能够支持仿真及实际网格计算环境可扩展网格任务调度器,通过理论分析和仿真实验对算法的正确性、效果和效率进行了评价。     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

基于遗传算法的网格任务调度方法分析

网格任务调度为多项式复杂程度的非确定性问题,其中所有非确定性多项式时间可解的判定问题,共同构成了NP类问题。如何快速地找到全局最优解是网格任务调度的难点所在。而遗传算法在验证猜测的正确性方面,具有自动获取和快速搜索的特性,是解决非线性问题的最优方案。本文主要对基于遗传算法的网格任务调度方法进行分析,通过网格任务调度模型构建、资源分配等操作,来完成遗传算法的仿真实验研究。     

基于云模型的网格QoS参数归约与调度优化

针对网格资源调度中用户对QoS的定性描述,利用云模型实现资源调度中的QoS匹配。深入分析了QoS参数云的特征,提出了QoS云处理模型,通过该模型,将离散的多个QoS参数归约到一个定性的概念上;设计了实现参数归约的体系结构;给出了基于定性概念的资源调度算法。实验表明,所提出方法在资源调度率和吞吐量以及系统资源的利用效率等方面体现出良好的特性,实现了基于定性概念的调度,达到了优化调度的目的。