Bandwidth‐aware divisible task scheduling for cloud computing

Task scheduling is a fundamental issue in achieving high efficiency in cloud computing. However, it is a big challenge for efficient scheduling algorithm design and implementation (as general scheduling problem is NP‐complete). Most existing task‐scheduling methods of cloud computing only consider task resource requirements for CPU and memory, without considering bandwidth requirements. In order to obtain better performance, in this paper, we propose a bandwidth‐aware algorithm for divisible task scheduling in cloud‐computing environments. A nonlinear programming model for the divisible task‐scheduling problem under the bounded multi‐port model is presented. By solving this model, the optimized allocation scheme that determines proper number of tasks assigned to each virtual resource node is obtained. On the basis of the optimized allocation scheme, a heuristic algorithm for divisible load scheduling, called bandwidth‐aware task‐scheduling (BATS) algorithm, is proposed. The performance of algorithm is evaluated using CloudSim toolkit. Experimental result shows that, compared with the fair‐based task‐scheduling algorithm, the bandwidth‐only task‐scheduling algorithm, and the computation‐only task‐scheduling algorithm, the proposed algorithm (BATS) has better performance. Copyright © 2012 John Wiley & Sons, Ltd.     

Feedback fuzzy-DVS scheduling of control tasks

To consider the energy-aware scheduling problem in computer-controlled systems is necessary to improve the control performance, to use the limited computing resource sufficiently, and to reduce the energy consumption to extend the lifetime of the whole system. In this paper, the scheduling problem of multiple control tasks is discussed based on an adjustable voltage processor. A feedback fuzzy-DVS (dynamic voltage scaling) scheduling architecture is presented by applying technologies of the feedback control and the fuzzy DVS. The simulation results show that, by using the actual utilization as the feedback information to adjust the supply voltage of processor dynamically, the high CPU utilization can be implemented under the precondition of guaranteeing the control performance, whilst the low energy consumption can be achieved as well. The proposed method can be applied to the design in computer-controlled systems based on an adjustable voltage processor.     

Time and Energy Performance of Parallel Systems with Hierarchical Memory

In this paper we analyze the impact of memory hierarchies on time-energy trade-off in parallel computations. Contemporary computing systems have deep memory hierarchies with significantly different speeds and power consumptions. This results in nonlinear phenomena in the processing time and energy usage emerging when the size of the computation is growing. In this paper the nonlinear dependence of the time and energy on the size of the solved problem is formalized and verified using measurements in practical computer systems. Then it is applied to formulate a problem of minimum time and minimum energy scheduling parallel processing of divisible loads. Divisible load theory is a scheduling and performance model of data-parallel applications. Mathematical programming is exploited to solve the scheduling problem. A trade-off between energy and schedule length is analyzed and again nonlinear relationships between these two criteria are observed. Further performance analysis reveals that energy consumption and schedule length are ruled by a complex interplay between the costs and speeds of on-core and out-of-core computations, communication delays, and activating new machines.     

A green energy-efficient scheduling algorithm using the DVFS technique for cloud datacenters

Information and communication technology (ICT) has a profound impact on environment because of its large amount of CO₂ emissions. In the past years, the research field of “green” and low power consumption networking infrastructures is of great importance for both service/network providers and equipment manufacturers. An emerging technology called Cloud computing can increase the utilization and efficiency of hardware equipment. The job scheduler is needed by a cloud datacenter to arrange resources for executing jobs. In this paper, we propose a scheduling algorithm for the cloud datacenter with a dynamic voltage frequency scaling technique. Our scheduling algorithm can efficiently increase resource utilization; hence, it can decrease the energy consumption for executing jobs. Experimental results show that our scheme can reduce more energy consumption than other schemes do. The performance of executing jobs is not sacrificed in our scheme. We provide a green energy-efficient scheduling algorithm using the DVFS technique for Cloud computing datacenters.     

Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

Modeling and analyzing the energy consumption of fork‐join‐based task parallel programs

