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

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

固定优先级混合关键偶发任务能耗感知算法

混合关键系统是将不同关键层次的应用或组件集成到同一个共享平台.由于受尺寸、重量与体积的限制,能耗对于混合关键系统而言尤其重要.能耗感知调度算法是解决混合关键系统能耗问题的关键,现有的能耗感知算法主要基于动态优先级策略且空闲时间利用率低.针对固定优先级混合关键系统偶发任务能耗感知问题,提出节能效果更好的固定优先级混合关键调度(fixed priority mixed criticality schedule, FPMCS)算法.首先,提出关键层次单调速率策略(criticality rate monotonic scheme, CRMS)调度混合关键偶发任务,分析该策略的调度可行性,且计算出能耗感知速度.其次,利用高关键层次任务预留的空闲时间,通过事件触发的方法动态更新混合关键偶发任务集的利用率来回收偶发任务到达时间不确定产生的空闲时间.再次,利用混合关键偶发任务集的利用率决定任务的执行速度以达到降低能耗的目的.最后,通过理论分析和实验验证FPMCS算法是可行的;仿真实验表明：所提出的FPMCS算法比现有的方法可以节约大约33.21%的能耗.     

一种基于遗传算法的网格任务调度算法

任务调度算法是网格计算研究的一个重要方向,已被证明是一个NP完全问题.提出了一种新的网格任务调度算法.该算法基于遗传算法,为加快算法的收敛速度,在生成初始种群时优先分配关键路径上的任务;由于资源间存在着通信延迟,引入任务复制方法,并结合遗传操作控制任务复制的深度,可以减少任务之间的通信开销,缩短整个调度的完成时间;最后进行优化操作,减少冗余的任务复制.模拟实验结果表明,该算法在收敛速度和调度完成时间均优于普通遗传算法.     

一种基于能耗优化的云计算系统任务调度方法

服务器执行任务产生的能耗是云计算系统动态能耗的重要组成部分。为降低云计算系统任务执行的总能耗,提出了一种基于能耗优化的最早完成时间任务调度方法,建立了服务器动态功率计算模型,基于动态功率的服务器执行能耗模型,以及云计算系统的能耗优化模型。调度策略根据任务的截止时间要求和在不同服务器上的执行能耗,选择不同的调度算法,以获得最小任务执行总能耗。实验结果证明,提出的任务调度方法,能够较好地满足任务截止时间的要求,降低云计算系统任务执行的总能耗。     

一种基于DAG图划分的网格关联任务调度算法

网格计算中的大型应用程序往往被分解为多个关联任务.对于这类应用,任务间的依赖是一个不可忽略的因素.传统算法只能将其视为元任务来考虑,限制了对任务粒度的进一步划分,从而大大降低了任务调度的性能.本文提出一种基于DAG图划分的关联任务调度算法.它优先调度关键路径上的任务,同时利用任务复制的方法充分利用资源上的时间碎片,保证依赖关系及时得到满足.仿真结果表明,对于网格环境下的大规模关联任务,该算法有效地提高了作业执行速度和资源使用效率.     

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

基于选择性复制前驱任务的DAG调度算法

针对异构环境下相关任务的静态调度问题,以最小化调度长度为主要目标,结合表调度与基于复制的调度思想提出了选择性任务复制调度算法.在任务调度过程中,利用处理器的空闲时间,通过有选择地复制能提前当前任务开始执行时间的父任务来减少任务之间信息传递的通信延迟,有利于后续任务的及时调度,从而缩短整个任务图的并行完成时间.实验结果表明,文中算法在通信量比较大的情况下在时间上优于复杂度相同的HEFT,HNDP及DDS算法,且随着任务图中通信时间/计算时间比值的增加,其优越性也越来越明显.     

一种基于遗传算法的网格任务调度算法

任务调度算法是网格计算研究的一个重要方向,已被证明是一个NP完全问题。提出了一种新的网格任务调度算法。该算法基于遗传算法,为加快算法的收敛速度,在生成初始种群时优先分配关键路径上的任务;由于资源间存在着通信延迟,引入任务复制方法,并结合遗传操作控制任务复制的深度,可以减少任务之间的通信开销,缩短整个调度的完成时间;最后进行优化操作,减少冗余的任务复制。模拟实验结果表明,该算法在收敛速度和调度完成时间均优于普通遗传算法。     

计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.     

资源动态组织支持的网格依赖任务重调度机制

针对网格依赖任务重调度所面临的效率低与触发频繁的问题,提出资源动态组织支持的网格依赖任务调度机制.该机制以资源的动态组织为核心,基于资源动态性度量结果对资源进行性能聚类分析,并过滤性能相似资源中的强动态性资源,以在减少资源数量的同时提高重调度备选资源的稳定性.实验表明基于该机制的重调度算法保持了静态调度策略在动态网格环境下相对于动态调度策略的性能优势,从而验证了该机制解决网格依赖任务重调度所面临问题的有效性.