云计算环境下多DAG调度的资源分配进化算法

现有多DAG调度研究主要在多个DAG共享资源调度的时间最小化、公平性最大化、吞吐量最大化等问题方面提出了相关的解决方案,然而,现有的方法还不能很好地解决云计算环境下多DAG共享资源调度的资源分配优化问题。为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享资源调度的资源分配优化问题,既保证了多DAG的调度执行时间最小化,也避免了资源的浪费。实验表明,EFRD算法能够有效地收敛到最优解。

一种求解异构DAG调度问题的置换蚁群

减少分布式程序的执行时间,是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。提出的置换调度蚁群PSACS(Permutation Scheduling Ant Colony System)将DAG调度方案表示为任务置换列表,使用标准蚁群搜索技术探索解空间。实验表明,该算法明显优于遗传算法和粒子群算法,能够一次求出大部分(65%)同构DAG调度问题的最优解并获得非常好的异构DAG调度方案。

基于最小化传输和完成时间的多DAG调度

针对云计算环境下多个有向无环图(DAG)工作流的调度问题,提出一种基于最小化数据传输时间和任务完成时间(LTCT)的算法,用于处理具有相同优先级的多个DAG工作流之间的调度问题。在多个DAG优先级各不相同时的情况下,给出多优先级多DAG的混合调度算法。实验结果表明,LTCT算法较E-Fairness算法在保证多DAG调度公平性的基础上,能避免额外的数据传输开销,有利于缩短整个工作流的执行Makespan,提高资源的利用率。

一种自适应资源精细匹配的DAG调度方法

针对目前计算密集或数据密集特征的任务依赖和并行处理的耦合度过高,采用将关联任务的执行顺序控制与并行算法的处理逻辑相分离。该方法通过任务分解的方式和自适应的多资源精细匹配,利用DEM数据建立起十万量级栅格的大流域生态水文过程DAG任务调度模拟。在实验部分,用多重对比的方法评估在分辨率、数据规模、进程数量以及本地资源管理器(LRM)不同条件情况下该方法的性能。实验结果表明,任务分解的自适应多资源精细匹配DAG调度方法大幅度提高了并行性能和效率,具有较好的鲁棒性和扩展性。

GridSim4Dag：基于GridSim的Dag调度仿真器

网格仿真器GridSim以其灵活的使用方式和广阔的应用前号，自2002年公布之后一直备受人们关注。但是，由于其采用面向任务池（taskp001）的任务建模方式，使其并不适合于仿真Dag图的调度。为了支持Dag图调度算法的研究，进一步丰富GridSim的功能，此文提出了一种改进GridSim的方法，即P2P的中间数据传输方式，并将改进后的GridSim仿真工具包叫作GridSim4Dag。当前驱子任务执行完毕之后直接将中间结果发送给后继子任务所在的资源以启动后继子任务的执行，从而减少传输时间．降低通许开销、降低通讯出错率。这同时也是一种对网格框架的调整，使得网格直接可以支持Dag任务的调度。

在边缘计算中有向无环图任务高效调度方法

随着用户对延迟敏感的应用程序的需求不断增长,边缘计算环境中的高效任务调度对于及时满足用户需求变得至关重要。边缘计算环境下有向无环图(directed acyclic graph,DAG)调度的静态任务调度方法,旨在研究最小化任务完成时间并及时响应用户需求。为了模拟边缘计算场景,本文采用Kubernetes(K8s)集群,通过构造基于深度优先搜索的异构最早完成时间(heterogeneous earliest finish time based on depth-first search,D-HEFT)调度算法优化了高效率任务调度。该算法使用深度优先搜索算法来优化异构最早完成时间(heterogeneous earliest finish time,HEFT)算法。实验结果表明,D-HEFT算法在任务调度效率和任务完成时间方面优于HEFT、具有复制的异构最早完成时间(heterogeneous earliest finish time with duplication,HEFT_D)、HEFT_U和处理器上的关键路径(critical path on the processor,CPOP)四种任务调度方法。

