A Survey of the Impact of Task Scheduling Algorithms on Energy-Efficiency in Cloud Computing

A Survey of the Impact of Task Scheduling Algorithms on Energy-Efficiency in Cloud Computing

T. Jenifer Nirubah

Post-Graduate Student, Department of Computer Science and Engineering, Karunya University, India

Ms. Rose Rani John

Assistant professor, Department of Computer Science and Engineering, Karunya University, India

Abstract

Cloud computing is a recent and upcoming technology which includes various areas. One among them is energy conservation. Maintaining the efficiency of energy has become a major problem with increased usage of devices consuming more energy. Each and every person has a separate system in the current world. Many efforts have been taken to minimize energy consumption. In this paper, task scheduling is taken as the factor to reduce consumption of energy. Tasks can be assigned and scheduled based on the algorithms and so energy can be conserved.

1. Introduction

   Cloud computing has earned its place because of its outstanding characteristics. When compared with Internet, Internet is a collection of networked computers and Cloud is a distributed system that consists of a collection of inter-connected and virtualized computers. This model uses vacant resources which increases the economic efficiency through increased utilization rate and decreased energy consumption. The main purpose of Cloud computing is sharing of data, services and resources among the users. Cloud provides many applications beneficial to the users. The focus is on improving the utilization rate of the computers and decreasing the energy consumption. The mode of using in Cloud is pay per usage. The payment is done for whatever resources are consumed. The services provided by cloud computing is mainly divided into three categories namely Software as a Service (SaaS), Infrastructure as a Service (Iaas) and Platform as a Service (Paas) [1]. Cloud computing faces many problems. One among them is task scheduling. The problem of scheduling the tasks increases with increase in number of users of Cloud computing systems. Task scheduling can be done in such a way that energy consumption is minimized. This needs to be focused because the system performance

   may be reduced if tasks are not properly allocated and scheduled. The operating costs also increases unnecessarily. While speaking about energy consumption, green computing technology must be included as it deals with reducing pollution by conserving energy. Green computing can refer to energy-efficient personal computers. The purposes of energy consumption reduction are: minimizing performance losses, achieving target battery lifetime, satisfying performance requirements, minimizing power consumption, minimizing the CO2 emissions, maximizing the profit, maximizing resource utilization [2]. Since cloud computing systems are heterogeneous computing systems, the focus should be on minimizing energy consumption in the heterogeneous computing systems and thus enhancing green computing.

