云计算中基于任务分层和时间约束的关联任务调度算法

针对云计算中对关联任务进行调度时出现任务执行延迟的问题,提出了一种基于任务分层和时间约束的关联任务调度(RTS-THTC)算法。该算法采用构建有向无环图(DAG)的方式表示关联任务的执行次序,通过使用对DAG进行分层的方法提高任务的并行性,计算每一层任务的完成时间约束,将每一层中的任务同时调度至具有最小完成时间的资源上。与基于异构环境的最小完成时间(HEFT)算法的对比实验〖BP(〗原文“试验”〖BP)〗结果表明,RTS-THTC算法在完成时间上比HEFT算法短,并且能够有效地减缓关联任务出现延迟的情况。     

微小卫星星务计算机任务调度算法

为了在有限的时间内尽可能多地安排具有时间约束的卫星任务,提出一种针对具有独占性、优先级相同的任务的先完成先调度算法EFFFS,对算法性能进行分析,将其与同类算法进行比较,结果表明,该算法具有较小的时间复杂度和较好的调度性能,适用于计算资源受限的环境。     

面向优先级用户的移动边缘计算任务调度策略

随着移动终端处理的数据量及计算规模不断增加,为降低任务处理时延、满足任务的优先级调度需求,结合任务优先级及时延约束,提出了基于任务优先级的改进min-min调度算法（task priority-based min-min,TPMM）。该算法根据任务的处理价值及任务的数据量计算任务的优先级,结合任务截止时间、服务器调度次数制定资源匹配方案,解决了边缘网络中服务器为不同优先级的用户进行计算资源分配的问题。仿真实验结果表明,该算法可以均衡服务器利用率,并有效降低计算处理的时延,提高服务器在任务截止处理时间内完成任务计算的成功率,相比min-min调度算法,TPMM算法最多可降低78.45%的时延,提高80%的计算成功率;相比max-min调度算法,TPMM算法最多可降低80.15%的时延并提高59.7%的计算成功率;相比高优先级（high priority first,HPF）调度算法,TPMM算法最多降低59.49%的时延,提高57.7%的计算成功率。     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

基于关联数据本地化的多密码作业流调度算法

针对云密码服务系统中服务请求多样、数据依赖性作业流与非数据依赖性作业流随机交叉并发等问题,为了避免处理节点之间关联数据的交互而带来的系统通信性能开销和数据安全性威胁,设计一种基于关联数据本地化的云密码作业流调度算法。首先通过任务请求密码功能的映射,保障多作业流请求密码功能的正确实现;然后对于具有相同请求密码功能的各任务中不同工作模式交叉问题,在提出任务优先级计算方法以促进多作业流调度公平性的基础上,采用分类调度的方法,在实现关联数据本地化的同时,保障了调度系统的整体性能。仿真结果表明,该算法不仅可以有效减少系统任务完成时间,提高资源利用率和公平性,并且具有良好的稳定性。     

基于优先级和优化完成时间的网格调度算法

网格由大量的异构资源组成,具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源,提高网格处理应用程序的能力。Min min算法是一个简单、快速、有效的调度算法,但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析,计算并优化Min min算法的任务完成时间,再根据任务需求赋予任务优先级,通过优先级安排任务调度,提高算法负载平衡能力,最后在上述分析基础上提出POTE Min min(Priority and Overlap Transmission and Execution Min min)调度算法。     

网格计算中一种改进的工作流调度算法

网格计算中如何有效地实现工作流的调度问题是目前的研究热点。文中综合考虑了资源节点的动态负载和服务能力,提出了一种改进的调度算法（AWSA）。该算法首先对任务的优先级进行降序排列,然后依次为它们选择具有最大截止时间约束的服务站点作为其候选资源,最后,依据资源站点的任务分配情况和负载变化趋势,白适应地实现从任务资源请求到站点的映射。仿真实验结果表明,文中方法是有效的,在作业拒绝率和作业调度长度方面,AWSA的性能要优于已有的方法。     

云平台下基于截止时间的自适应调度策略

