基于动态资源选择策略的微服务工作流调度算法

为解决现有云中工作流调度算法在面对大量微服务任务组成的工作流时出现整体调度成本偏高的问题,提出一种基于动态资源选择策略(dynamic resource selection strategy, DRSS)的微服务工作流调度算法——DRSS调度算法。利用任务在工作流中的位置确定任务的子截止期以及调度优先级,采用动态资源选择策略对任务进行调度,获得任务执行的最优资源,在此基础上更新任务状态以及虚拟机实例的资源向量。实验结果表明,该算法在调度成功率与成本方面上较同类算法更优。     

满足实时云任务需求的主动响应式工作流调度模型

为了改善云平台中多工作流调度时的执行代价和资源利用率,提出一种满足实时云任务需求的主动响应式工作流调度算法.该算法可以分别针对新工作流的到达、任务完成后的虚拟机资源提供、紧迫任务到达等做出主动的实时响应调度策略,从而充分利用虚拟机资源的空闲时槽和更大化的任务并行程度,以混合形式调度来自不同工作流的任务.在确保截止期限约束的同时,有效满足实时云任务的调度需求.大量实时工作流的仿真测试表明,与另外几种同类型算法相比,该算法不仅可以降低任务执行代价,而且可以得到更高的资源利用率,实现算法预期效果.     

云工作流中基于分时虚拟机的任务层调度算法

云计算是新的一种面向市场的商业计算模式,向用户按需提供服务,云计算的商业特性使其关注向用户提供服务的服务质量。任务调度和资源分配是云计算中两个关键的技术,所使用的虚拟化技术使得其资源分配和任务调度有别于以往的并行分布式计算。目前主要的调度算法是借鉴网格环境下的调度策略,研究基于QoS的调度算法,存在执行效率较低的问题。我们对云工作流任务层调度进行深入研究,分析由底层资源虚拟化形成的虚拟机的特性,结合工作流任务的各类QoS约束,提出了基于虚拟机分时特性的任务层ACS调度算法。经过试验,我们提出的算法相比于文献[1]中的算法在对于较多并行任务的执行上存在较大的优势,能够很好的利用虚拟的分时特性,优化任务到虚拟机的调度。     

云工作流中基于分时虚拟机的任务层调度算法

云计算是新的一种面向市场的商业计算模式,向用户按需提供服务,云计算的商业特性使其关注向用户提供服务的服务质量。任务调度和资源分配是云计算中两个关键的技术,所使用的虚拟化技术使得其资源分配和任务调度有别于以往的并行分布式计算。目前主要的调度算法是借鉴网格环境下的调度策略,研究基于QoS的调度算法,存在执行效率较低的问题。我们对云工作流任务层调度进行深入研究,分析由底层资源虚拟化形成的虚拟机的特性,结合工作流任务的各类QoS约束,提出了基于虚拟机分时特性的任务层ACS调度算法。经过试验,我们提出的算法相比于文献[1]中的算法在对于较多并行任务的执行上存在较大的优势,能够很好的利用虚拟的分时特性,优化任务到虚拟机的调度。     

虚拟云下满足多重约束的时限敏感任务调度算法

目前以虚拟云服务平台作为强大计算平台的虚拟云环境下,许多现存调度方法致力于合并虚拟机以减少物理机数目,从而达到减少能源消耗的目的,但会引入高额虚拟机迁移成本;此外,现存方法也没有考虑导致用户高额支付成本的成本因子影响。以减少云服务提供者能源消耗和云服务终端用户支付成本为目标,同时保障用户任务的时限要求,提出一种能源与时限可感知的非迁移调度（EDA-NMS）算法。EDA-NMS利用任务时限的松弛度,延迟宽松时限任务的执行从而无需唤醒新的物理机,更无需引入虚拟机动态迁移成本,以达到减少能源消耗的目的。多重扩展实验结果表明,EDA-NMS采用成本和能耗有效的虚拟机实例类型组合方案,与主动及响应式调度（PRS）算法相比,在减少静态能耗的同时,能更有效地满足用户关键任务的敏感时限并确保用户支付成本最低。     

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

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

不确定性云环境工作流调度多目标优化