2. Task scheduling

   Task scheduling is the process of allocating the tasks to the processors and then scheduling them. Various task scheduling algorithms are used for this purpose. This section deals with such algorithms that have impact on energy efficiency. They are classified under: genetic algorithm, slack reclamation scheduling, green scheduling and power aware scheduling.

   1. Genetic algorithm

      Genetic algorithm is a search heuristic which is used for generating solutions to optimization and search problems [15]. Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population will be taken and are used to form a new population [16]. The genetic operations include reproduction, crossover, mutation, swap and exchange operations [17].

      1. Genetic algorithm for task scheduling. [3] presents the problem of scheduling and mapping of the precedence-constrained task graph to the processors in

         parallel and distributed computing systems as a major NP-complete problem. The existing genetic algorithms are monolithic and they do not concentrate on reducing the complexity of the optimization process. Hence there is the need for developing new genetic algorithms to improve the performance of the optimization process. Two algorithms that are developed are The Critical Path Genetic Algorithm (CPGA) and The Task Duplication Genetic Algorithm (TDGA). CPGA uses two fitness functions. First one concerns with minimizing the total execution time and the second one deal with load balance satisfaction. TDGA is based on a task duplication technique to overcome the communication overhead. The parameters are normalized schedule length, speedup and number of processors. The performance of CPGA algorithm is better than the already existing ones. Using TDGA algorithm, the communication delays are reduced and the overall execution time is minimized.

      2. Improved genetic algorithm. [4] discusses the problems of allocating the tasks and scheduling them, making use of the computing resources to complete the tasks within a shorter period of time and also reducing the cost. Genetic algorithm is used to complete the tasks within the average completion time and thereby reducing the cost. The improved genetic algorithm includes chromosome encoding and decoding, production of the initial population, fitness function, genetic operations: selection, crossover and mutation. The parameters are generations (population), cost, sumtime (s), average time (s) of task completion.

   2. Slack reclamation

      Slack reclamation is the process of executing individual tasks with slacks (free time) at a lower processor frequency [6]. In other words, it is the utilization of the idle time slots of processors by lowering the voltage supply [7]. The following concepts use slack reclamation scheduling.

      1. Linear combinations of DVFS-enabled processor frequencies. [5] discusses the energy consumption problem in distributed computing systems. A new slack reclamation algorithm is developed which uses a linear combination of the maximum and minimum processor frequencies to decrease energy consumption. Two more algorithms that are used are Reference DVFS (RDVFS) algorithm and Maximum-Minimum Frequency DVFS (MMF- DVFS) algorithm. RDVFS reduces task execution energy consumption by choosing the smallest available processor speed capable of finishing a job in given

         time. MMF-DVFS uses two processor frequencies namely the minimum and the maximum processor frequencies. The parameters are frequency and time. MMF-DVFS algorithm is best when compared to RDVFS algorithm. But both of them depend on the idle time of tasks. Increasing the number of processors increases the system idle time.

      2. MVFS-DVFS algorithm. [6] focuses on energy consumption problem in parallel and distributed computing systems. A new slack reclamation algorithm is proposed to achieve reduction in energy consumption. It is called as Multiple Voltage- Frequency Selection for Dynamic Voltage-Frequency Scaling (MVFS-DVFS) algorithm. The performance of this algorithm is evaluated with two sets of task graphs: randomly generated and real-world applications. The optimal energy in a discrete set of voltage-frequencies for each task is achieved by a combination of two voltage-frequencies. The various parameters used are frequency and time. The optimal energy in a discrete set of voltage-frequencies for each task is achieved by a combination of two voltage-frequencies. The overhead of running MVFS-DVFS is an issue. This occurs from the transition time of switching from one frequency to another frequency.

      3. Energy-conscious scheduling algorithms. [7] discusses the necessity to develop task scheduling algorithms in order to minimize energy consumption as the power and energy consumed by the computers and servers in the data centers reached beyond the limits. Energy-conscious scheduling algorithms are developed to solve the problem of scheduling precedence- constrained parallel applications in distributed computing systems. Two energy-conscious algorithms namely ECS and ECS makespan are used. Makespan is the time difference between start and finish of a sequence of tasks. The task scheduling problem using energy- conscious algorithms see that they do not violate precedence constraints. ECS accounts for energy consumption and makespan equally. ECS makespan considers makespan as a preferred performance metric. The parameters are schedule length ratio (SLR) and communication to computation ratio (CCR). Often when the energy consumption is minimized, the makespan increases.

      4. Slack reclamation in multi-processor real-time systems. [8] addresses the power consumption problem in high performance processors. Two novel power- aware scheduling algorithms are used for independent and dependent tasks to reduce the energy consumption. Power-aware scheduling for independent tasks includes

         two strategies namely Global Scheduling with Greedy Slack Reclamation and Global Scheduling with Shared Slack Reclamation (GSSR). In the former scheduling, any slack on one processor is used to reduce the speed of the next task running on this processor. The latter scheduling deals with estimated end time (EET) and start time of the next task (STNT). Power-aware scheduling for dependent tasks includes strategies like List Scheduling with Shared Slack Reclamation and Fixed-Order List Scheduling with Shared Slack Reclamation (LSSR). The former scheduling takes longer time because the ready time of the tasks change and thus the order at which the tasks are added to the queue is different from canonical execution order. In the latter scheduling method, the execution order of tasks is known during first step, so the tasks are put in the canonical execution order. The parameters are the energy consumption rate and the number of processors. The scheduling algorithm that uses shared slack reclamation saves energy more than the other static scheduling algorithms.

         1. Green scheduling

            Human race is threatened by problems like air pollution due to the carbon dioxide gas emission and improper disposal of e-waste. This environment pollution even causes harmful diseases. Energy consumption is increasing day by day so that there is a problem of lack of power and energy in future. Green computing technology should be enhanced so that the environment will be protected. This can be improved by reducing the energy consumption level and thereby reducing the pollution due to carbon dioxide gas. There are many ways to achieve these reductions. One of the key areas is to efficiently manage the tasks given to a computer.

            1. Neural network predictor. [9] addresses the problem of energy shortage and global climate change. The power consumption rate has been a major problem in data centers. In order to optimize the server power consumption in Cloud computing, a green scheduling algorithm is designed, implemented, evaluated and integrated to a neural network predictor. A neural network predictor can predict the future load demand based on historical demand. Four different running modes are available to evaluate the algorithm. They are optimal mode, conventional mode, prediction mode and prediction plus 20% additional servers. The green scheduling algorithm determines which servers should be turned on/off. Each server must not be loaded more than its capacity C. The parameters are load demand and time. The best configuration among the four

               running modes is the prediction plus 20% additional servers.

            2. Speed optimization on heterogeneous cloud servers. [11] identifies that many servers waste a tremendous amount of energy and emit carbon dioxide gas. Hence the environment is getting polluted. Six innovative green task scheduling algorithms are developed in order to reduce the pollution and thereby lowering the energy consumption. They are developed for heterogeneous cloud servers with a certain deadline to complete the sequential tasks. The six algorithms are Shortest Task First for Computer with Minimum Energy (STF-CME) which assigns shortest task to computer with minimum energy slope, Longest Task First for Computer with Minimum Energy (LTF-CME) which assigns longest task to the computer with minimum energy slope, Random Task for Computer with Minimum Energy (RT-CME) which assigns tasks randomly to the computer with minimum energy slope, Shortest Task First for Random Computer(STF-RC) which assigns shortest task to any random computer, Longest Task First for Random Computer (LTF-RC) which assigns longest task to any random computer and Random Task for Random Computer (RT-RC) which assigns tasks randomly to any random computer. The parameters are energy consumption rate, deadline and number of tasks. Shortest Task First for Computer with Minimum Energy algorithm is the best among all the six algorithms. It conserves more energy than the other algorithms.

            3. Energy reduction on heterogeneous computers. [12] focuses on multi-task scheduling problem on multiple computers to reduce energy consumption and finish the required tasks before deadline. Two traditional heuristic task scheduling algorithms and two new green task scheduling algorithms are evolved. The two traditional heuristic task scheduling algorithms are namely Shortest Task First for Computer with Minimal Energy First with Maximum Speeds (STFCMEF-MS) algorithm and Longest Task First for Computer with Minimal Energy First with Maximum Speeds (LTFCMEF-MS) algorithm. They assign a task from the front in the task queue to a computer with minimum energy slope. Two new green task scheduling algorithms namely Shortest Task First for Computer with Minimal Energy First with Speed Adjustment (STFCMEF-SA) algorithm and Longest Task First for Computer with Minimal Energy First with Speed Adjustment (LTFCMEF-SA) algorithm are proposed to solve the same problem. These two algorithms optimize computer speeds to reduce energy consumption. The parameters used are

               number of tasks, energy reduction percentage and deadline. STFCMEF-SA algorithm and LTFCMEF-SA algorithm are more effective than STFCMEF-MS algorithm and LTFCMEF-MS algorithm in lowering energy consumption.

            4. Continuous and discrete speed task scheduling. [10] presents the problem of emission of large amount of carbon dioxide gas due to excessive usage of computer systems and servers. More amount of energy is also consumed. Six energy-efficient task scheduling algorithms with continuous speeds, six energy-efficient task scheduling algorithms with discrete speeds and hybrid algorithms are developed. Discrete speed can be a clock frequency. Hybrid algorithm is given for both continuous and discrete speeds. It conserves the maximum energy and found to be the best. The parameters are number of tasks, number of computers, deadline and energy consumption. The algorithms are not integrated into data centers and cloud computing systems.

         1. Power aware scheduling

            Power aware scheduling attempts to place the processes on CPUs in such a way that minimizes the systems overall consumption of the power [18]. The following are the concepts that uses power aware scheduling.

            1. Multiprocessor computers with dynamic voltage and speed. [13] presents task scheduling on multiprocessor computers with dynamic voltage and speed as a combinatorial optimization problem, i.e. the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint. Problem can be decomposed into two sub problemsnamely scheduling the tasks and determining power supplies. It is necessary to analyze the performance of list scheduling algorithms and equal-speed algorithms and so to say that they are asymptotically optimal. List scheduling algorithms deal with making a partition of

               n tasks into m groups. Variation in LS algorithm is based on the initial ordering of the tasks. In equal-speed algorithm, all the tasks are supplied with same power p and executed with same speed s. The parameters are the number of tasks, the number of processors. These algorithms are applicable to energy-efficient task scheduling in general multiprocessor computers, real- time multiprocessing systems, mobile computing and communication environments. But it deals with only

               independent tasks and not for tasks with precedence constraints.

            2. Power aware task clustering and list-based scheduling. [14] suggests the need for efficient algorithms to minimize the wasted server energy because the energy consumption reduction can lead to various advantages like reduction of operating costs, increasing of the system reliability and environmental respect. A scheduling heuristics is developed to present application experience for reducing power consumption of parallel tasks in a cluster with Dynamic Voltage Frequency Scaling (DVFS) technique. Power Aware Task Clustering (PATC) algorithm will guide the edge zeroing process in order to reduce the power consumption. The Power Aware List-based Scheduling (PALS) algorithm employs Earliest Task First (ETF) algorithm to find the best effort task response time. The parameters are voltage and time. The slack time for non-critical jobs is studied. It is not deployed in real applications.