针对在共享集群中进行任务调度时,无法兼顾任务的响应速度与任务完成时间的问题,提出一种基于截止时间的自适应调度算法。该算法以用户提交的截止时间为依据,根据任务的执行进度自适应地分配适当的计算资源。不同于传统调度方式里由用户提交固定资源参数,该算法在资源约束的情况下会对优先级高的任务进行抢占式调度以保证服务质量（QoS）,并在抢占过程结束后额外分配资源补偿被抢占的任务。在Spark平台进行的任务调度实验结果显示,与另一种资源协调者（YARN）框架下的调度算法相比,所提算法能严格地控制短任务的响应速度,并使长作业的任务完成时间缩短35%。     

一种用于异构环境中并行任务调度的弹性节能算法

节能调度算法设计是高性能计算领域中的一个研究热点。本文通过软件方法设计异构多核计算机的调度算法,实现系统的弹性节能,达到降低能耗并提升系统性能的目的。本文的调度策略建立在基于处理器异构的并行任务调度的环境中,构建了节能模型,提出了EAPS（Energy-aware parallel scheduling）算法模型,该算法在每一任务完成之后重新计算优先级以使优先级符合任务的实时情况,并对复制的前驱任务是否冗余任务进行判断从而避免资源的浪费,并通过调节节点电压选择能耗最少的节点进行调度,在节能与期望完成时间之间取得平衡。     

基于广义随机Petri网的网格调度模型

针对网格资源调度中负载不均衡问题,在基于QoS且具有容错性的任务调度算法基础上提出一种基于任务优先级的QoS约束参数的调度策略。采用广义随机Petri网建立网格调度模型,增加Petri网的抑制弧功能,实现优先调度策略。结果证明了该策略优先运行紧迫任务,并且其运行任务时间和费用的综合代价较小。     

基于聚类和改进共生演算法的云任务调度策略

针对云计算环境中一些基于服务质量（QoS）调度算法存在寻优速度慢、调度成本与用户满意度不均衡的问题,提出了一种基于聚类和改进共生演算法的云任务调度策略。首先将任务和资源进行模糊聚类并对资源进行重排序放置,依据属性相似度对任务进行指导分配,减小对资源的选择范围;然后依据交叉和旋转学习机制改进共生演算法,提升算法的搜索能力;最后通过加权求和方式构造驱动模型,均衡调度代价与系统性能间关系。通过不同任务量的云任务调度仿真实验,表明该算法相比改进遗传算法、混合粒子群遗传算法和离散共生演算法,有效减少了进化代数,降低了调度成本并提升了用户满意度,是一种可行有效的任务调度算法。     

异构云环境下基于分簇的云资源感知任务调度方案

针对提高异构云平台中资源调度的效率,提出了一种基于任务和资源分簇的异构云计算平台任务调度方案。利用K-means算法,根据任务的CPU和I/O处理时间对任务分簇,根据资源的计算能力对资源分簇;然后,将任务簇对应到合适的资源簇,并利用最早截止时间优先（EDF）算法对任务簇中的独立任务进行调度,利用提出的改进型最小关键路径（MCP）算法对依赖性任务进行调度。实验结果表明,在资源异构的云计算环境中,该方案执行任务时间短、能耗低。     

面向建材装备集团制造的分布式多项目资源调度

针对建材装备集团项目执行过程中存在的项目内和项目间多类别资源协同共用现象,提出并行调度机制下考虑多类别资源转移时间和转移成本的分布式多项目资源调度问题,以最小化资源转移成本和项目执行工期为目标建立问题的数学模型.为改善进化算法在局部搜索能力方面的不足,提出将禁忌搜索与进化算法相结合,构造一种内嵌禁忌搜索寻优搜索的多目标混合进化算法,在保证算法全局搜索能力的前提下提升局部精确搜索能力.同时,考虑资源转移成本和时间对任务选取的影响,改进任务选择的优先权值,提出并行调度机制下资源转移冲突消解策略.数据实验表明,所提算法能够有效避免不合理的资源转移,在求解质量方面具有良好的性能.     