分布式系统下的DAG任务调度研究综述

近年来随着网格、云计算工作流等分布式计算技术的发展,关于DAG(有向无环图)模型任务在分布式系统环境下的调度问题逐渐成为备受关注的研究热点。根据最新研究进展,对分布式系统下的DAG任务调度问题和有关技术进行了研究与讨论,主要包括四个方面:系统地描述了分布式系统和异构分布式系统的有关概念,异构分布式系统下的DAG任务调度问题、调度模型及其典型应用;对现有分布式系统下DAG任务调度的研究按照不同的方式进行了分类;探讨了多DAG共享异构分布式资源调度的研究现状;讨论了目前多DAG共享异构分布式资源调度研究存在的问题和未来可能的研究方向。

异构分布式环境下多DAG工作流的混合调度策略

关于多个DAG工作流在异构分布式环境下调度的研究近来有了新的进展,也解决了一些问题,但现阶段还没有考虑和解决根据不同类型DAG的需求按优先级进行分类,以及对不同时间到达的多个不同优先级DAG进行调度的问题.为解决这些问题,针对各用户对DAG工作流的QoS需求的不同,在对不同用户的DAG工作流进行优先级划分的基础上,首先提出了一种新的调度模型,并改进了已有的公平调度算法,解决在不同时间上被提交的具有相同优先级的多个DAG工作流之间调度的公平性问题.为了提高资源利用率和高优先级DAG尽可能小地受低优先级DAG的影响,又提出了一种适用于多个不同优先级DAG之间调度的Backfill算法.在新的系统模型和这两种算法的基础上,提出了一种混合调度策略.实验结果表明,这种混合调策略能够兼顾不同时间到达的多个不同类型DAG调度需求和资源利用率的改善.另外,通过实验发现了关于两个DAG调度所特有的'拖尾'规律,具有进一步研究和应用的价值.

有期限约束的多DAG共享资源的调度及公平费用优化方法

随着网格和云计算工作流技术的发展,近来关于多DAG(Directed Acyclic Graph)共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的"相对严格程度"的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS(Scheduling for Multi-DAGs with Deadline based on Relative Stritness).该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的"过饱和"情况进行探测和处理.一旦遇到"过饱和"情况,则采用"堆栈"与"调度回溯"相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS(Cost Decrease based on Variance of the Relative Strictness).实验表明:这些方法及算法能够达到较好的性能.

一种多DAG任务共享异构资源调度的费用优化方法

针对多DAG(Directed Acyclic Graph)共享一组异构资源在调度吞吐量最大化基础上的费用优化问题,本文提出了一种基于总费用变化量探测的费用优化算法PDTC(based on the Probe of the Total Cost Decrease),目的在于尽可能降低有优化条件的多个DAG的总费用.实验表明,该算法不仅能使得各DAG充分利用期限内的冗余时间,也能够在一定程度上降低多个DAG调度执行的总费用.

云计算中一种多DAG工作流可抢占式调度策略

为解决多用户工作流调度过程中的公平性问题,提高资源利用率,满足不同用户DAG工作流的不同QoS需求,提出了抢占式多DAG工作流动态调度模型。该算法将DAG工作流按照QoS需求进行优先级划分,采用高优先级作业优先占有资源的原则调度作业。相同优先级DAG工作流的任务依据带有启发性信息的slowdown进行资源抢占,进一步提高了作业调度的公平性;对于不同优先级的作业调度,提出了基于阈值的回填算法,该算法在保证作业调度公平的同时提高了资源利用率。

异构系统中DAG任务调度的双螺旋结构遗传算法

任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴于此,根据染色体双螺旋结构模型,提出了一种异构计算系统中依赖任务调度的双螺旋结构遗传算法.算法将遗传算法和启发式方法有机地结合,首先针对任务图的数据依赖关系,采用启发式方法,控制遗传算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列;然后模仿碱基互补配对方法,利用启发式异构环境下最早完成时间算法,实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机任务图和真实问题任务图的仿真实验表明,所提出的算法在调度性能上明显优于启发式算法,最大完成时间平均减少10.1%.