Because of environmental and monetary concerns, it is increasingly important to reduce the energy consumption in all areas, including parallel and high performance computing. In this article, we propose an approach to reduce the energy consumption needed for the execution of a set of tasks computed in parallel in a fork‐join fashion. The approach consists of an analytical model for the energy consumption of a parallel computation in fork‐join form on dynamic voltage frequency scaling processors, a theoretical specification of an energy‐optimal frequency‐scaled state, and the energy minimization by computing optimal scaling factors. For larger numbers of tasks, the approach is extended by scheduling algorithms, which exploit the analytical result and aim at a reduction of the energy. Energy measurements of a complex numerical method and the SPEC CPU2006 benchmarks as well as simulations for a large number of randomly generated tasks illustrate and validate the energy modeling, the minimization, and the scheduling results. Copyright © 2014 John Wiley & Sons, Ltd.     

Power‐aware provisioning of virtual machines for real‐time Cloud services

Reducing power consumption has been an essential requirement for Cloud resource providers not only to decrease operating costs, but also to improve the system reliability. As Cloud computing becomes emergent for the Anything as a Service (XaaS) paradigm, modern real‐time services also become available through Cloud computing. In this work, we investigate power‐aware provisioning of virtual machines for real‐time services. Our approach is (i) to model a real‐time service as a real‐time virtual machine request; and (ii) to provision virtual machines in Cloud data centers using dynamic voltage frequency scaling schemes. We propose several schemes to reduce power consumption by hard real‐time services and power‐aware profitable provisioning of soft real‐time services. Copyright © 2011 John Wiley & Sons, Ltd.     

Power-aware fixed priority scheduling for sporadic tasks in hard real-time systems

In this paper, we consider the generalized power model in which the focus is the dynamic power and the static power, and we study the problem of the canonical sporadic task scheduling based on the rate-monotonic (RM) scheme. Moreover, we combine with the dynamic voltage scaling (DVS) and dynamic power management (DPM). We present a static low power sporadic tasks scheduling algorithm (SSTLPSA), assuming that each task presents its worst-case work-load to the processor at every instance. In addition, a more energy efficient approach called a dynamic low power sporadic tasks scheduling algorithm (DSTLPSA) is proposed, based on reclaiming the dynamic slack and adjusting the speed of other tasks on-the-fly in order to reduce energy consumption while still meeting the deadlines. The experimental results show that the SSTLPSA algorithm consumes 26.55–38.67% less energy than that of the RM algorithm and the DSTLPSA algorithm reduces the energy consumption up to 18.38–30.51% over the existing DVS algorithm.     

A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems

In this paper, we investigate the problem of scheduling precedence-constrained parallel applications on heterogeneous computing systems (HCSs) like cloud computing infrastructures. This kind of application was studied and used in many research works. Most of these works propose algorithms to minimize the completion time (makespan) without paying much attention to energy consumption.We propose a new parallel bi-objective hybrid genetic algorithm that takes into account, not only makespan, but also energy consumption. We particularly focus on the island parallel model and the multi-start parallel model. Our new method is based on dynamic voltage scaling (DVS) to minimize energy consumption.In terms of energy consumption, the obtained results show that our approach outperforms previous scheduling methods by a significant margin. In terms of completion time, the obtained schedules are also shorter than those of other algorithms. Furthermore, our study demonstrates the potential of DVS.     

多核系统中基于Global EDF 的在线节能实时调度算法

随着多核系统能耗问题日益突出,在满足时间约束条件下降低系统能耗成为多核实时节能调度研究中亟待解决的问题之一.现有研究成果基于事先已知实时任务属性的假设,而实际应用中,只有当任务到达之后才能够获得其属性.为此,针对一般任务模型,不基于任何先验知识提出一种多核系统中基于Global EDF在线节能硬实时任务调度算法,通过引入速度调节因子,利用松弛时间,结合动态功耗管理和动态电压/频率调节技术,降低多核系统中任务的执行速度,达到实时约束与能耗节余之间的合理折衷.所提出的算法仅在上下文切换和任务完成时进行动态电压/频率调节,计算复杂度小,易于在实时操作系统中实现.实验结果表明,该算法适用于不同类型的片上动态电压/频率调节技术,节能效果始终优于Global EDF算法,最多可节能15％～20％,最少可节能5％～10％.     

Joint optimization method for task scheduling time and energy consumption in mobile cloud computing environment

