Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

云计算环境任务调度方法研究综述

随着应用程序计算需求的快速增长,异构计算资源不断地增多,任务调度成为云计算领域中重要的研究问题。任务调度负责将用户任务匹配给合适的虚拟计算资源,算法的优劣将直接影响响应时间、最大完工时间、能耗、成本、资源利用率等一系列与用户和云服务供应商经济利益密切相关的性能指标大小。针对独立任务和科学工作流这两类云环境主流任务,结合不同云环境特征对任务调度算法研究进展进行综述和讨论。回顾梳理已有的任务调度类型、调度机制及其优缺点;归纳单云环境和混合云、多云及联盟云等跨云环境下任务调度特征,并对部分相关典型文献的使用方法、优化目标、优缺点等方面进行阐述,在此基础上讨论各个环境下任务调度研究现状;进一步对各类环境下文献使用的调度优化方法进行梳理,明确其使用范围;总结并指出需要对计算数据密集型应用在跨云环境下的任务调度研究进行重点关注。     

Task Scheduling for Multi-Cloud Computing Subject to Security and Reliability Constraints

The rise of multi-cloud systems has been spurred. For safety-critical missions, it is important to guarantee their security and reliability. To address trust constraints in a heterogeneous multi-cloud environment, this work proposes a novel scheduling method called matching and multi-round allocation (MMA) to optimize the makespan and total cost for all submitted tasks subject to security and reliability constraints. The method is divided into two phases for task scheduling. The first phase is to find the best matching candidate resources for the tasks to meet their preferential demands including performance, security, and reliability in a multi-cloud environment; the second one iteratively performs multiple rounds of re-allocating to optimize tasks execution time and cost by minimizing the variance of the estimated completion time. The proposed algorithm, the modified cuckoo search (MCS), hybrid chaotic particle search (HCPS), modified artificial bee colony (MABC), max-min, and min-min algorithms are implemented in CloudSim to create simulations. The simulations and experimental results show that our proposed method achieves shorter makespan, lower cost, higher resource utilization, and better trade-off between time and economic cost. It is more stable and efficient.      

云环境中基于分解的多目标工作流调度算法

云服务提供商在给用户提供海量虚拟资源的同时,也面临着一个现实的问题,即怎样调度这些资源,以最小的代价(完工时间、执行费用、资源利用率等)完成工作流的执行。针对IaaS环境下的工作流调度问题,以完工时间和执行费用作为目标,提出了一种基于分解的多目标工作流调度算法。该算法结合了基于列表的启发式算法和多目标进化算法的选择过程,采用一种分解方法,将多目标优化问题分解为一组单目标优化子问题,然后同时求解这些单目标子问题,使得调度过程更为简单有效。算法利用天马项目发布的现实世界中的工作流进行实验,结果表明,和MOHEFT算法以及NSGA-II*算法相比较,所提出的算法能得到更优的Pareto解集,同时具有更低的时间复杂度。     

Multi-objective energy-efficient workflow scheduling using list-based heuristics

Workflow applications are a popular paradigm used by scientists for modelling applications to be run on heterogeneous high-performance parallel and distributed computing systems. Today, the increase in the number and heterogeneity of multi-core parallel systems facilitates the access to high-performance computing to almost every scientist, yet entailing additional challenges to be addressed. One of the critical problems today is the power required for operating these systems for both environmental and financial reasons. To decrease the energy consumption in heterogeneous systems, different methods such as energy-efficient scheduling are receiving increasing attention. Current schedulers are, however, based on simplistic energy models not matching the reality, use techniques like DVFS not available on all types of systems, or do not approach the problem as a multi-objective optimisation considering both performance and energy as simultaneous objectives. In this paper, we present a new Pareto-based multi-objective workflow scheduling algorithm as an extension to an existing state-of-the-art heuristic capable of computing a set of tradeoff optimal solutions in terms of makespan and energy efficiency. Our approach is based on empirical models which capture the real behaviour of energy consumption in heterogeneous parallel systems. We compare our new approach with a classical mono-objective scheduling heuristic and state-of-the-art multi-objective optimisation algorithm and demonstrate that it computes better or similar results in different scenarios. We analyse the different tradeoff solutions computed by our algorithm under different experimental configurations and we observe that in some cases it finds solutions which reduce the energy consumption by up to 34.5% with a slight increase of 2% in the makespan.     

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.     

