基于多约束图分割机制的科学工作流调度

为了解决数据密集型环境下的科学工作流应用调度问题,提出一种基于多约束图分割的工作流调度算法。解决标准图分割方法中顶点维度单一而无法反映任务并行性的问题;设计多维度的顶点权重矢量机制,通过有向边的修剪,在所有维度上实现权重和的均衡;得到最小化的任务间数据传输量,降低通信代价。以Montage工作流结构为例进行仿真实验,结果表明,该算法仅以较小的图分割时间代价使得工作流调度过程中的访问量降低了14%,调度时间降低了31%。     

基于自适应惩罚函数的云工作流调度协同进化遗传算法

云计算为大规模科学工作流应用的执行提供了更高效的运行环境。为了解决云环境中科学工作流调度的代价优化问题,提出了一种基于协同进化的工作流调度遗传算法CGAA。该算法将自适应惩罚函数引入严格约束的遗传算法中,通过协同进化的方法,自适应地调整种群个体的交叉与变异概率,以加速算法收敛并防止种群早熟。通过4种科学工作流的仿真实验结果表明,CGAA算法得到的调度方案在满足工作流调度截止时间约束与降低任务执行代价的综合性能方面优于同类型算法。     

云环境中面向可靠性约束的工作流调度策略研究

随着越来越多的计算密集型依赖应用被卸载到云环境中执行，工作流调度问题受到了广泛的关注。针对云环境多目标优化的工作流调度问题，考虑到任务执行过程中服务器可能会发生性能波动和宕机等问题，基于模糊理论，使用三角模糊数表示任务执行时间和数据传输时间，提出了一种基于遗传算法的自适应粒子群优化算法(Adaptive Particle Swarm Optimization based GA,APSOGA),目的是在工作流的可靠性约束下，综合优化工作流的完成时间和执行代价。该算法为了避免传统粒子群优化算法存在的过早收敛问题，引入了遗传算法的随机两点交叉操作和单点变异操作，有效地提升了算法的搜索性能。实验结果表明，与其他策略相比，基于APSOGA的调度策略能够有效地降低云环境中面向可靠性约束的科学工作流的模糊总代价。     

基于局部关键路径与截止期限分配的云工作流调度算法

为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。     

基于服务质量的网格工作流算法优化

本文介绍了网格的基本概念,结合工作流任务的服务质量(QoS)需求,提出了基于服务质量的网格工作流调度算法,对GGWF算法中的LGSS算法做了改进,提出了ILGSS算法,对该算法的算法复杂度进行了分析,并在局域网环境下做了仿真实验,并给出了实验结果和分析,提出了在网格环境下探索自适应的工作流事务机制这一十分重要的研究方向,为网格环境下工作流的调度提供了一种新的解决方案.     

事务工作流模型中恢复策略的研究

阐述工作流中事务的起源和发展,针对目前工作流模型对事务处理方面的不足,提出一种具有事务支持的工作流过程元模型.该模型不仅支持过程的层次结构,并且引入隔离域及错误恢复属性概念,从语义的角度进行了扩展.同时,分析了事务工作流中并发控制机制和各种调度算法,重点研究并提出了事务工作流的错误恢复策略和错误恢复算法.最后,对算法进行了实例分析,验证了该算法是可行和实用的.     

多目标最优化云工作流调度进化遗传算法

为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。     

云科学工作流截止期限约束代价优化调度算法*

针对异构云环境下科学工作流调度的代价优化问题,提出一种基于约束关键路径的代价优化调度算法(CSACCP)。算法以满足截止期限约束同时最小化执行代价为目标,充分考虑云环境和科学工作流的独有特性,设定任务的向上权值,将工作流分解成约束关键路径(CCP)集合。结合首次适应插入算法以减少空闲时隙,改善费用优化效果,采用及时完成和最小费用增长代价的虚拟机选择策略形成备选资源集合。整体分配CCP到最便宜的虚拟机实例,压缩数据通信开销减少工作流的执行代价。通过四种著名的科学工作流仿真测试,结果表明与现有启发式算法相比,CSACCP不仅可以在满足截止期限的约束下得到更小的执行代价,还拥有更高的任务调度成功率。     

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。     

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

基于WDAG的工作流模型优化分析