An unheard of growth in mobile data traffic has drawn attention from academia and industry. Mobile cloud computing is an emerging computing paradigm combining cloud computing and mobile networks to alleviate resource-constrained limitations of mobile devices, which can greatly improve network quality of service and efficiency to make good use of available network resource. Mobile cloud computing not only inherits the advantages of strong computing capacity and massive storage of cloud computing, but also overcomes the time and geographical restrictions, bringing benefits for mobile users to offload complex computation to powerful cloud servers for execution anytime and anywhere. To this end, an optimal task workflow scheduling scheme is proposed for the mobile devices, based on the dynamic voltage and frequency scaling technique and the whale optimization algorithm. Through considering three factors: task execution position, task execution sequence, and operating voltage and frequency of mobile devices, this study makes a tradeoff between performance and energy consumption by solving the joint optimization for task completion time and energy consumption simultaneously. Finally, a series of extensive simulation results has demonstrated and verified the scheme has distinguished performance in terms of efficiency and operational cost, providing feasible solutions to similar optimization problems of mobile cloud computing.     

System-level integrated power management for handheld systems

We propose a system-level integrated power management scheme for battery-operated handheld systems such as cell phones and PDAs. Rather than dealing separately with each system component, we consider the interactions between CPU, WNIC (wireless network interface card), LCD, and applications, to reduce energy consumption at the system-level. Depending on the type of applications, the proposed scheme takes the interaction between CPU voltage and frequency and either LCD clock frequency or WNIC power modes, selectively, or both of them. The proposed method selects voltage for CPU in the context of LCD clock speed to reduce the system energy consumption. The application type and the power mode of WNIC are also considered to control the CPU voltage and frequency. Experimental results show that our scheme reduces the system energy consumption by as much as 30% compared to the systems of simply combining DVS (dynamic voltage scaling) and DPM (dynamic power management) or those of using no energy saving policy.     

System level fixed priority energy management algorithm for embedded real time application

Dynamic power management (DPM) and dynamic voltage scaling (DVS) are crucial techniques to reduce the energy consumption in embedded real-time systems. Many previous studies have focused on the energy consumption of the processor or I/O devices. In this paper, we focus on the problem of energy management integrating DVS and DPM techniques for periodic embedded real-time applications with rate monotonic (RM) policy and present a system level fixed priority energy-efficient scheduling (SLFPEES) algorithm. The SLFPEES algorithm consists of I/O device scheduling and job scheduling. I/O device scheduling is based on the dynamic power management with rate monotonic (DPM-RM) policy which puts devices into the sleep state when the idle interval is larger than devices break even time. Job scheduling is based on the RM policy and uses stack resource protocol (SRP) to guarantee exclusive access to the shared resources. For energy efficiency, the SLFPEES algorithm schedules the task with a lower speed and a higher speed. The experimental result shows that the SLFPEES algorithm can yield significantly energy savings with respect to the existing techniques.     

Energy efficient scheduling of parallel tasks on multiprocessor computers

In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed are addressed as combinatorial optimization problems. Two problems are defined, namely, minimizing schedule length with energy consumption constraint and minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor and multicore processor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems and environments where timing constraint is a major requirement. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy-efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. Each subproblem should be solved efficiently, so that heuristic algorithms with overall good performance can be developed. The above decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. A unique feature of our work is to compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally, not to compare the performance of heuristic algorithms among themselves only experimentally. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed, and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption and that our heuristic algorithms are able to produce solutions very close to optimum.     

Energy efficient scheduling for real-time embedded systems with QoS guarantee