Reliability-aware scheduling strategy for heterogeneous distributed computing systems

Heterogeneous computing systems are promising computing platforms, since single parallel architecture based systems may not be sufficient to exploit the available parallelism with the running applications. In some cases, heterogeneous distributed computing (HDC) systems can achieve higher performance with lower cost than single-machine supersystems. However, in HDC systems, processors and networks are not failure free and any kind of failure may be critical to the running applications. One way of dealing with such failures is to employ a reliable scheduling algorithm. Unfortunately, most existing scheduling algorithms for precedence constrained tasks in HDC systems do not adequately consider reliability requirements of inter-dependent tasks. In this paper, we design a reliability-driven scheduling architecture that can effectively measure system reliability, based on an optimal reliability communication path search algorithm, and then we introduce reliability priority rank (RRank) to estimate the task’s priority by considering reliability overheads. Furthermore, based on directed acyclic graph (DAG) we propose a reliability-aware scheduling algorithm for precedence constrained tasks, which can achieve high quality of reliability for applications. The comparison studies, based on both randomly generated graphs and the graphs of some real applications, show that our scheduling algorithm outperforms the existing scheduling algorithms in terms of makespan, scheduling length ratio, and reliability. At the same time, the improvement gained by our algorithm increases as the data communication among tasks increases.     

一种可靠性驱动的云工作流调度遗传算法

为了解决云环境中工作流调度的可靠性问题,提出了一种基于可靠性驱动信誉度模型的工作流调度遗传算法RDR-GA。算法以工作流执行跨度makespan与可靠性最优化为目标,设计了一种基于时间依赖的可靠性驱动信誉度模型,通过该模型可以有效评估资源可靠性。同时,为了寻找遗传最优解,算法设计了新的遗传进化和评估机制,包括：1)以进化算子对调度解中的任务-资源映射进行遗传进化;2)以两阶段MAX-MIN策略评估并决定调度解的任务执行序列。仿真实验结果表明,满足可靠性驱动的信誉度算法不仅能够以更精确的信誉度改善工作流应用执行可靠性,而且能够以比同类遗传算法更快的收敛速度得到进化更优解。     

Energy-Aware Scheduling for Tasks with Target-Time in Blockchain based Data Centres

Cloud computing infrastructures have intended to provide computing services to end-users through the internet in a pay-per-use model. The extensive deployment of the Cloud and continuous increment in the capacity and utilization of data centers (DC) leads to massive power consumption. This intensifying scale of DCs has made energy consumption a critical concern. This paper emphasizes the task scheduling algorithm by formulating the system model to minimize the makespan and energy consumption incurred in a data center. Also, an energy-aware task scheduling in the Blockchain-based data center was proposed to offer an optimal solution that minimizes makespan and energy consumption. The established model was analyzed with a target-time responsive precedence scheduling algorithm. The observations were analyzed and compared with the traditional scheduling algorithms. The outcomes exhibited that the developed solution incurs better performance with a response to resource utilization and decreasing energy consumption. The investigation revealed that the applied strategy considerably enhanced the effectiveness of the designed schedule.

     

CLPS-GA: A case library and Pareto solution-based hybrid genetic algorithm for energy-aware cloud service scheduling

Since the appearance of cloud computing, computing capacity has been charged as a service through the network. The optimal scheduling of computing resources (OSCR) over the network is a core part for a cloud service center. With the coming of virtualization, the OSCR problem has become more complex than ever. Previous work, either on model building or scheduling algorithms, can no longer offer us a satisfactory resolution. In this paper, a more comprehensive and accurate model for OSCR is formulated. In this model, the cloud computing environment is considered to be highly heterogeneous with processors of uncertain loading information. Along with makespan, the energy consumption is considered as one of the optimization objectives from both economic and ecological perspectives. To provide more attentive services, the model seeks to find Pareto solutions for this bi-objective optimization problem. On the basis of classic multi-objective genetic algorithm, a case library and Pareto solution based hybrid Genetic Algorithm (CLPS-GA) is proposed to solve the model. The major components of CLPS-GA include a multi-parent crossover operator (MPCO), a two-stage algorithm structure, and a case library. Experimental results have verified the effectiveness of CLPS-GA in terms of convergence, stability, and solution diversity.     

Reliability versus performance for critical applications