3. Conclusion

In cloud computing, energy efficiency is taken into account. More amount of energy consumption results in lack of energy and power in future. Also carbon dioxide gas is emitted into the atmosphere. Minimizing the amount of consumption of energy is achieved to a certain extent by many task scheduling algorithms. Some of those task scheduling algorithms are classified as genetic algorithm, slack reclamation scheduling, green scheduling and power aware scheduling. All these algorithms are used in various applications in cloud computing. They are applied in heterogeneous systems, multi-processor real-time systems, real-time embedded systems, distributed computing systems, etc. By minimizing the energy consumption, green computing technology can be enhanced and a pollution free environment will be available in future as the greenhouse gas emission is reduced.

References

1. V.A. Lepakshi, Dr. Prashanth C S R, A Study on Task Scheduling Algorithms in Cloud Computing, International Journal of Engineering and Innovative Technology (IJEIT) Volume 2, Issue 11,2013.

2. A. Beloglazov, R. Buyya, Y.C. Lee, A. Zomaya, A Taxonomy and Survey of Energy-Efficient Data Centers and Cloud Computing Systems, Advances in Computers, Volume 82, 2011, Pages 47-111.

3. F.A. Omara, M.M. Arafa, Genetic algorithms for task scheduling problem, Journal of Parallel and Distributed Computing, Volume 70, Issue 1, 2010, Pages 1322.