云计算弹性的资源提供和虚拟机性能的不稳定性使得工作流的执行面临诸多不确定性.针对此问题,考虑执行时间具有不确定性,基于执行时间和代价的同步优化,提出同步满足健壮性的三目标优化工作流调度算法.以满足帕累托最优的均衡最优解集的形式进行建模,以启发式方式对模型求解.为衡量均衡解的质量,设计基于超体积的评估机制,得到冲突目标的均衡调度解,比原始双目标优化对执行时间的波动具有更小敏感性.实验结果表明,比较未考虑不确定性的双目标优化,该算法求解质量更高,均衡度更好,更符合不确定性实时云工作流调度.     

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

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

基于多维评价模型及改进蚁群优化算法的云计算资源调度策略

针对云计算环境下资源调度模型未充分考虑资源评价的问题,为更好适应不同节点计算性能和大规模数据环境的处理需求,提出了一种基于多维评价模型的虚拟机资源调度策略;首先,在云计算环境下建立包括网络性能在内的多维资源评价模型,在此基础上提出一种改进的蚁群优化算法实现资源调度策略;然后在云计算仿真平台CloudSim上进行实现。实验结果表明,该算法可以更好适应不同网络性能的计算环境,显著提高了资源调度的性能,同时降低了虚拟机负载均衡离差,满足了云计算环境下的虚拟机资源负载均衡需求。     

基于公共云的 HPC 集群实现及自动伸缩闲时计算研究

对于HPC用户来说,计算成本是迁云所考虑的重要因素之一,阿里云上提供的抢占式实例,是一种按需实例,旨在降低使用公共云计算资源成本,抢占式实例市场价格是波动的,通常远低于正常的按需实例,甚至达到正常按需实例的一折。抢占式实例一般会在创建时为用户保留一段最短时间,过后有可能会被释放,所以一般适用于无状态的应用场景。提出在公共云上的自动伸缩策略,其面向通用的HPC集群调度器,基于用户的应用软件类型、提交作业规律以及用户对性能和成本等多方面需求,自动在云上部署扩容计算资源,控制成本。对用户来说,可以做到"only pay for what you want and what you use"。基于公共云上丰富的资源规格类型和售卖方式,利用自动伸缩服务,抢占式实例,断点续算等技术可以配置低成本的公共云上HPC自动伸缩方案:用户提交作业的同时可以指定成本上限,自动伸缩服务自动在低于此成本的前提下寻找和扩容抢占式计算资源,同时利用断点续算功能保证作业在计算资源切换的时候可以继续运算。最后,通过LAMMPS和GROMACS两个高性能应用实例验证了该策略的可行性和有效性。     

An intelligent water drops-based workflow scheduling for IaaS cloud

Cloud computing is an emerging technology in a distributed environment with a collection of large-scale heterogeneous systems. One of the challenging issues in the cloud data center is to select the minimum number of virtual machine (VM) instances to execute the tasks of a workflow within a time limit. The objectives of such a strategy are to minimize the total execution time of a workflow and improve resource utilization. However, the existing algorithms do not guarantee to achieve high resource utilization although they have abilities to achieve high execution efficiency. The higher resource utilization depends on the reusability of VM instances. In this work, we propose a new intelligent water drops based workflow scheduling algorithm for Infrastructure-as-a-Service (IaaS) cloud. The objectives of the proposed algorithm are to achieve higher resource utilization and minimize the makespan within the given deadline and budget constraints. The first contribution of the algorithm is to find multiple partial critical paths (PCPs) of a workflow which helps in finding suitable VM instances. The second contribution is a scheduling strategy for PCP-VM assignment for assigning the VM instances. The proposed algorithm is evaluated through various simulation runs using synthetic datasets and various performance metrics. Through comparison, we show the superior performance of the proposed algorithm over the existing ones.     

An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.     

移动云计算中基于延时传输的多目标工作流调度

