Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Game Theory strategy for Energy Efficient Scheduling <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> Game Theory strategy for Energy Efficient Scheduling <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> BIB002 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Game Theory strategy for Energy Efficient Scheduling <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> BIB003 </s> Energy Management for Cloud Computing: A Survey from Scheduling Perspective of Heuristic, Game Theory and Learning Strategy <s> Game Theory strategy for Energy Efficient Scheduling <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> BIB004
Equilibrium is a key concept in game theory and it aims to provide optimal solutions against several choices BIB003 . Nash equilibrium is a non-cooperative strategy where each player has its own game with its own way without bothering the other players. It shows the true colors of selfish behavior in reality, but remarkably effective. There are also cooperative game theories such as Nash axiomatic which finds bargain point and settle down BIB001 . Pre-scheduling and Scheduling using Game Theory (PSGT) by Abdeyazdan et al. BIB003 proposed energy efficient task scheduling with initial pre-scheduling process. PSGT aims for the best trade-off between makespan and energy consumption by discovering the equilibrium number of processors. Each level of task graph is considered as a selfish player with non-cooperative behavior by using Nash equilibrium concept that tried to get the best number of processors for themselves. PSGT determined the appropriate number of processors and then, merged the tasks for assigning to processors. PSGT is able to reach better energy consumption with less number of available parallel processors. The pre-scheduling stage as implemented by the authors is a good technique in massaging the tasks. It is because the system is 'more prepared' for scheduling the tasks thus it improves the performance. Instead of the noncooperative or Nash equilibrium, it could be interesting to alter this scheduling with the cooperative or Nash bargaining to see the result. Cooperative and Non-cooperative Task Scheduling by Bielik and Ahmad BIB004 that was based on Energy Aware Task Allocation (EATA) are converted into bargaining game for distributed heterogeneous grid. Results from both scheduling approaches (cooperative and non-cooperative) are used by Dynamic Voltage Frequency Scaling (DVFS) in the processor to reduce the energy consumption. Their work proved that cooperative scheduling saves 8% to 26% more energy compared to non-cooperative scheduling. In other words, non-cooperative scheduling is 3 to 4 times faster than cooperative scheduling. Low performance of the cooperative scheduling is caused by the complex pseudo-code. Incorporation of cooperative and non-cooperative scheduling would create a hybrid game theory approach for better performance. Meanwhile, Nash Bargaining Solution -Energy Aware Task Allocation (NBS-EATA) by Ahmad et al. BIB001 identified the bargaining point by combining the classical game theory techniques that applied the Kuhn-Tucker conditions and the Lagrangian. NBS-EATA performed better trade-off between energy consumption and performance compared to Greedy Heuristic. The authors mentioned that they selected the cooperative approach in this scheduling because their intention was to optimize the cumulative performance rather than individual cores. Generalized Tit-For-Tat Temperature-aware Scheduling (GTFTTS) by Wu et al. BIB002 used generalized Tit-For-Tat game theory for resource-rich environment. The scheduling decision for cooperation depends on the hardness factor (i.e., percentage of cooperation among other processors in prior round). While lowering the energy consumption in the whole system, the scheduling approach managed to avoid local hotspot in the processor thus increases the processors lifetime. GTFTTS is slightly better than Pure Tit for Tat scheduling and NBS-EATA in term of energy efficiency. It is achieved by occasionally forcing the neighboring cores to cooperate when some cores are overloaded. Table 2 . Energy model for energy efficient task scheduling with game theory approach