云环境下融合安全与可用性的DAG任务调度

在异构复杂的云环境中,任务调度时应保证资源的安全与可用性。为此,提出一种融合安全与可用性的DAG任务调度策略。改进主观逻辑信任模型,将计算出的资源信誉度作为调度的重要依据,对树云资源与DAG任务的可用性偏离度进行量化,给出调度函数并设计贪心调度算法(ISAG)。实验结果表明,在资源安全性和可用性较低的环境中,ISAG算法仍能满足用户需求,与表调度算法DLS和可用性优先调度算法Afsa相比,具有更高的任务执行成功率。

带通信开销的DAG工作流费用优化模型与算法

通信开销在云环境中无法忽略,但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销,难以在实际云环境中应用.为此,提出带通信开销的工作流费用优化模型CA-DAG(communication aware-DAG),并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent,FC)求解工作流的最小完工时间;根据逆向分层策略将任务分层,使费用优化问题从全局转化到局部;采用动态规划方法收集任务在选择服务时产生的零散"时间碎片",增加任务的费用优化空间,改善费用优化效果.仿真实验结果表明,在考虑通信开销时,CACO费用优化效果较DTL(deadline top level),DBL(deadline bottom level),TCDBL(temporal consistency deadline bottom level)都有显著提高.

一种用于网格任务调度的退火进化算法

针对网格环境下具有约束关系的任务调度问题,基于有向无环图DAG(directed acyclic graph)设计了调度模型;提出了一种改进的退火进化算法,对任务的执行次序和资源的具体分配分离编码,给出适应度函数计算方法和算法步骤。最后将算法和传统的遗传算法比较,实验结果显示该算法能获得更好的调度结果。

基于混合粒子群算法的网格任务调度

减少分布式程序的执行时间是网格调度系统需要解决的重要问题。因分布式程序常建模为DAG图,故该问题又称异构DAG调度问题。在研究网格环境下的任务调度的基础上,提出了一种用于解决DAG任务调度问题的通用混合粒子群优化算法(Common Hybrid Particle Swarm Optimization),简称为CHPSO。该算法将问题的解(粒子)表示为任务的调度优先权向量,采用混合粒子群优化算法探索解空间。实验结果表明,在求解不含孤立点的单个DAG调度问题时,该算法所得解的调度长度仅为HEFT的90%～92%,求解质量与PSGA相当;在多张DAG图(含孤立节点)并发执行的网格环境中,该算法的调度性能明显优于PSGA及文中列出的其它演化计算方法。

一种基于异构系统的实时调度算法研究

高效调度是异构系统中实现高性能计算的关键.调度问题已经被证明是NP完全问题,由于其关键性,调度问题已经被国内外研究机构广泛研究,并提出了多种算法.尽管在一些文献中提出了异构多处理器的调度算法,但是这些算法的调度成本较高,并且在较低的调度成本下无法提供高质量的调度.本文提出一种最小评分优先算法(HMSF),该算法是一种适用于异构系统的高性能、快速调度算法,通过和传统的HEFT算法和DLS算法进行试验对比发现,HMSF算法可以使调度长度更短.

负载均衡优先的改进优先级表调度算法

针对当前云计算环境下DAG任务调度时存在的负载失衡、任务调度效率不高的问题,提出了一种负载均衡优先的改进优先级表调度算法(LS-IPLB).算法将云计算集群中虚拟机的状态参数变化抽象成空间中的参数向量变化,给出实时衡量云计算集群的负载均衡性方法,并作为虚拟机选择权值的重要参数.同时以任务执行代价、任务的出度和任务间的通信代价作为参数计算任务优先级,并在任务调度时采用任务复制策略进一步优化调度过程.结果表明,LS-IPLB算法能有效缩短DAG任务图的完成时间,并实现了良好的负载均衡性.