While the dynamic voltage scaling (DVS) techniques are efficient in reducing the dynamic energy consumption for the processor, varying voltage alone becomes less effective for the overall energy reduction as the static power is growing rapidly. On the other hand, Quality of Service (QoS) is also a primary concern in the development of today’s pervasive computing systems. In this paper, we propose a dynamic approach to minimize the overall energy consumption for soft real-time systems while ensuring the QoS-guarantee. The QoS requirements are deterministically quantified with the window-constraints, which require that at least m out of each non-overlapped window of k consecutive jobs of a task meet their deadlines. Necessary and sufficient conditions for checking the feasibility of task sets with arbitrary service times and periods are developed to ensure that the window-constraints can be guaranteed in the worst case. And efficient scheduling techniques based on pattern variation and dynamic slack reclaiming extensions are proposed to combine the task procrastination and dynamic slowdown to minimize the energy consumption. In contrast to the previous leakage-aware dynamic reclaiming work which never scales the job speed below the critical speed, we will show that it can be more energy efficient to reclaim the slack with speed lower than the critical speed when necessary. Through extensive simulations, our experiment results demonstrate that the proposed techniques significantly outperformed the previous research in both overall and idle energy reduction.     

能量敏感实时系统能量管理分析*

便携系统越来越广泛的应用使得电池使用问题日益突出。对能量敏感实时系统的能量管理进行了分析和探讨,通过对任务执行过程中的电压进行调整以减少实时任务的能量消耗,给出了能量敏感实时系统的静态能量管理和动态能量管理的分析方法,并提出了具有截止时间限制的实时任务减少能量消耗的调度机制。     

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.     

异构计算系统中弹性节能调度策略研究

目前,节能已成为异构计算系统中减少电量开销、提高系统可靠性和保护环境的重要研究内容.传统的节能调度策略侧重于研究如何节能而忽略了用户对任务完成时间的期望,使得任务执行效果受到较大影响.特别是当系统负载较重时,由于电压调节缺乏自适应性,导致在某些情况下(如应急服务)的任务执行效果不可容忍.文中提出一种弹性节能调度策略(Elastic Energy-Aware Scheduling,EEAS),用于动态调度异构计算系统中非周期、独立任务.EEAS策略根据系统负载情况在系统节能与用户期望之间进行权衡,即当系统负载较重时,EEAS优先考虑用户期望,通过动态调整计算节点局部队列中等待任务的执行电压提高任务完成率;当系统负载较轻时,EEAS在尽量满足用户期望的基础上最大限度地降低任务执行电压以实现节能.文中通过大量的模拟实验比较了EEAS、GEA、HVEA和LVEA的性能.实验结果表明,EEAS的调度质量优于其他策略,可有效提高系统弹性.     

Adaptive energy-efficient scheduling for real-time tasks on DVS-enabled heterogeneous clusters

Developing energy-efficient clusters not only can reduce power electricity cost but also can improve system reliability. Existing scheduling strategies developed for energy-efficient clusters conserve energy at the cost of performance. The performance problem becomes especially apparent when cluster computing systems are heavily loaded. To address this issue, we propose in this paper a novel scheduling strategy–adaptive energy-efficient scheduling or AEES–for aperiodic and independent real-time tasks on heterogeneous clusters with dynamic voltage scaling. The AEES scheme aims to adaptively adjust voltages according to the workload conditions of a cluster, thereby making the best trade-offs between energy conservation and schedulability. When the cluster is heavily loaded, AEES considers voltage levels of both new tasks and running tasks to meet tasks’ deadlines. Under light load, AEES aggressively reduces the voltage levels to conserve energy while maintaining higher guarantee ratios. We conducted extensive experiments to compare AEES with an existing algorithm–MEG, as well as two baseline algorithms–MELV, MEHV. Experimental results show that AEES significantly improves the scheduling quality of MELV, MEHV and MEG.     

An Energy-Aware Heuristic Scheduling for Data-Intensive Workflows in Virtualized Datacenters

With the development of cloud computing, more and more data-intensive workflows have been deployed on virtualized datacenters. As a result, the energy spent on massive data accessing grows rapidly. In this paper, an energy-aware scheduling algorithm is proposed, which introduces a novel heuristic called Minimal Data-Accessing Energy Path for scheduling data-intensive workflows aiming to reduce the energy consumption of intensive data accessing. Extensive experiments based on both synthetical and real workloads are conducted to investigate the effectiveness and performance of the proposed scheduling approach. The experimental results show that the proposed heuristic scheduling can significantly reduce the energy consumption of storing/retrieving intermediate data generated during the execution of data-intensive workflow. In addition, it exhibits better robustness than existing algorithms when cloud systems are in presence of I/O- intensive workloads.