Applications implemented on critical systems are subject to both safety critical and real-time constraints. Classically, applications are specified as precedence task graphs that must be scheduled onto a given target multiprocessor heterogeneous architecture. We propose a new method for simultaneously optimizing two objectives: the execution time and the reliability of the schedule. The problem is decomposed into two successive steps: a spatial allocation during which the reliability is maximized (randomized algorithm), and a scheduling during which the makespan is minimized (list scheduling algorithm). It allows us to produce several trade-off solutions, among which the user can choose the solution that best fits the application’s requirements. Reliability is increased by replicating adequate tasks onto well chosen processors. Our fault model assumes that processors are fail-silent, that they are subject to transient failures, and that the occurrences of failures follow a constant parameter Poisson law. We assess and validate our method by running extensive simulations on both random graphs and actual application graphs. They show that it is competitive, in terms of makespan, compared to existing reference scheduling methods for heterogeneous processors (HEFT), while providing a better reliability.     

On the efficiency of several VM provisioning strategies for workflows with multi-threaded tasks on clouds

Cloud computing promises the delivery of on-demand pay-per-use access to unlimited resources. Using these resources requires more than a simple access to them as most clients have certain constraints in terms of cost and time that need to be fulfilled. Therefore certain scheduling heuristics have been devised to optimize the placement of client tasks on allocated virtual machines. The applications can be roughly divided in two categories: independent bag-of-tasks and workflows. In this paper we focus on the latter and investigate a less studied problem, i.e., the effect the virtual machine allocation policy has on the scheduling outcome. For this we look at how workflow structure, execution time, virtual machine instance type affect the efficiency of the provisioning method when cost and makespan are considered. To aid our study we devised a mathematical model for cost and makespan in case single or multiple instance types are used. While the model allows us to determine the boundaries for two of our extreme methods, the complexity of workflow applications calls for a more experimental approach to determine the general relation. For this purpose we considered synthetically generated workflows that cover a wide range of possible cases. Results have shown the need for probabilistic selection methods in case small and heterogeneous execution times are used, while for large homogeneous ones the best algorithm is clearly noticed. Several other conclusions regarding the efficiency of powerful instance types as compared to weaker ones, and of dynamic methods against static ones are also made.     

Cost-Time Efficient Scheduling Plan for Executing Workflows in the Cloud

The emergence of Cloud Computing as a model of service provisioning in distributed systems instigated researchers to explore its pros and cons on executing different large scale scientific applications, i.e., Workflows. One of the most challenging problems in clouds is to execute workflows while minimizing the execution time as well as cost incurred by using a set of heterogeneous resources over the cloud simultaneously. In this paper, we present, Budget and Deadline Constrained Heuristic based upon Heterogeneous Earliest Finish Time (HEFT) to schedule workflow tasks over the available cloud resources. The proposed heuristic presents a beneficial trade-off between execution time and execution cost under given constraints. The proposed heuristic is evaluated for different synthetic workflow applications by a simulation process and comparison is done with state-of-art algorithm i.e. BHEFT. The simulation results show that our proposed scheduling heuristic can significantly decrease the execution cost while producing makespan as good as the best known scheduling heuristic under the same deadline and budget constraints.     

ARMCO: Advanced topics in resource management for ubiquitous cloud computing: An adaptive approach

Cloud Computing can be seen as one of the latest major evolution in computing offering unlimited possibility to use ICT in various domains: business, smart cities, medicine, environmental computing, mobile systems, design and implementation of cyber-infrastructures. The recent expansion of Cloud Systems has led to adapting resource management solutions for large number of wide distributed and heterogeneous datacenters. The adaptive methods used in this context are oriented on: self-stabilizing, self-organizing and autonomic systems; dynamic, adaptive and machine learning based distributed algorithms; fault tolerance, reliability, availability of distributed systems. The pay-per-use economic model of Cloud Computing comes with a new challenge: maximizing the profit for service providers, minimizing the total cost for customers and being friendly with the environment.This special issue presents advances in virtual machine assignment and placement, multi-objective and multi-constraints job scheduling, resource management in federated Clouds and in heterogeneous environments, dynamic topology for data distribution, workflow performance improvement, energy efficiency techniques and assurance of Service Level Agreements.     

Multi-objective workflow grid scheduling using \varepsilon -fuzzy dominance sort based discrete particle swarm optimization