分布式计算中基于资源分级的自适应Min-Min算法*

Min-Min任务调度算法的思路总是优先调度执行时间较短的小任务,无法得到理想的最优跨度及资源负载平衡．针对该问题,提出基于资源分级的自适应Min-Min算法．分配任务前,先参考现有资源的属性进行分级处理,再与任务在资源中的最小完成时间作乘积得到的最小任务资源组合进行调度;在任务调度过程中,引入自适应阈值,调节长任务的调度等级,从而达到优化效果．通过模拟仿真实验,表明该算法在时间跨度和负载平衡上均有较好性能．     

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

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

基于代价优化的云工作流调度改进PSO算法

云计算可以通过即付即用的方式向用户工作流提供资源。为了解决资源服务代价异构环境下的云工作流任务调度代价问题,提出一种基于改进粒子群算法的云工作流任务调度算法WSA-IPSO。通过综合考虑任务的执行代价和依赖任务间发生数据传输时的通信代价,算法将总代价优化问题形式化为有向无环图DAG中的任务调度模型,并提出基于改进粒子群算法的优化模型对其进行求解。通过改进传统粒子群算法的粒子速度更新策略和惯性权重更新策略,算法可以以更快的收敛速度得到代价最小化的调度方案。通过仿真实验,与MCT算法及标准粒子群算法进行性能比较。实验结果表明,WSA-IPSO算法在降低总代价、任务分布的负载均衡以及算法收敛性方面比较同类算法均表现出更好的性能。     

数据密集作业在GPU集群上的调度算法研究

数据密集型作业包含大量的任务,使用GPU设备来提高任务的性能是目前的主要手段.但是,在解决数据密集型作业之间的GPU资源公平共享以及降低任务所需数据在网络间的传输代价方面,现有的研究方法没有综合考虑资源公平与数据传输代价的矛盾.分析了GPU集群资源调度的特点,提出了一种基于最小代价最大任务数的GPU集群资源调度算法,解决了GPU资源的公平分配与数据传输代价较高的矛盾.将调度过程分为两个阶段：第1阶段为各个作业按照数据传输代价给出自己的最优方案;第2阶段为资源分配器合并各个作业的方案,按照公平性给出全局的最优方案.首先,给出了GPU集群资源调度框架的总体结构,各个作业给出自己的最优方案,资源分配进行全局优化;第二,给出了网络带宽估计策略以及计算任务的数据传输代价的方法;第三,给出了基于GPU数量的资源公平分配的基本算法;第四,提出了最小代价最大任务数的资源调度算法,描述了资源非抢夺、抢夺以及不考虑资源公平策略的实现策略;最后,设计了6种数据密集型计算作业,对所提出的算法进行了实验.通过实验验证,最小代价最大任务数的资源调度算法对于资源公平性能够达到90%左右,同时亦能保证作业并行运行时间最小.     

不规则任务在图形处理器集群上的调度策略

针对大量的资源需求少且并行度高的不规则任务集合,利用图形处理器（GPU）来加速处理是目前的主流。然而现有的不规则任务调度策略要么采用独占GPU的方式,要么使用传统的优化方法将任务映射到GPU设备上。前者导致GPU资源的闲置,后者不能最大限度利用GPU计算资源。在分析了现存问题的基础上,采用多背包优化思想,使更多的不规则任务以最佳的方式共享GPU设备。首先,针对GPU集群的特点,给出了由调度器、执行器组成的分布式GPU作业调度框架;然后,以GPU显存为代价,设计了一种基于GPU计算资源的扩展贪心调度（EGS）算法,该算法将尽可能多的不规则任务调度到多个可用的GPU上,以最大限度地利用GPU计算资源,并解决了GPU资源的闲置问题;最后,使用实际基准程序随机生成目标任务集来验证所提调度策略的有效性。实验结果表明,与传统的贪心算法、最早完成时间（MCT）算法和Min-min算法相比,当任务数量等于1 000时,EGS算法的执行时长分别平均降低至原来的58%、64%和80%,并且能有效提升GPU资源利用率。