为优化过程执行,降低实际运行成本,采用加权有向无环图(WDAG)的形式对工作流进行优化分析。将WDAG中的节点、弧和权重映射为工作流模型中的事件、运行过程和付出代价,建立基于WDAG的工作流模型,针对工作流中出现频率最高的顺序运行方式,提出一种包含合并优化和并行优化2种优化策略的优化算法。模拟实验结果验证了该算法的有效性。     

A security and cost aware scheduling algorithm for heterogeneous tasks of scientific workflow in clouds

Security is increasingly critical for various scientific workflows that are big data applications and typically take quite amount of time being executed on large-scale distributed infrastructures. Cloud computing platform is such an infrastructure that can enable dynamic resource scaling on demand. Nevertheless, based on pay-per-use and hourly-based pricing model, users should pay attention to the cost incurred by renting virtual machines (VMs) from cloud data centers. Meanwhile, workflow tasks are generally heterogeneous and require different instance series (i.e., computing optimized, memory optimized, storage optimized, etc.). In this paper, we propose a security and cost aware scheduling (SCAS) algorithm for heterogeneous tasks of scientific workflow in clouds. Our proposed algorithm is based on the meta-heuristic optimization technique, particle swarm optimization (PSO), the coding strategy of which is devised to minimize the total workflow execution cost while meeting the deadline and risk rate constraints. Extensive experiments using three real-world scientific workflow applications, as well as CloudSim simulation framework, demonstrate the effectiveness and practicality of our algorithm.     

基于路径平衡的工作流费用优化方法

针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称 PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法。 PBCO 基于 PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间。同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果。实验结果表明,PBCO比另外几种著名算法(如DET,DBL等)改进了约35%。     

一种满足可靠性和能效的云工作流调度方法

为了同步解决云工作流调度时的失效和高能耗问题,提出一种基于可靠性和能效的工作流调度算法.算法为了在截止时间的QoS约束下最大化系统可靠性并最小化调度能耗,将工作流调度过程划分为四个阶段:计算任务优先级、工作流任务聚簇、截止时间子分配和任务调度.算法在满足执行次序的情况下对任务进行拓扑排序,并以通信代价最小为目标对任务进...     

Scheduling large-scale scientific workflow on virtual machines with different numbers of vCPUs

With the wide deployment of cloud computing in scientific computing, cost minimization is increasingly critical for large-scale scientific workflow. Unfortunately, due to the highly intricate directed acyclic graph (DAG)-based workflow and the flexible usage of virtual machines (VMs) in cloud platform, the existing workflow scheduling approaches are inefficient to strike a balance between the parallelism and the topology of the DAG-based workflow while using the VMs, which causes a low utilization of VMs and consumes more cost. To address these issues, this paper presents a novel task scheduling framework named cost minimization approach with the DAG splitting method (COMSE) for minimizing the cost of running a deadline-constrained large-scale scientific workflow. First, we provide comprehensive theoretical analyses on how to improve the utilization of a resource-balanced multi-vCPU VM for running multiple tasks simultaneously. Second, considering the balance between the parallelism and the topology of a workflow, we simplify the DAG-based workflow, and based on the simplified DAG, a DAG splitting method is devised to preprocess the workflow. Third, since the cloud is charged by hours, we also design an exact algorithm to find the optimal operation pattern for a given schedule to make the consumed instance hours minimum, and this algorithm is named as instance hours minimization by Dijkstra (TOID). Finally, by employing the DAG splitting method and the TOID, the COMSE schedules a deadline-constrained large-scale scientific workflow on the multi-vCPU VMs and incorporates two important objects: minimizing the computation cost and the communication cost. Our solution approach is evaluated through rigorous performance evaluation study using real-word workflows, and the results show that the proposed COMSE approach outperforms existing algorithms in terms of computation cost and communication cost.

     

一种多重约束下确保成功率的云工作流调度方法

为提高多重约束下的调度成功率,提出一种满足期限和预算双重约束的云工作流调度算法。将可行工作流调度方案求解分解为工作流结构分层、预算分配、期限分配、任务选择和实例选择。工作流结构分层将所有工作流任务划分层次形成包任务,以提高并行执行程度;预算分配对整体预算在层次间进行分割;期限分配将全局期限在不同层次间分割;任务选择基于任务最早开始时间确定优先级,得到任务调度次序;实例选择根据时间和代价均衡因子,获取任务执行最佳实例。仿真结果证明,该算法在调度成功率、同步优化工作流执行时间与执行代价上相较对比算法更好。