Advanced
Minimizing Energy Consumption in Scheduling of Dependent Tasks using Genetic Algorithm in Computational Grid
Minimizing Energy Consumption in Scheduling of Dependent Tasks using Genetic Algorithm in Computational Grid
KSII Transactions on Internet and Information Systems (TIIS). 2015. Aug, 9(8): 2821-2839
Copyright © 2015, Korean Society For Internet Information
  • Received : February 13, 2015
  • Accepted : June 06, 2015
  • Published : August 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Omprakash Kaiwartya
Faculty of Computing, Universiti Teknologi Malausia (UTM), 81310 Skudai Johor, Malaysia
Shiv Prakash
Department of Chemical Engineering, Indian Institute of Technology Delhi, New Delhi-110 016, India
Abdul Hanan Abdullah
Faculty of Computing, Universiti Teknologi Malausia (UTM), 81310 Skudai Johor, Malaysia
Ahmed Nazar Hassan
Faculty of Computing, Universiti Teknologi Malausia (UTM), 81310 Skudai Johor, Malaysia

Abstract
Energy consumption by large computing systems has become an important research theme not only because the sources of energy are depleting fast but also due to the environmental concern. Computational grid is a huge distributed computing platform for the applications that require high end computing resources and consume enormous energy to facilitate execution of jobs. The organizations which are offering services for high end computation, are more cautious about energy consumption and taking utmost steps for saving energy. Therefore, this paper proposes a scheduling technique for Minimizing Energy consumption using Adapted Genetic Algorithm (MiE-AGA) for dependent tasks in Computational Grid (CG). In MiE-AGA, fitness function formulation for energy consumption has been mathematically formulated. An adapted genetic algorithm has been developed for minimizing energy consumption with appropriate modifications in each components of original genetic algorithm such as representation of chromosome, crossover, mutation and inversion operations. Pseudo code for MiE-AGA and its components has been developed with appropriate examples. MiE-AGA is simulated using Java based programs integrated with GridSim. Analysis of simulation results in terms of energy consumption, makespan and average utilization of resources clearly reveals that MiE-AGA effectively optimizes energy, makespan and average utilization of resources in CG. Comparative analysis of the optimization performance between MiE-AGA and the state-of-the-arts algorithms: EAMM, HEFT, Min-Min and Max-Min shows the effectiveness of the model.
Keywords
1. Introduction
C omputational Grid (CG) is a hardware and software infrastructure that is geographically distributed and connected via high speed communication networks which provides highly satisfactory computing resources to the grid users [1] . One of the prime goal of CG is to fulfill the different computing requirement of jobs submitted by the grid users [2] . Recently, optimizing electrical energy consumption in high end computing resources has witnessed a significant research attention which is aimed at to keep the environment green [3] . This can be attributed to the fact that it not only depletes the resources of energy but also a case of concern considering environment and cost. In order to save electrical energy in CG, tasks are migrated from lightly loaded nodes to average loaded nodes so that the lightly loaded nodes can be switched off [4] . High end computing resources requires more electrical energy and therefore, there is a tradeoff between computing power and electrical energy. From the hardware point of view, energy saving is being addressed by the researchers and it is believed that with the advancement in technology modern computing resources will offer better computational power using less amount of electrical energy. From the software point of view, the design of the software system should be energy efficient. This work deals with the design of grid scheduler to meet the energy requirement of grid efficiently. It considers dependency of tasks of a job forming a directed acyclic graph. Dependent tasks submitted to CG form a grid workflow. Generally, grid workflow has two types of schedulers; namely, global scheduler and local scheduler. Global scheduler is responsible to fulfill the requirements of the users by distributing the jobs to various nodes of the grid [5 , 6] . Local scheduler handles local scheduling policy on the nodes of grid. Workflow scheduling problem in computational grid, has been noted to be an NP-Hard problem due to various constraints involved [7] . Therefore, energy based grid workflow scheduling is of prime concern that has been addressed in this work.
Faster nodes takes lesser time for execution but they consume higher electrical energy. Therefore, in energy-aware scheduling, job allocation to a grid is done in a manner that minimizes energy consumption. It has been observed that meta-heuristic techniques are very useful for such optimization problems [8] . Therefore, this paper uses a meta-heuristic: GA to propose an energy-aware scheduling model for grid workflow. The rest of the paper is organized as follows. In section 2, related literatures are reviewed with pros and cons of each research article considered. In section 3, energy consumption in CG is mathematically formulated as an optimization problem and an adapted genetic algorithm is proposed to solve the optimization problem. In section 4, simulation and analysis of results are discussed. In section 5, conclusion and future research direction of the work is presented.
2. Related Work
Makespan, turnaround time, energy, reliability, resource availability etc. are some of the important characteristic parameters often optimized by scheduling the jobs appropriately on grid nodes. The grid scheduling problem has been extensively discussed in literature [9 - 11] . GA is often used to address the scheduling problem in grid, as the problem is NP-Hard [12 , 13] .
To study the effect of Inter Process Communication (IPC) in task scheduling, GA is used [14] . Load balancing that considers load distribution and load variation on grid nodes, using GA has been elaborated in [15 , 16] . Another important parameter, security, also finds place in many research works. Security aware scheduling using GA in CG is discussed in [17] focusing on security optimization. Availability is discussed in [18 , 19] that demonstrate the availability metric. Maximization of availability for task scheduling problem in CG using GA is suggested in [20] . Makespan minimization in CG has been discussed in [21 - 25] . Dependent task scheduling in grid computing is discussed in [26] .
The above discussed works clearly indicate that GA has been widely used for workflow scheduling in grid. This also points out that energy optimization are rarely considered for workflow scheduling in grid, which is the prime objective of the proposed work. In [27] , energy aware scheduling for independent tasks using GA is discussed. In [28] , Dynamic voltage frequency scaling (DVFS) is used which is an effective technique for processor energy reduction. It adjusts processor voltage and frequency level during runtime. In [29] , system optimization procedures constructed on dynamic reconfiguration are broadly implemented for energy conservation. DVFS techniques have been extensively studied for processor energy conservation in this paper. A general and flexible model for energy minimization based on reconfiguration dynamics in multitasking systems is proposed. In [30] scheduling problem on a single processor for a given set of jobs is discussed. Further, processor can vary its speed and hibernate to reduce energy consumption. Therefore the schedule minimizes the overall consumed energy.
In MIN-MIN scheduling, tasks are assigned based on the completion time of a grid workflow. Heterogeneous Earliest Time First (HEFT) algorithm assigns higher priority to the unallocated independent tasks in the grid workflow. Rank calculation is based on the expected time for each task and communication cost of two successive tasks. Task having maximum rank is assigned higher priority. The tasks are scheduled based on their priorities. The readers are advised to refer to the article in [31] for details of MIN-MIN, MAX-MIN and HEFT. Energy Aware Max-Min (EAMM) [32] is a variant of Max-Min which considers energy in the first phase and completion time in the second phase. In each iteration it selects the pairs (task, node) that minimizes the energy consumption for each task in phase 1 then it selects the pair that maximizes the completion time in phase 2. The aforementioned models do not consider dependency of tasks in scheduling.
3. MiE-AGA
A computation grid having M computational nodes is assumed for the problem formulation. The grid workflow scheduling problem is considered equivalent to the mapping of tasks to nodes of the grid with the objective of minimization of energy consumption. It is also assumed that all parent tasks finish their execution before the execution of the exit task. Grid users submit their jobs to the grid and each job consists of number of tasks. A queue of jobs waiting to be assigned to the nodes of the grid is considered. The length of the queue depends on the arrival and departure rate of jobs which follows Poisson distribution and execution time of task follows exponential distribution [33] . Task scheduling of a node in CG (local scheduling) follows M/M/1 model whereas Task scheduling in all nodes in CG (global scheduling) follows M/M/S model. All the tasks submitted to CG are partially dependent and parallel in nature. The average load and service rate at jth node are λj and μj respectively and μj > λj . Average waiting time at jth node using M/M/S model is given by Equation (1).
PPT Slide
Lager Image
The service average time at jth node is 1/ μj . The execution time ETCi,j for computation of ith task on jth node can be expressed as given in Equation (2).
PPT Slide
Lager Image
PPT Slide
Lager Image
Where,
PPT Slide
Lager Image
represents the number of tasks allotted to jth node, δi,j is the binary parameter and
Noli represents the number of instructions in ith task. The notations used throughout in this research article are listed in Table 1 with their purpose of usage.
Notation Table
PPT Slide
Lager Image
Notation Table
- 3.1 Fitness Function Formulation for Energy Consumption
In this section, fitness function formulation for determining energy consumption in nodes of the CG is described. Nodes of the CG are involved in execution of tasks of grid workflow. Initially all nodes of the CG are considered empty which means no tasks have been allocated to any nodes. For each task Ti a binary parameter αi is initialized. The initialization process can be expressed as given in Equation (4).
PPT Slide
Lager Image
For each tasks Ti with αi =1 , initialization of ESTi,j and ECTi,j are performed using the following two scenarios. In the first scenario, all the nodes are considered empty which means Nat [ j ]=0,∀ j ∈ {1,2,3,…, M } or Sne =∅. The initialization in the first scenarios can be expressed as given by Equation (5).
PPT Slide
Lager Image
For example, ith task is allocated to the jth node with minimum ECTi,j , thus jth node will be treated as non-empty nodes and Nat [ j ] which contains the number of allocated jobs to jth node will be incremented by 1. Subsequently, jth node will be removed from the set of empty nodes. In the second scenario, at least one node is considered non-empty which means ∃ j ∈ {1,2,3,…, M }, Nat [ j ] ≥ 1 or Sne ≠∅..The initialization in the second scenario can be expressed as given by Equation (6).
PPT Slide
Lager Image
After the above initialization, the value of Nat [ j ] is incremented or decremented and according the node j will be added to set of empty or non-empty nodes. After completion of the initialization for the ith task, set of ancestors of all the descendants of ith task is updated by removing ith task from the ancestors as given by Equation (7)
PPT Slide
Lager Image
The total execution time TETj for all allocated tasks to jth node can be computed by adding ETCi,j of all the tasks to TETj as given by Equation (7).
PPT Slide
Lager Image
For each tasks Ti with αi = 0 which means all the parents are not completed, the initialization of ESTi,j and ECTi,j are performed using the following two scenarios. In the first scenario, Nat [ j ]=0,∀ j ∈ {1,2,3,…, M } or Sne =∅ is considered and the initialization can be expressed as given by Equation (8).
PPT Slide
Lager Image
After the initialization, Nat [ j ] is incremented by 1 and jth node is removed from the set of empty nodes. In the second scenario, ∃ j ∈ {1,2,3,…, M }, Nat [ j ] ≥ 1 or Sne ≠∅ is considered and the initialization can be expressed as given by Equation (9).
PPT Slide
Lager Image
and, ECTi,j = ESTi,j + ETCi,j , ∀ Ti , αi = 1 and j ∈ {1,2,…, M }, Nat [ j ] ≥ 1
After the initialization, Nat [ j ] is incremented by 1. The latest completion time LCTj of a grid work flow at jth node can be computed as given by Equation (10).
PPT Slide
Lager Image
Makespan Mspan of the CG is the maximum LCTj of all the grid workflow being executed in different nodes. By using Equation (10), Mspan can be computed as given by Equation (11).
PPT Slide
Lager Image
Idle time
PPT Slide
Lager Image
of jth node can be computed as given by Equation (12).
PPT Slide
Lager Image
Energy Ej consumed by jth node for executing all the allocated tasks can be computed as given by Equation (13).
PPT Slide
Lager Image
Total energy TE consumed by all the nodes in the CG for executing grid workflows is given by Equation (14).
PPT Slide
Lager Image
Utilization Uj of resources at jth node can be computed as given by Equation (15).
PPT Slide
Lager Image
Average utilization AUl of all the nodes in a CG by lth solution can be expressed as given by Equation (16)
PPT Slide
Lager Image
- 3.2 Adapted Genetic Algorithm
In this section, various components of adapted genetic algorithm developed for minimizing energy consumption are described.
- 3.2.1 Representation of Chromosome
The representation of chromosome which is a potential solution of the identified problem related to energy consumption is shown in Fig. 1 .
PPT Slide
Lager Image
Representation of chromosome
where, i,j,k,l,m ∈ {1,2,3,…, M }. The above representation of chromosome shows an ordered sequence of nodes considering the dependencies of the tasks. All the tasks are allocated to the nodes of CG following the order of the sequence of the chromosome. In other words, 1 st task is allocated to Nodei , 2 nd task is allocated to Nodej , 3 rd task is allocated to Nodek and the last task is allocated to Nodem (cf. Fig. 1 ). The length of the chromosomes considering them as one dimensional arrays is equal to the total number of tasks available for allocation. The crossover and mutation operations used in MiE-AGA are described using Pseudo code and example.
- 3.2.2 Adapted Crossover
The Pseudo code of crossover operation adapted for MiE-AGA is given in Algorithm 1 . To make the process of adapted crossover more understandable, an example (cf. Fig. 2 ) is provided for readers with three computing nodes in the CG. There are two children generated from the cross over. The child 1 retains the genes from the parent 1 at the bit positions where the masking bit pattern is 1 and the genes from parent 2 where the masking bit pattern is 0. The child 2 retains the genes from the parent 1 at the bit positions where the masking bit pattern is 0 and the genes from parent 2 where the masking bit pattern is 1.
PPT Slide
Lager Image
PPT Slide
Lager Image
Adapted crossover
- 3.2.3 Adapted Mutation
The Pseudo code of mutation operation adapted for MiE-AGA is given in Algorithm 2 [34] . To make the process of adapted mutation more understandable, an example (cf. Fig. 3 ) is provided for readers with three computing nodes in the CG. Randomly selects two gens and exchange the positions in the mutated chromosome.
PPT Slide
Lager Image
PPT Slide
Lager Image
Adapted mutation
- 3.2.4 Adapted Inversion
The Pseudo code of inversion operation adapted for MiE-AGA is given in Algorithm 3 . The size of the group choosing for inversion depends on the stage of the optimization process. In initial stages, the size is generally chosen larger whereas during the last stages of optimization smaller size is preferred. To make the process of adapted inversion more understandable, an example is provided for readers with three computing nodes in the CG. The size of the group is taken 3 and the group of gens chosen for inversion is (1,2,2) in the example (cf. Fig. 4 ).
PPT Slide
Lager Image
PPT Slide
Lager Image
Adapted inversion
- 3.2.5 Pseudo code of MiE-AGA
The Pseudo code for MiE-AGA is presented in this section using the above discussed operations such as adapted crossover, mutation, and inversion. Initially, random solutions are generated for each chromosome to produce initial population used in MiE-AGA. A self-explanatory Pseudo code for MiE-AGA is given in algorithm 4 .
PPT Slide
Lager Image
4. Simulation and Analysis of Results
In this section, extensive simulation is performed to evaluate the performance of MiE-AGA. The three metrics considered for performance evaluation are; energy consumption, makespan and average utilization. The state-of-the-art algorithms used for comparative analysis are; EAMM, HEFT, Min-Min and Max-Min. Table 2
Parameter values and ranges used in Simulation
PPT Slide
Lager Image
Parameter values and ranges used in Simulation
- 4.1 Simulation Environment
The simulation is designed by writing programs in Java using Eclipse IDE and integrating them to GridSim simulator. Simulation environment uses a random generator with uniform distribution. The values of the load, processing speed, task size and communication cost are produced randomly between the given ranges. Task dependency graph also known as grid workflow is generated based on the communication cost matrix. Frequencies and voltages of nodes in CG are also randomly generated within specified range. The ranges and value of parameters used in the simulation are listed in the Table 2 . All the values generated conform to similar models for the same purpose. The simulator designed for the simulation has ten classes; namely, random_generator.java, selection.java, crossover.java, mutation.java, inversion.java, calculate_parameters.java, sort.java, global_scheduler.java, local_scheduler.java and Main.java. The simulation is performed in a SUN FIRE X4470 Server @ 4 Intel Xeon μP 7500 Series with up to 512 GB of memory and over 1.8 TB of internal storage. The system is equipped with Sun Studio software with Open MP and MPI programming models. The simulations are classified into three categories small (3 to 64 nodes and 10 to 128 tasks), medium (65 to 128 nodes and 128 to 256 tasks) and large (129 to 188 nodes and 256 to 512 tasks) grid.
- 4.2 Analysis of Results with Small Grid Workflow
In this section, the optimization performance of MiE-AGA is analyzed.
Result in Fig. 5 shows the optimization of energy consumption of nodes in case of MiE-AGA with increasing number of generations. It can be clearly observed that energy consumption of nodes in the CG decreases with increasing number of generations up to around 251 generations. The optimization converges completely reaching to 500 generations and minimum consumed energy is approximately 1551870 J . This can be attributed to the fact that MiE-AGA considers energy consumption of nodes while scheduling of tasks in CG. Result in Fig. 6 shows the optimization of Makespan of CG in case of MiE-AGA with increasing number of generations. It can be clearly observed that makespan of nodes in the CG decreases with increasing number of generations up to around 500 generations. The optimization converges completely reaching to above 500 generations and minimum makespan is approximately 98994 s . This can be attributed to the fact that MiE-AGA considers dependency of task while scheduling of tasks in CG.
PPT Slide
Lager Image
Optimization of energy consumption in case of MiE-AGA with 128 tasks and 8 nodes
PPT Slide
Lager Image
Optimization of makespan in case of MiE-AGA with 128 tasks and 8 nodes
Results in Table 3 show the comparison of energy consumption of nodes between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower energy consumption as compared to the state-of-the-arts techniques for each of the number of nodes considered in the results. This is due to the consideration of energy consumption while scheduling of tasks in case of MiE-AGA .Additionally, it is also noteworthy that energy consumption of nodes increases with increasing number of nodes in CG for each of the algorithms considered but the increment in energy consumption is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of energy consumption in joule (J) with 128 tasks
PPT Slide
Lager Image
Comparison of energy consumption in joule (J) with 128 tasks
Results in Table 4 show the comparison of makespan of CG between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower makespan as compared to the state-of-the-arts algorithms for each of the number of nodes considered in the results. This is due to the consideration of dependency of tasks while scheduling of tasks in case of MiE-AGA. Additionally, it is also noteworthy that makespan of CG increases with increasing number of nodes in CG for each of the algorithms considered but the increment in makespan is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of makespan in second (s) with 128 tasks
PPT Slide
Lager Image
Comparison of makespan in second (s) with 128 tasks
Results in Table 5 show the average utilization in case of MiE-AGA for 128 and 256 tasks with increasing number of nodes in CG. It can be clearly observed that average utilization decreases with increasing number of nodes in CG and increases with increasing number of tasks in CG. This can be attributed to the fact that MiE-AGA considers utilization of nodes while scheduling of tasks in CG.
Average utilization in case of MiE-AGA
PPT Slide
Lager Image
Average utilization in case of MiE-AGA
- 4.3 Analysis of Results with Medium Grid Workflow
Experiment has been performed for the medium grid workflow with various possibilities.
Next experiment takes the observation on energy and makespan considering 72 nodes and 256 tasks. Results are shown in Fig. 7 and Fig. 8 .
PPT Slide
Lager Image
Optimization of energy consumption in case of MiE-AGA with 256 tasks and 72 nodes
PPT Slide
Lager Image
Optimization of makespan in case of MiE-AGA with 256 tasks and 72 nodes
Result in Fig. 7 shows the optimization of energy consumption of nodes in case of MiE-AGA with increasing number of generations. It can be clearly observed that energy consumption of nodes in the CG decreases with increasing number of generations up to around 1900 generations. The optimization converges completely reaching to 2000 generations and minimum consumed energy is approximately MiE-AGA is 9707300 J . This can be attributed to the fact that MiE-AGA considers energy consumption of nodes while scheduling of tasks in CG. Fig. 8 shows the optimization of Makespan of CG in case of MiE-AGA with increasing number of generations. It can be clearly observed that makespan of nodes in the CG decreases with increasing number of generations up to around 1950 generations. The optimization converges completely reaching to above 2000 generations and minimum makespan with proposed MiE-AGA is 99134.3 s. This can be attributed to the fact that MiE-AGA considers dependency of task while scheduling of tasks in CG.
A comparative study, of the proposed model with other models, has been performed to observe energy. Results in Table 6 show the comparison of energy consumption of nodes between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower energy consumption as compared to the state-of-the-arts techniques for each of the number of nodes considered in the results. This is due to the consideration of energy consumption while scheduling of tasks in case of MiE-AGA .Additionally, it is also noteworthy that energy consumption of nodes increases with increasing number of nodes in CG for each of the algorithms considered but the increment in energy consumption is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of energy consumption in joule (J) with 256 tasks
PPT Slide
Lager Image
Comparison of energy consumption in joule (J) with 256 tasks
From Table 7 , it is observed that when number of nodes increases, makespan decreases. The proposed MiE-AGA is performing better than other models. Results in Table 7 show the comparison of makespan of CG between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower makespan as compared to the state-of-the-arts algorithms for each of the number of nodes considered in the results. This is due to the consideration of dependency of tasks while scheduling of tasks in case of MiE-AGA. Additionally, it is also noteworthy that makespan of CG increases with increasing number of nodes in CG for each of the algorithms considered but the increment in makespan is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of makespan in second (s) with 256 tasks
PPT Slide
Lager Image
Comparison of makespan in second (s) with 256 tasks
Results in Table 8 show the average utilization in case of MiE-AGA for 128 and 256 tasks with increasing number of nodes in CG. It can be clearly observed that average utilization decreases with increasing number of nodes in CG and increases with increasing number of tasks in CG. This can be attributed to the fact that MiE-AGA considers utilization of nodes while scheduling of tasks in CG.
Average utilization in case of MiE-AGA with 256 tasks
PPT Slide
Lager Image
Average utilization in case of MiE-AGA with 256 tasks
- 4.4 Analysis of Results with Large Grid Workflow
For the large grid workflow, experiment has been performed with various possibilities.
This experiment takes the observation on energy and makespan. Makespan is obtained considering 180 nodes and 512 tasks whereas energy is obtained considering 136 nodes and 512 tasks. It is because; on less number of nodes energy was not quite observable. Results are shown in Fig. 9 and Fig. 10 .
PPT Slide
Lager Image
Optimization of energy consumption in case of MiE-AGA with 512 tasks and 136 nodes
PPT Slide
Lager Image
Optimization of makespan in case of MiE-AGA with 512 tasks and 136 nodes
Result in Fig. 9 shows the optimization of energy consumption of nodes in case of MiE-AGA with increasing number of generations. It can be clearly observed that energy consumption of nodes in the CG decreases with increasing number of generations up to around 4951 generations. The optimization converges completely reaching to 5000 generations and minimum consumed energy is approximately using MiE-AGA is 25517663 J . This can be attributed to the fact that MiE-AGA considers energy consumption of nodes while scheduling of tasks in CG. Result in Fig. 10 shows the optimization of Makespan of CG in case of MiE-AGA with increasing number of generations. It can be clearly observed that makespan of nodes in the CG decreases with increasing number of generations up to around 4950 generations. The optimization converges completely reaching to above 5000 generations and minimum makespan using MiE-AGA is 125925.90 s . This can be attributed to the fact that MiE-AGA considers dependency of task while scheduling of tasks in CG.
From Table 9 it is clear that energy increased when number of nodes increased. Again, MiE-AGA is performing better than other models. A comparative study, of the proposed model with other models, has been performed to observe energy. Results in Table 9 show the comparison of energy consumption of nodes between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower energy consumption as compared to the state-of-the-arts techniques for each of the number of nodes considered in the results. This is due to the consideration of energy consumption while scheduling of tasks in case of MiE-AGA .Additionally, it is also noteworthy that energy consumption of nodes increases with increasing number of nodes in CG for each of the algorithms considered but the increment in energy consumption is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of energy consumption in joule (J) with 512 tasks
PPT Slide
Lager Image
Comparison of energy consumption in joule (J) with 512 tasks
A Comparative study, of the proposed model with other models, has been performed to observe the makespan using 136 nodes to 172 nodes and 512 tasks. Results in Table 10 show the comparison of makespan of CG between MiE-AGA and state-of-the-arts algorithms. The comparative analysis clearly shows that MiE-AGA has lower makespan as compared to the state-of-the-arts algorithms for each of the number of nodes considered in the results. This is due to the consideration of dependency of tasks while scheduling of tasks in case of MiE-AGA. Additionally, it is also noteworthy that makespan of CG increases with increasing number of nodes in CG for each of the algorithms considered but the increment in makespan is smaller in case of MiE-AGA as compared to the state-of-the-arts algorithms.
Comparison of makespan in second (s) with 512 tasks
PPT Slide
Lager Image
Comparison of makespan in second (s) with 512 tasks
Results in Table 11 show the average utilization in case of MiE-AGA for 128 and 256 tasks with increasing number of nodes in CG. It can be clearly observed that average utilization decreases with increasing number of nodes in CG and increases with increasing number of tasks in CG. This can be attributed to the fact that MiE-AGA considers utilization of nodes while scheduling of tasks in CG.
Average utilization in case of MiE-AGA with 512 tasks
PPT Slide
Lager Image
Average utilization in case of MiE-AGA with 512 tasks
5. Conclusion and Future Work
In this paper, a scheduling technique for Minimizing Energy consumption using Adapted Genetic Algorithm (MiE-AGA) for dependent tasks in computational grid has been proposed and simulated in Java based programs integrated with GridSim. From the analysis of simulation results obtained with small, medium and large scal grid, following conclusions have been made. MiE-AGA effectively minimizes energy consumption and makespan with increasing number of generations. Energy consumption converges with 300, 2000 and 5000 generations for small, medium and large scale grid respectively. Makespan converges with 500, 1300, 5000 generations for small, medium and large scale grid respectively. Average resource utilization increases with increasing number of tasks and decreases with increasing number of nodes. The minimum energy consumption observed are 1551870 J , 9707300 J and 25517663 J for small, medium and large scale grid respectively. The minimum makespan observed are 99134.3 s , 125925.90 s and 98994 s for small, medium and large scale grid respectively. Energy consumption and makespan of MiE-AGA are lower as compared to the state-of-the-arts algorithms for all the scales of the grid considered. In future research, authors will explore multi-objective meta-heuristics techniques for energy consumption with other QoS parameter optimization.
- Conflict of Interest
The authors declare that there is no conflict of interests regarding the publication of this paper.
- Authors’ Contribution
Omprakash Kaiwartya and Shiv Prakash conceived designed and experimental study of the work. The paper is written by Omprakash Kaiwartya with the help of Shiv Prakash and Ahmed Nazar Hassan. The written English of the paper has been improved by Abdul Hanan Abdulla.
Acknowledgements
The research is supported by Ministry of Education Malaysia (MOE) and conducted in collaboration with Research Management Center (RMC) at University Teknologi Malaysia (UTM) under VOT NUMBER: Q.J130000.2528.06H00.
BIO
Omprakash Kaiwartya received his M.Tech and PhD in Computer Science from School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India in 2012 and 2015. He is currently working as a Post-Doctoral Faculty at Universiti Teknologi Malaysia (UTM). His research interests include VANETs, MANETs, WSNs and Computing. He has published papers in reputed Journals and Conferences including ACM, IEEE, Springer, MDPI, Inderscience and Hindawi.
Shiv Prakash received his M.Tech and PhD in Computer Science from School of Computer and System Sciences, Jawaharlal Nehru University, New Delhi, India in 2010 and 2014. He is a member of the IEEE and ACM. His research interest includes parallel/distributed system, grid computing, cloud Computing, Machine Learning. He has published around papers in various international journals and peer-reviewed Conferences including IEEE, Springer, Wiley & Sons and Inderscience.
Abdul Hanan Abdullah received his Ph.D. degree from Aston University in Birmingham, United Kingdom in 1995. He is currently working as a Professor at Universiti Teknologi Malaysia (UTM). He was the dean at the Faculty of Computing, UTM from 2004 to 2011. Currently he is heading Pervasive Computing Research Group, a research group under K-Economy Research Alliances. Prof. Abdullah has published papers in reputed Journals and Conferences including IEEE, Elsevier, Wiley & Sons, Springer, MDPI and Hindawi.
Ahmed Nazar Hassan is currently a Ph.D. research scholar at Faculty of Computing Universiti Teknologi Malaysia(UTM), Skudai Johor, Malaysia. His research interest includes VANETs, MANETs, WSNs and Computing. He has published papers in reputed Journals including MDPI and Hindawi.
References
Foster I. , Kesselman C. 2004 "Grid 2: Blueprint for a new computing infrastructure,” Morgan Kaufmann, An Imprint of Elsevier
Berman F. , Hey A.J.G. , Fox G.C. 2003 “Grid computing: Making the global infrastructure a reality,” John Wiley and Sons
Nesmachnow S. , Dorronsoro B. , Pecero J. , Bouvry P. 2013 “Energy-aware scheduling on multicore heterogeneous grid computing systems,” Journal of Grid Computing 11 (4) 653 - 680    DOI : 10.1007/s10723-013-9258-3
Wang W. , Ranka S. , Mishra P. 2012 “Energy-aware dynamic slack allocation for real-time multitasking systems,” Sustainable Computing: Informatics and Systems 2 (3) 128 - 137    DOI : 10.1016/j.suscom.2012.04.001
Buyya R. , Murshed M. 2002 “GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing,” Concurrency Computation: Practice and Experience 14 (13-15) 1175 - 1220    DOI : 10.1002/cpe.710
Ding D. , Luo S. , Gao Z. 2010 “A matrix scheduling strategy with multi QoS constraints in grid,” Lecture Notes in Computer Science 6104 59 - 68
Garey M.R. , Johnson D.S. 1990 “Computers and intractability: A guide to the theory of NP-completeness,” W.H. Freeman and Co.
Kashyap R. , Vidyarthi D.P. 2013 “Security driven scheduling model for computational grid using NSGA II,” Journal of Grid Computing 11 (4) 721 - 734    DOI : 10.1007/s10723-013-9251-x
Prakash S. , Vidyarthi D.P. 2013 “A novel scheduling model for computational grid using quantum genetic algorithm,” Journal of Supercomputing 65 (4) 745 - 764
Parsa S. , Entezari-Maleki R. 2012 “Task dispatching approach to reduce the number of waiting tasks in grid environments,” Journal of Supercomputing 59 (1) 469 - 484    DOI : 10.1007/s11227-010-0448-5
Rajni A. , Chana I. 2012 Formal “QoS policy based grid resource provisioning framework,” Journal of Grid Computing 10 (2) 249 - 264    DOI : 10.1007/s10723-012-9202-y
Xhafa F. , Abraham A. 2010 “Computational models and heuristic methods for grid scheduling problems,” Future Generation Computer System 26 (4) 608 - 621    DOI : 10.1016/j.future.2009.11.005
Chen W.N. , Zhang J. 2009 “An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem with various QoS Requirements,” IEEE Transaction on Systems, Man, and Cybernetics-Part C: Applications and Reviews 39 (1) 29 - 43    DOI : 10.1109/TSMCC.2008.2001722
Prakash S. , Vidyarthi D.P. 2012 “Observations on effect of IPC in GA based scheduling on computational grid,” Int. J. of Grid and High Performance Computing 4 (1) 67 - 80    DOI : 10.4018/jghpc.2012010105
Prakash S. , Vidyarthi D.P. 2011 “Load balancing in computational grid using genetic algorithm,” International Journal of Advances in Computer 1 (1) 8 - 17
Subrata R. , Zomaya A. Y. , Landfeldt B. 2007 “Artificial life techniques for load balancing in computational grids,” J. of Com. and Sys. Sci. 73 (8) 1176 - 1190    DOI : 10.1016/j.jcss.2007.02.006
Kashyap R. , Vidyarthi D.P. 2012 “Security-aware scheduling model for computational grid,” Concurrency Computation: Practice and Experience 24 (12) 1377 - 1391    DOI : 10.1002/cpe.1850
Koren I. , Krishna C.M. 2007 “Fault-tolerant System,” Morgan Kaufmann an imprint of Elsevier
Allenotor D. , Thulasiram R.K. 2013 “A fuzzy grid-QoS framework for obtaining higher grid resources availability,” Journal of Supercomputing 66 (3) 1231 - 1242    DOI : 10.1007/s11227-011-0728-8
Prakash S. , Vidyarthi D.P. 2015 “Maximizing availability for task scheduling in computational grid using GA,” Concurrency Computation: Practice and Experience 27 (1) 197 - 210    DOI : 10.1002/cpe.3216
Singh Susmita , Sarkar Madhulina , Roy Sarbani , Mukherjee Nandini 2013 “Genetic Algorithm based Resource Broker for Computational Grid,” Procedia Technology 10 (1) 572 - 580    DOI : 10.1016/j.protcy.2013.12.397
Carretero J. , Xhafa F. , Barolli L. , Durresi A. 2007 “Immediate mode scheduling in grid systems,” Journal of Web and Grid Services 3 (2) 219 - 236    DOI : 10.1504/IJWGS.2007.014075
Xhafa F. , Kolodziej J. , Barolli L. , Kolici V. , Miho R. , Takizawa M. 2012 “Hybrid algorithms for independent batch scheduling in grids,” Journal of Web and Grid Services 8 (2) 134 - 152    DOI : 10.1504/IJWGS.2012.048402
Prakash S. , Vidyarthi D.P. 2014 “Immune Genetic Algorithm for Scheduling in Computational Grid,” Journal of Bio-Inspired Computing 6 (6) 397 - 408    DOI : 10.1504/IJBIC.2014.066970
Prakash S. , Vidyarthi D. P. 2014 “A Hybrid GABFO Approach for Scheduling in Computational Grid,” Int. Journal of Applied Evolutionary Computation 5 (3) 57 - 83    DOI : 10.4018/ijaec.2014070104
Meddeber M. , Yagoubi B. 2011 “Tasks assignment for Grid computing,” Journal of Web and Grid Services 7 (4) 427 - 443    DOI : 10.1504/IJWGS.2011.044697
Kolodziej J. , Khan S. U. , Wang L. , Chen D. , Zomaya A. Y. 2013 “Energy and Security Awareness in Evolutionary-driven Grid Scheduling,”Evolutionary based Solutions for Green Computing
Xhafa F. , Abraham A. 2008 “Metaheuristics for scheduling in distributed computing environments studies,”computational intelligence Springer 146 1 - 37
Wang W. , Ranka S. , Mishra P. 2011 “Energy-aware dynamic reconfiguration algorithms for real-time multitasking systems,” Sustainable Computing: Informatics and Systems 1 (1) 35 - 45    DOI : 10.1016/j.suscom.2010.10.006
Bampis E. , Dürra C. , Kacem F. , Mills I. 2012 “Speed scaling with power down scheduling for agreeable deadlines, systems,” Sustainable Computing: Informatics and Systems 2 (4) 184 - 189    DOI : 10.1016/j.suscom.2012.10.003
Braun T.D. , Sigel H.J. , Beck N. 2001 “A comparison of eleven static heuristic for mapping a class of independent tasks onto heterogeneous distributed computing systems,” Journal Parallel and Distributed Computing 61 (6) 810 - 837    DOI : 10.1006/jpdc.2000.1714
Shi Z. , Dongarra J. 2006 “Scheduling workflow applications on processors with different capabilities,” Future Generation Computer System 22 (6) 665 - 675    DOI : 10.1016/j.future.2005.11.002
Levy Y. 1981 “Introduction to queueing theory,” Networks Elsevier North Holland 13 (1) 155 - 156    DOI : 10.1002/net.3230130112
Goldberg D.E. 2005 “Genetic algorithms in search optimization and machine learning,” 3rd edition Pearson Education India