With the rapid development of networking technology, grid computing has emerged as a source for satisfying the increasing demand of the computing power of scientific computing community. Mostly, the user applications in scientific and enterprise domains are constructed in the form of workflows in which precedence constraints between tasks are defined. Scheduling of workflow applications belongs to the class of NP-hard problems, so meta-heuristic approaches are preferred options. In this paper, $\varepsilon $ -fuzzy dominance sort based discrete particle swarm optimization ( $\varepsilon $ -FDPSO) approach is used to solve the workflow scheduling problem in the grid. The $\varepsilon $ -FDPSO approach has never been used earlier in grid scheduling. The metric, fuzzy dominance which quantifies the relative fitness of solutions in multi-objective domain is used to generate the Pareto optimal solutions. In addition, the scheme also incorporates a fuzzy based mechanism to determine the best compromised solution. For the workflow applications two scheduling problems are solved. In one of the scheduling problems, we addressed two major conflicting objectives, i.e. makespan (execution time) and cost, under constraints (deadline and budget). While, in other, we optimized makespan, cost and reliability objectives simultaneously in order to incorporate the dynamic characteristics of grid resources. The performance of the approach has been compared with other acknowledged meta-heuristics like non-dominated sort genetic algorithm and multi-objective particle swarm optimization. The simulation analysis substantiates that the solutions obtained with $\varepsilon $ -FDPSO deliver better convergence and uniform spacing among the solutions keeping the computation overhead limited.     

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.     

处理顺序约束的信息物理融合系统静态任务表调度算法

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (Directed acyclic graph, DAG)的执行跨度为目标,改变HEFT (Heterogeneous earliest finish time)算法中任务上行权重的计算方法, 获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT (Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时, 分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确. 确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT, CPOP (Critical-path-on-a-processor)和LDCP (Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.     

Autonomic cloud resource provisioning and scheduling using meta-heuristic algorithm

We investigate that resource provisioning and scheduling is a prominent problem due to heterogeneity as well as dispersion of cloud resources. Cloud service providers are building more and more datacenters due to demand of high computational power which is a serious threat to environment in terms of energy requirement. To overcome these issues, we need an efficient meta-heuristic technique that allocates applications among the virtual machines fairly and optimizes the quality of services (QoS) parameters to meet the end user objectives. Binary particle swarm optimization (BPSO) is used to solve real-world discrete optimization problems but simple BPSO does not provide optimal solution due to improper behavior of transfer function. To overcome this problem, we have modified transfer function of binary PSO that provides exploration and exploitation capability in better way and optimize various QoS parameters such as makespan time, energy consumption, and execution cost. The computational results demonstrate that modified transfer function-based BPSO algorithm is more efficient and outperform in comparison with other baseline algorithm over various synthetic datasets.

     

Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm

The traditional production scheduling problem considers performance indicators such as processing time, cost, and quality as optimization objectives in manufacturing systems; however, it does not take energy consumption or environmental impacts completely into account. Therefore, this paper proposes an energy-efficient model for flexible flow shop scheduling (FFS). First, a mathematical model for a FFS problem, which is based on an energy-efficient mechanism, is described to solve multi-objective optimization. Since FFS is well known as a NP-hard problem, an improved, genetic-simulated annealing algorithm is adopted to make a significant trade-off between the makespan and the total energy consumption to implement a feasible scheduling. Finally, a case study of a production scheduling problem for a metalworking workshop in a plant is simulated. The experimental results show that the relationship between the makespan and the energy consumption may be apparently conflicting. In addition, an energy-saving decision is performed in a feasible scheduling. Using the decision method, there could be significant potential for minimizing energy consumption.     

云环境下基于强化学习的多目标任务调度算法

针对云计算环境下的多目标任务调度问题,提出一种新的基于Q学习的多目标优化任务调度算法(Multi-objective Task Scheduling Algorithm based on Q-learning,QM TS).该算法的主要思想是:首先,在任务排序阶段利用Q-learning算法中的自学习过程得到更加合理的任务序列;然后,在虚拟机分配阶段使用线性加权法综合考虑任务最早完成时间和计算节点的计算成本,达到同时优化多目标问题的目的;最后,以产生更小的makespan和总成本为目标函数对任务进行调度,得到任务完成后的实验结果.实验结果表明,QMTS算法在使用Q-learning对任务进行排序后可以得到比HEFT算法更小的makespan;并且根据优化多目标调度策略在任务执行过程中减少了makespan和总成本,是一种有效的多目标优化任务调度算法.