4. GE Junwei, Y. Yongsheng, Research of cloud computing task scheduling algorithm based on improved genetic algorithm, in: Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering, 2013.

5. N.B. Rizvandi, J. Taheri, A.Y. Zomaya, Y.C. Lee, Linear combinations of DVFS-enabled processor frequencies to modify the energy-aware scheduling algorithms, in: Proc.10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2010, pp. 388397.

6. N.B. Rizvandi, J. Taheri, A.Y. Zomaya, Some observations on optimal frequency selection in DVFS-based energy consumption minimization, Journal of Parallel and Distributed Computing 71 (8) (2011) 11541164.

7. Y.C. Lee, A.Y. Zomaya, On effective slack reclamation in task scheduling for energy reduction, Journal of Information Processing Systems 5 (4) (2009) 175186.

8. D. Zhu, R. Melhem, B.R. Childers, Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems, IEEE Transactions on Parallel and Distributed Systems 14 (7) (2003) 686700.

9. V.T.D. Truong, Y. Sato, Y. Inoguchi, Performance evaluation of a green scheduling algorithm for energy savings in cloud computing, in: Proc. 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), April 2010, pp. 18.

10. L.M. Zhang, K. Li, D.C. Lo, Y. Zhang, Energy-efficient task scheduling algorithms on heterogeneous computers with continuous and discrete speeds, Sustainable Computing: Informatics and Systems 3, 2013, 109-118.

11. L.M. Zhang, K. Li, Y. Zhang, Green task scheduling algorithms with speeds optimization on heterogeneous cloud servers, in: Proc. of 2010 IEEE/ACM International Conference on Green Computing and Communications (Green-Com2010), Hangzhou, December 1820, 2010, pp. 7680.

12. L.M. Zhang, K. Li, Y. Zhang, Green task scheduling algorithms with energy reduction on heterogeneous computers, in: Proc. of 2010 International Conference on Progress in Informatics and Computing (PIC-2010), Shanghai, December 1012, 2010, pp. 560563.

13. K. Li, Performance analysis of power-aware task scheduling algorithms on multiprocessor computers with dynamic voltage and speed, IEEE Transactions on Parallel and Distributed Systems 19 (11) (2008) 14841497.

14. L. Wang, S.U. Khan, D. Chen, J. Kolodziej, R. Ranjan,

    C. Xu, A. Zomaya, Energy-aware parallel task scheduling in a cluster, Future Generation Computer Systems, Volume 29, Issue 7, 2013, Pages 1661-1670.

15. Genetic algorithm – Wikipedia, the free encyclopedia, en.wikipedia.org/wiki/Genetic_algorithm, January 2014.

16. Genetic Algorithm Description – Introduction to Genetic Algorithms, www.obitko.com/tutorials/genetic- algorithms/ga-basic-description.php, January 2014.

17. Genetic Operations, www.ceng.metu.edu.tr/~mturhan/dfa/node6.html, January 2014.

18. A new direction for power-aware scheduling [LWN.net], https://lwn.net/Articles/570353/, January 2014.