云计算和移动互联网的不断融合,促进了移动云计算的产生与发展.在移动云计算环境下,用户可将工作流的任务迁移到云端执行,这样不但能够提升移动设备的计算能力,而且可以减少电池能源消耗.但是不合理的任务迁移会引起大量的数据传输,这不仅损害工作流的服务质量,而且会增加移动设备的能耗.基于此,本文提出了基于延时传输机制的多目标工作流调度算法MOWS-DTM.该算法基于遗传算法,结合工作流的调度过程,在编码策略中考虑了工作流任务的调度位置和执行排序.由于用户在不断移动的过程中,移动设备的无线网络信号也在不断变化.当传输一定大小的数据时,网络信号越强则需要的时间越少,从而移动设备的能耗也越少.而且工作流结构中存在许多非关键任务,延长非关键任务的执行时间并不会对工作流的完工时间造成影响.因此,本文在工作流调度过程中融入了延时传输机制DTM,该机制能够同时有效地优化移动设备的能耗和工作流的完工时间.仿真结果表明,相比MOHEFT算法和RANDOM算法,MOWS-DTM算法在多目标性能上更优.     

混合云环境中数据敏感工作流调度

混合云环境下调度包含敏感数据的工作流主要考虑在满足数据安全性以及工作流截止时间的前提下,对工作流任务在混合云上进行分配,实现计算资源与任务的映射,并优化调度费用。采用了整数规划来建模求解包含数据敏感性、截止时间和调度费用3种约束条件的混合云工作流调度问题,同时为优化模型求解速度,基于“帕雷托最优”原理对工作流任务在混合云上的分配方案进行筛选以减小模型求解规模。实验表明,优先排除不合理的任务分配方案可有效减小整数规划模型的求解规模,缩短模型计算时间,在产生较小误差的情况下获得较优的调度结果。     

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

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

A hybrid instance-intensive workflow scheduling method in private cloud environment

Aiming to solve the problem of instance-intensive workflow scheduling in private cloud environment, this paper first formulates a scheduling optimization model considering the communication time between tasks. The objective of this model is to minimize the execution time of all workflow instances. Then, a hybrid scheduling method based on the batch strategy and an improved genetic algorithm termed fragmentation based genetic algorithm is proposed according to the characters of instance-intensive cloud workflow, where task priority dispatching rules are also taken into account. Simulations are conducted to compare the proposed method with the canonical genetic algorithm and two heuristic algorithms. Our simulation results demonstrate that the proposed method can considerably enhance the search efficiency of the genetic algorithm and is able to considerably outperform the compared algorithms, in particular when the number of workflow instances is high and the computational resource available for optimization is limited.

     

A delay-based dynamic scheduling algorithm for bag-of-task workflows with stochastic task execution times in clouds

Bag-of-Tasks (BoT) workflows are widespread in many big data analysis fields. However, there are very few cloud resource provisioning and scheduling algorithms tailored for BoT workflows. Furthermore, existing algorithms fail to consider the stochastic task execution times of BoT workflows which leads to deadline violations and increased resource renting costs. In this paper, we propose a dynamic cloud resource provisioning and scheduling algorithm which aims to fulfill the workflow deadline by using the sum of task execution time expectation and standard deviation to estimate real task execution times. A bag-based delay scheduling strategy and a single-type based virtual machine interval renting method are presented to decrease the resource renting cost. The proposed algorithm is evaluated using a cloud simulator ElasticSim which is extended from CloudSim. The results show that the dynamic algorithm decreases the resource renting cost while guaranteeing the workflow deadline compared to the existing algorithms.     

Cost optimal scheduling in IaaS for dependent workload with particle swarm optimization

Optimizing cloud provisioning for scientific workflow applications is a challenging problem, since the workflows generally contain dependency between tasks and require specific deadlines. Usually, cloud providers offer many options to the consumers. These options include the number of virtual machines, the type of each virtual machine and the purchasing method for each machine. Currently, cloud provisioning cost optimization is an active research topic. Most of this literature is concerned with task scheduling, cloud option selection, and cloud option selection for scientific workflow applications. However, research that attempts to find solutions which cover both cloud option selection and workflow task scheduling is very limited. In this paper, we focus on optimizing the cost of purchasing infrastructure-as-a-service cloud capabilities to achieve scientific work flow execution within the specific deadlines. The proposed system considers the number of purchased instances, instance types, purchasing options, and task scheduling as constraints in an optimization process. Particle swarm optimization augmented with a variable neighborhood search technique is used to find the optimal solution. Our approach finds the configurations of purchasing options with the optimum budget for a specified workflow application based on the required performance. The solutions from the proposed system show promising performance from the perspectives of the total cost and fitness convergence when compared with other state-of-the-art algorithms.