允许违反局部时间约束的科学工作流调度策略

提高科学工作流在云环境中的执行效率、降低执行费用受到广泛关注。用户期望的局部QoS约束与工作流的总体执行效率之间往往存在矛盾。针对该现象,在前期的研究基础上提出一种允许违反局部时间约束的科学工作流调度策略。通过对已聚簇的工作流任务集使用任务后向优先合并的方法,可实现任务间空闲时间片的合理利用,进而优化科学工作流的执行时间;另外,为充分利用任务的松弛时间,提高工作流的整体执行效率,允许部分任务的调度违反局部最晚完成时间的约束。实验结果表明,该策略能提前科学工作流的最早完成时间,提高处理机的利用率,并最终降低工作流的执行费用。     

基于任务概率聚簇的工作流云费用优化调度算法

由于云资源具有弹性伸缩、按使用量计费等优势,科研机构将工作流部署在云环境执行。工作流任务在云计算环境执行过程中会产生不可避免的系统开销。针对实际运行环境系统开销过大的问题,笔者提出基于聚簇概率的任务概率聚簇算法,平衡每层任务的资源需求,提高资源分配粒度,降低系统开销和降低公有云执行费用。实验表明,该算法能够有效降低公有云花费。     

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

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

边缘环境下基于模糊理论的科学工作流调度研究

作为一种新型计算范式,边缘计算已成为解决大规模科学应用程序的重要途径。针对边缘环境下的科学工作流调度问题,考虑到任务计算过程中的服务器执行性能波动和数据传输过程中的带宽波动造成的不确定性,文中基于模糊理论,使用三角模糊数表示任务计算时间和数据传输时间,同时提出一种基于遗传算法算子的自适应离散模糊粒子群优化算法(Adaptive Discrete Fuzzy GA-based Particle Swarm Optimization,ADFGA-PSO),目的是在满足工作流截止日期约束的前提下,降低其模糊执行代价。该方法引入遗传算法的两点交叉算子以及关于任务优先级的邻域变异算子和关于服务器编号的自适应多点变异算子,避免粒子陷入局部最优,有效提高算法的搜索性能。实验结果表明,与其他调度策略相比,基于ADFGA-PSO的调度策略能够更加有效地降低边缘环境下带截止日期约束的科学工作流的模糊执行代价。     

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

为了同步解决云工作流调度时的失效和高能耗问题,提出一种基于可靠性和能效的工作流调度算法。算法为了在截止时间的QoS约束下最大化系统可靠性并最小化调度能耗,将工作流调度过程划分为四个阶段:计算任务优先级、工作流任务聚簇、截止时间子分配和任务调度。算法在满足执行次序的情况下对任务进行拓扑排序,并以通信代价最小为目标对任务进行聚簇;将截止时间在任务间进行子分割;以合适的频率/电压等级对聚簇后的任务进行调度,在确保可靠性的前提下最小化系统能耗。通过随机任务图和高斯消除任务图进行综合仿真测试,结果表明算法在降低总体能耗和提高工作流调度可靠性方面均优于对比算法。     

基于任务分配和数据集副本的科学工作流数据布局

云环境下科学工作流的数据布局成为当前工作流研究中的一个热点问题,对科学工作流中任务和数据之间多对多关系进行分析,可以发现不同数据布局方案在数据传输上的费用各不相同,在很大程度上影响工作流的运行成本。为降低科学工作流数据集传输费用,提出一种基于任务分配和数据集副本的科学工作流数据布局方法。该方法从任务分配开始,在定量计算任务依赖度的基础上进行任务分配,根据分配结果给出一个基于数据集副本的两阶段数据布局方法,以实现科学工作流运行中传输费用的优化。实例结果表明,与工作流层方法相比,该方法可以有效降低科学工作流的运行成本。     

基于集群拓扑结构的工作流调度研究

针对MapReduce的默认调度策略先进先出(FIFO)在执行任务时考虑本地性调度带来的任务等待时间长、资源利用率不高和没有考虑任务的优先级等问题,提出一种基于集群拓扑结构的工作流实时调度算法。MapReduce在对工作流进行Map处理时,首先根据taskTracker的计算能力和数据大小对map阶段工作流的完成时间进行估计,得到一个完成时间隶属函数,然后再利用集群的拓扑结构,得到taskTracker在集群中的距离隶属函数,根据这两个隶属函数来对集群中的taskTracker在工作流处理时间和数据传输时间进行综合性能评估,这样可以有效地缩短任务的等待时间并提高资源的利用率。同时该算法采用对作业进行优先级划分的方式,满足不同类型作业的需求。大量的实验结果表明:该优化策略在平均完成时间和平均等待时间方面要优于FIFO算法,可以有效提高工作流处理的实时性。     

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

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

安全工作流用户分配策略

根据工作流执行的特点,在基于任务角色访问控制模型的基础上,提出了用户基本分配策略、用户负载均衡、用户职责分离、用户基数约束等分配方案,有效地提高了资源的利用率和工作流的执行效率.     

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

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

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.     

