Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Multi-core processors are beginning to revolutionize the landscape of high-performance computing. In this paper, we address the problem of power-aware scheduling/mapping of tasks onto heterogeneous and homogeneous multi-core processor architectures. The objective of scheduling is to minimize the energy consumption as well as the makespan of computationally intensive problems. The multi- objective optimization problem is not properly handled by conventional approaches that try to maximize a single objective. Our proposed solution is based on game theory. We formulate the problem as a cooperate game. Although we can guarantee the existence of a Bargaining Point in this problem, the classical cooperative game theoretical techniques such as the Nash axiomatic technique cannot be used to identify the Bargaining Point due to low convergence rates and high complexity. Hence, we transform the problem to a max-max-min problem such that it can generate solutions with fast turnaround time. <s> BIB001 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> We address the problem of scheduling directed a-cyclic task graph (DAG) on a heterogeneous distributed processor system with the twin objectives of minimizing finish time and energy consumption. Previous scheduling heuristics have assigned DAGs to processors to minimize overall run-time of the application. But applications on embedded systems, such as high performance DSP in image processing, multimedia, and wireless security, need schedules which use low energy too. ::: ::: We develop a new scheduling algorithm called Energy Aware DAG Scheduling (EADAGS) on heterogeneous processors that can run on discrete operating voltages. Such processors can scale down their voltages and slow down to reduce energy whenever they idle due to task dependencies. EADAGS combines dynamic voltage scaling (DVS) with Decisive Path Scheduling (DPS) to achieve the twin objectives. Using simulations we show average energy consumption reduction over DPS by 40%. Energy savings increased with increasing number of nodes or increasing Communication to Computation Ratios and decreased with increasing parallelism or increasing number of available processors. These results were based on a software simulation study over a large set of randomly generated graphs as well as graphs for real-world problems with various characteristics. <s> BIB002 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Temperature-constraint computing environments are emerging those years, especially in embedding computing. A game theoretic temperature-aware scheduling algorithm for multi-core systems is proposed in this paper, namely, GTFTTS (Generalized Tit-For-Tat Temperature-aware Scheduling). GTFTTS is designed to work in a resource-rich environment where resources always compete for tasks. A generalized Tit-for-Tat based method, where whether a core will corporate or not is decided by a hardness factor, is considered in this paper. The algorithm is implemented in our TASS simulator. Simulations results show that the proposed game can reduce the temperature difference between different group of cores which effectively avoids the local hotspot of a processor. <s> BIB003 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> There is growing demand on datacenters to serve more clients with reasonable response times, demanding more hardware resources, and higher energy consumption. Energy-aware datacenters have thus been amongst the forerunners to deploy virtualization technology to multiplex their physical machines (PMs) to as many virtual machines (VMs) as possible in order to utilize their hardware resources more effectively and save power. The achievement of this objective strongly depends on how smart VMs are consolidated. In this paper, we show that blind consolidation of VMs not only does not reduce the power consumption of datacenters but it can lead to energy wastage. We present four models, namely the target system model, the application model, the energy model, and the migration model, to identify the performance interferences between processor and disk utilizations and the costs of migrating VMs. We also present a consolidation fitness metric to evaluate the merit of consolidating a number of known VMs on a PM based on the processing and storage workloads of VMs. We then propose an energy-aware scheduling algorithm using a set of objective functions in terms of this consolidation fitness metric and presented power and migration models. The proposed scheduling algorithm assigns a set of VMs to a set of PMs in a way to minimize the total power consumption of PMs in the whole datacenter. Empirical results show nearly 24.9% power savings and nearly 1.2% performance degradation when the proposed scheduling algorithm is used compared to when other scheduling algorithms are used. <s> BIB004 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Computation grids and computational clouds are becoming increasingly popular in the organizations which require massive computational capabilities. Building such infrastructures makes a lucrative business case, thanks to availability of cheap hardware components and affordable software. Maintaining computational grids or cloud, however, require careful planning as in such dedicated environments, round-the-clock availability of workstations is very crucial. Ensuring uninterrupted availability, not only demands mechanism for failover redundancy but also results in constant power drainage. The tradeoff between the cost and the performance is the constant dilemma that the operations of the data centers face today. In this paper, we propose various heuristics for power-aware scheduling algorithms for scheduling jobs with dependent tasks onto the computational grid. We formulate the problem as a multi-objective function which results in various cost-performance tradeoffs each lying within the solution boundary. <s> BIB005 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Large-scale distributed computing systems (LDSs), such as grids and clouds are primarily designed to provide massive computing capacity. These systems dissipate often excessive energy to both power and cool them. Concerns over greening these systems have prompted a call for scheduling policies with energy awareness (e.g., energy proportionality). The dynamic and heterogeneous nature of resources and tasks in LDSs is a major hurdle to be overcome for energy efficiency when designing scheduling policies. In this paper, we address the problem of scheduling tasks with different priorities (deadlines) for energy efficiency exploiting resource heterogeneity. Specifically, our investigation for energy efficiency focuses on two issues: (1) balancing the workload in the way utilization is maximized and (2) power management by controlling execution of tasks on processor for ensuring the energy is optimally consumed. We form a hierarchical scheduler that exploits the multi-core architecture for effective scheduling. Our scheduling approach exploits the diversity of task priority for proper load balancing across heterogeneous processors while observing energy consumption in the system. Simulation experiments prove the efficacy of our approach, and the comparison results indicate our scheduling policy helps improve energy efficiency of the system. <s> BIB006 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Energy consumption in large-scale distributed systems, such as computational grids and clouds gains a lot of attention recently due to its significant performance, environmental and economic implications. These systems consume a massive amount of energy not only for powering them, but also cooling them. More importantly, the explosive increase in energy consumption is not linear to resource utilization as only a marginal percentage of energy is consumed for actual computational works. This energy problem becomes more challenging with uncertainty and variability of workloads and heterogeneous resources in those systems. This paper presents a dynamic scheduling algorithm incorporating reinforcement learning for good performance and energy efficiency. This incorporation helps the scheduler observe and adapt to various processing requirements (tasks) and different processing capacities (resources). The learning process of our scheduling algorithm develops an association between the best action (schedule) and the current state of the environment (parallel system). We have also devised a task-grouping technique to help the decision-making process of our algorithm. The grouping technique is adaptive in nature since it incorporates current workload and energy consumption for the best action. Results from our extensive simulations with varying processing capacities and a diverse set of tasks demonstrate the effectiveness of this learning approach. <s> BIB007 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> This study looks at how increased memory utilisation affects throughput and energy consumption in scientific computing, especially in high-energy physics. Our aim is to minimise energy consumed by a set of jobs without increasing the processing time. The earlier tests indicated that, especially in data analysis, throughput can increase over 100% and energy consumption decrease 50% by processing multiple jobs in parallel per CPU core. Since jobs are heterogeneous, it is not possible to find an optimum value for the number of parallel jobs. A better solution is based on memory utilisation, but finding an optimum memory threshold is not straightforward. Therefore, a fuzzy logic-based algorithm was developed that can dynamically adapt the memory threshold based on the overall load. In this way, it is possible to keep memory consumption stable with different workloads while achieving significantly higher throughput and energy-efficiency than using a traditional fixed number of jobs or fixed memory threshold approaches. <s> BIB008 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Power efficiency is one of the main challenges in large-scale distributed systems such as datacenters, Grids, and Clouds. One can study the scheduling of applications in such large-scale distributed systems by representing applications as a set of precedence-constrained tasks and modeling them by a Directed Acyclic Graph. In this paper we address the problem of scheduling a set of tasks with precedence constraints on a heterogeneous set of Computing Resources (CRs) with the dual objective of minimizing the overall makespan and reducing the aggregate power consumption of CRs. Most of the related works in this area use Dynamic Voltage and Frequency Scaling (DVFS) approach to achieve these objectives. However, DVFS requires special hardware support that may not be available on all processors in large-scale distributed systems. In contrast, we propose a novel two-phase solution called PASTA that does not require any special hardware support. In its first phase, it uses a novel algorithm to select a subset of available CRs for running an application that can balance between lower overall power consumption of CRs and shorter makespan of application task schedules. In its second phase, it uses a low-complexity power-aware algorithm that creates a schedule for running application tasks on the selected CRs. We show that the overall time complexity of PASTA is $$O(p.v^{2})$$ where $$p$$ is the number of CRs and $$v$$ is the number of tasks. By using simulative experiments on real-world task graphs, we show that the makespan of schedules produced by PASTA are approximately 20 % longer than the ones produced by the well-known HEFT algorithm. However, the schedules produced by PASTA consume nearly 60 % less energy than those produced by HEFT. Empirical experiments on a physical test-bed confirm the power efficiency of PASTA in comparison with HEFT too. <s> BIB009 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> Prescheduling algorithms are targeted at restructuring of task graphs for optimal scheduling. Task graph scheduling is a NP-complete problem. This article offers a prescheduling algorithm for tasks to be executed on the networks of homogeneous processors. The proposed algorithm merges tasks to minimize their earliest start time while reducing the overall completion time. To this end, considering each task as a player attempting to reduce its earliest time as much as possible, we have applied the idea of Nash equilibrium in game theory to determine the most appropriate merging. Also, considering each level of a task graph as a player, seeking for distinct parallel processors to execute each of its independent tasks in parallel with the others, the idea of Nash equilibrium in game theory can be applied to determine the appropriate number of processors in a way that the overall idle time of the processors is minimized and the throughput is maximized. The communication delay will be explicitly considered in the comparisons. Our experiments with a number of known benchmarks task graphs and also two well-known problems of linear algebra, LU decomposition and Gauss---Jordan elimination, demonstrate the distinguished scheduling results provided by applying our algorithm. In our study, we consider ten scheduling algorithms: min---min, chaining, A ?, genetic algorithms, simulated annealing, tabu search, HLFET, ISH, DSH with task duplication, and our proposed algorithm (PSGT). <s> BIB010 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> This paper proposes energy-efficient scheduling algorithms for distributed heterogeneous grids. The conservation of energy consumption has a tirade of effects that improve system reliability, increases in the lifespan of the system, ideally with only a linear degradation in performance. With a few restrictions and proper modeling, we convert the Energy Aware Task Allocation (EATA) problem into a Bargaining game, wherein the machines compete with each other. Although we have done work previously in addressing the EATA problem, the question arises whether the players should cooperate or not. In this paper, we compare cooperative and non-cooperative games for the EATA problem on a heterogeneous set of machines. The contribution of the paper is not just the comparison of the two approaches but also two new algorithms for the EATA problem with energy consumption as the primary objective. The energy savings generated by the proposed algorithms is achieved through Dynamic Voltage and Frequency Scaling (DVFS) at the processor level. The comparison leads to some interesting results, highlighting the strength of each scheme. <s> BIB011 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Scheduling Name Energy Model <s> In order to reduce energy consumption of data centers while employing infrastructure resource effectively, a comprehensive resource management method using an improved online energy saving mapping algorithm for virtual machines of data centers is proposed. An intelligent feedback management framework is built for online resource optimization. We propose reinforcement learning and threshold based virtual machine migration to find the lowest energy consumption mapping between virtual machines and host of data centers dynamically and avoid the resources contention in physical machines. Our experimental results shows that the proposed effective online energy saving resource optimization methodology can reduce data center energy consumption by at least 30.3% compared to traditional random placement and save at least 10% running time compared to the offline Q-Learning scheduling algorithm. <s> BIB012
Power-efficient distributed BIB004 Power consumption = Summation of power consumed by processor and disk. Energy consumption = Integral of the power consumption over a period of time. PASTA BIB009 Power consumption of task schedule* = Power consumption of each CR** from the beginning of schedule to its finish time. *Schedule = Queue of application tasks. **CRs= Computing resources. PRISM BIB005 Resource utilization ratio = Ratio between the average active workstations and the total number of workstations. Energy saved = 1− Resource utilization ratio. Priority BIB006 Resource utilization = Power usage of processor at 100% utilization multiplied by total task execution time. Resource idle = Power usage of idle processor multiplied by total idle time. Energy consumption = The summation of resource utilization and idle. EADAG BIB002 Total energy consumption (without voltage scaling) = Total power consumed by processors multiplied by makespan. Total energy consumption (with voltage scaling) = Summation of non-idle power consumption* and idle power consumption** *non-idle power consumption refers to average power consumed by processors at normal voltage multiplied by non-idle time **idle power consumption refers to average power consumed by processors at lower voltage multiplied by idle time PSGT BIB010 Appropriate number of processor = Applying Nash equilibrium at each level of task graph. Cooperative and Non-cooperative Task Scheduling BIB011 Power consumption = Multiplication of voltage, frequency and effective capacitance. NBS-EATA BIB001 Energy consumption = Multiplication of capacitance, voltage and task cycles. GTFTTS BIB003 Power density of core = Multiplication of power and tasks cycles divided with area of core. The game theory approach is suitable for task scheduling in Cloud where there are limited knowledge of system states and resources. Although large payoff matrix in the game theory approach would create complex challenges but this approach is able to deal with energy consumption and system performance in dynamic computing environment. Table 2 summarizes the energy models with metrics and system behaviors that used to calculate energy efficiency based on the game theory scheduling discussed above. Adaptive Reinforcement Learning Based BIB007 Resource utilization = Power usage of processor at 100% utilization multiplied by total task execution time Resource idle = power usage of idle processor multiplied by total idle time Power consumption = The summation of resource utilization and idle Memory-based BIB008 Energy consumption = Multiplication of capacitance, voltage and task cycles. Online Energy Saving Resource Optimization BIB012 Energy level = Summation of resource utilization difference between hosts and optimal level, and disk utilization difference between hosts and optimal level