用户QoS感知的GPU集群深度学习任务动态调度

提出一种GPU集群下用户服务质量QoS感知的深度学习研发平台上的动态任务调度方法.采用离线评估模块对深度学习任务进行离线评测并构建计算性能预测模型.在线调度模块基于性能预测模型,结合任务的预期QoS,共同开展任务放置和任务执行顺序的调度.在一个分布式GPU集群实例上的实验表明,该方法相比其他基准策略能够实现更高的QoS保证率和集群资源利用率.     

考虑负载平衡的科学工作流容错聚类算法研究

科学工作流执行过程中,多个任务组成的聚类作业相对单任务故障风险更高。容错聚类算法在进行故障恢复的同时面临着负载不平衡问题,为此提出了一种平衡重聚类算法（Balanced Re-clustering,BR）。该算法结合水平运行时间平衡聚类算法（Horizontal Runtime Balancing,HRB）对选择重聚类方法（Selective Re-clustering,SR）进行改进,将运行时间最长的任务分配给运行时间最短的类,在故障发生后重新运行失败的任务。实验结果表明,与现有的两种任务重聚类方法相比,BR算法的性能增益最高分别可达84%和18.75%,显著降低了工作流执行成本,提高了系统的运行效率。     

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

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

Workflow-and-Platform Aware task clustering for scientific workflow execution in Cloud environment

A scientific workflow, usually consists of a good mix of fine and coarse computational granularity tasks displaying varied runtime requirements. It has been observed that fine grained tasks incur more scheduling overhead than their execution time, when executed on widely distributed platforms. Task clustering is extensively used, in such situations, as a runtime optimization method which involves combining multiple short duration tasks into a cluster, to be scheduled on a single resource. This helps in minimizing the scheduling overheads of the fine grained tasks. However, tasks grouping curtails the degree of parallelism and hence needs to be done optimally. Though a number of task clustering techniques have been developed to reduce the impact of system overheads, they fail to identify the appropriate number of clusters at each level of workflow in order to achieve maximum possible parallelism. This work proposes a level based autonomic Workflow-and-Platform Aware (WPA) task clustering technique which takes into consideration both; the workflow structure and the underlying resource set size for task clustering. It aims to achieve maximum possible parallelism among the tasks at a level of a workflow while minimizing the system overheads and resource wastage. A comparative study with current state of the art task clustering approaches on four well-known scientific workflows show that the proposed method significantly reduces the overall workflow execution time and at the same time is able to consolidate the load onto minimum possible resources.     

Modeling, run-time optimization and execution of distributed workflow applications in the JEE-based BeesyCluster environment

The paper presents a complete solution for modeling scientific and business workflow applications, static and just-in-time QoS selection of services and workflow execution in a real environment. The workflow application is modeled as an acyclic directed graph where nodes denote tasks and edges denote dependencies between the tasks. The BeesyCluster middleware is used to allow providers to publish services from sequential or parallel applications, from their servers or clusters. Optimization algorithms are proposed to select a capable service for each task so that a global criterion is optimized such as a product of workflow execution time and cost, a linear combination of those or minimization of the time with a cost constraint. The paper presents implementation details of the multithreaded workflow execution engine implemented in JEE. Several tests were performed for three different optimization goals for two business and scientific workflow applications. Finally, the overhead of the solution is presented.     

基于节点集计算能力差异的Hadoop自适应任务调度算法

针对异构集群任务推测式执行算法存在的任务进度比例固定、落后任务被动选取等问题,提出基于快慢节点集计算能力差异的自适应任务调度算法。该算法量化节点集计算能力差异实现分集调度,并通过节点与任务速率的动态反馈及时更新快慢节点集,提高节点集资源利用率与任务并行度。在两节点集中,利用动态调整任务进度比例判别落后任务,主动选择采用替代执行方式为落后任务执行备份任务的快节点,从而提升任务执行效率。与最长近似结束时间(LATE)算法的实验对比结果表明,该算法在短作业集、混合型作业集、出现节点性能下降的混合型作业集执行时间上比LATE算法分别缩短了5.21%、20.51%、23.86%,启用的备份任务数比LATE算法明显减少。所提算法可使任务主动适应节点差异,在减少备份任务的同时有效提高作业整体执行效率。     

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

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

面向Flink的负载均衡任务调度算法的研究与实现

Apache Flink是现在主流的大数据分布式计算引擎之一,其中任务调度问题是分布式计算系统中的关键问题。由于集群的异构性以及不同算子复杂度不同,大数据计算系统Flink中不可避免地会出现负载不均的情况,针对这种问题,提出了基于资源反馈的负载均衡任务调度算法RFTS。通过实时资源监控、区域划分和基于人工萤火虫优化的任务调度算法3个模块,把负载过重的机器中处于等待状态的任务分配给负载较轻的机器,来实现集群的负载均衡,提高系统集群利用率和执行效率。最后通过基于TPC-C和TPC-H数据集的实验结果表明,RFTS算法从执行时间和吞吐量2个方面有效提升了Apache Flink计算系统的性能。