Downloaded 261 times
![ [1] Kaur, P.D., Chana, I. ―Unfolding the distributed computing paradigm‖ ,In: International Conference on Advances in Computer Engineering, pp. 339-342 (2010) [2] Mei, L., Chan, W.K., Tse, T.H., ―A Tale of Clouds: Paradigm Comparisons and Some Thoughts on Research Issues‖, In: APSCC 2008, pp. 464-469 (2008) [3] Silva, J.N., Veiga, L., Ferreira, P.: ―Heuristics for Resource Allocation on Utility Computating Infrastructures. In: 6th International Workshop on Middleware for Grid Computing, New York (2008) [4] Mell, P., Grance, T., ―The NIST Definition of Cloud Computing‖, Version 15, 10-7-09. National Institute of Standard and Technology, Information technology Laboratory (2009) 34](https://image.slidesharecdn.com/g-160801065227/75/Genetic-Algorithm-for-task-scheduling-in-Cloud-Computing-Environment-34-2048.jpg)
Uploaded bySwapnil Shahade
Genetic Algorithm for task scheduling in Cloud Computing Environment
This document proposes a modified genetic algorithm to schedule tasks in cloud computing environments. It begins with an introduction and background on cloud computing and task scheduling. It then describes the standard genetic algorithm approach and introduces the modified genetic algorithm which uses Longest Cloudlet to Fastest Processor and Smallest Cloudlet to Fastest Processor scheduling algorithms to generate the initial population. The implementation and results show that the modified genetic algorithm reduces makespan and cost compared to the standard genetic algorithm.
In this document
Powered by AI
Presented by Swapnil S. Shahade, guided by Mrs. Rupali Gangarde. Contains introduction and the outline of the presentation.
Explains cloud computing concepts, including types of services (IaaS, PaaS, SaaS), and the cloud ecosystem which includes consumers, providers, and services.
Discusses areas for improvement in cloud technology, especially on resource management and task scheduling. Lists existing scheduling algorithms and their limitations.
Introduces a Genetic Algorithm (GA) approach for task scheduling to minimize execution time and cost, describing its process and benefits.
Details the Modified Genetic Algorithm (MGA), which combines approaches to optimize cloud task scheduling, including population and fitness evaluation.
Describes the methodologies of Longest Cloudlet to Fastest Processor (LCFP) and Smallest Cloudlet to Fastest Processor (SCFP) algorithms for task allocation.
Explains the importance of crossover and mutation in genetic algorithms, and evaluation based on execution time and cost minimization.
Details the implementation specs, testing conditions, and goals for the proposed scheduling algorithms on specified hardware.
Presents experimental findings on the performance of MGA versus SGA in terms of make-span and execution costs, demonstrating MGA's efficiency.
Lists scholarly references related to cloud computing and task scheduling algorithms.
A concluding slide with no content, intended for the ending of the presentation.
Genetic Algorithm for task scheduling in Cloud Computing Environment
- 1. BY SWAPNIL S. SHAHADE 1 GuidedBy Mrs. RUPALI GANGARDE
- 2. 1.Introduction 2.Related Works 3.Problem Formulation 4.AlgorithmDescription 5. Implementation & Results 6. Conclusion 2
- 3. A cloudis a type of parallel and distributed system. A collection of interconnected and virtualized computer that are dynamically presented as one or more unified computing resources based on service level agreements established through negotiation between the service providers and consumers. 3
- 4. It providesvirtual resources that are dynamically scalable It describes virtualized resources, software, platforms, applications, computations and storage to be scalable and provided to users instantly on payment for only what they use. Cloud ecosystem comprises of three main entities: Cloud consumers Cloud service providers Cloud services. 4
- 5. It providesthree service models which are- Cloud Infrastructure as a Service (IaaS), Cloud Platform as Service (PaaS) and Cloud Software as a Service (SaaS). Cloud IaaS provides consumer the processing, storage, networks and other fundamental computing resources where the consumer is able to run arbitrary software, which can include operating system and applications. 5
- 6. Cloud PaaSservice facilitate developers with provider specific programming language and tools to develop the applications. Cloud SaaS provides the capability to users to use the provider’s application running on cloud infrastructures. Google Apps is an example of SaaS. 6
- 7. Fig. 1: ServiceModels 7 Cloud computing Server Desktop Tablet Laptop Phones
- 8. Cloud technologyis still not developed. There are some areas that are needed to be focused on. 1.Resource management 2.Task scheduling 8
- 9. In 2008,A heuristic method to schedule bag-of-tasks (tasks with short execution time and no dependencies) in a cloud is presented in so that the number of virtual machines to execute all the tasks within the budget, is minimum and the same time speed up. 9
- 10. There aremany algorithms like Min-Min, Max-Min, Suffrage, Shortest Cloudlet to Fastest Processor (SCFP), Longest Cloudlet to Fastest Processor (LCFP) and some meta-heuristics like Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant-Colony Optimization (ACO) and Simulated Annealing (SA) already existing for task scheduling. 10
- 11. There areso many algorithms are given by various researchers for clouds, But, none of the above existing algorithms have considered the -Computational complexity(job length, processing power) - Computing cost(processor cost) The two task Scheduling algorithms of Cloud LCFP & SCFP takes the computational complexity and processing power of resource into consideration. 11
- 12. Our mainpurpose is to schedule tasks which involves finding out a proper sequence in which all the tasks can be executed such that execution time and execution cost can be minimized. A Genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. Inspired by natural evolution, such as inheritance, mutation, selection, and crossover. 12
- 13. Those individualsmost successful in each 'competition' will produce offspring than those individuals that perform poorly. Genes from `good' individuals propagate throughout the population so that two good parents will sometimes produce offspring that are better than either parent. Time minimization will give profit to service provider and less maintenance cost to the resources. It will also provide benefit to cloud’s service users as their application will be executed at reduced cost. 13
- 14. Standard GeneticAlgorithm (SGA) 1.Produce an initial population by randomly generated individuals 2.Evaluate the fitness of all individuals 3.while termination condition not met do - select fitter individuals for reproduction - crossover between individuals - mutate individuals - evaluate the fitness of the modified individuals - Generate a new population 4. End while 14
- 15.
- 16.
- 17. Modified GeneticAlgorithm (MGA) Step1 :- Generate an initial population of individuals with output schedules of algorithms Longest Cloudlet to Fastest Processor (LCFP), Smallest Cloudlet to Fastest Processor (SCFP) and Random Schedules. Step2 :- Evaluate the fitness of all individuals Step3 :- While termination condition not met do 17
- 18.
- 19. We havemerged LCFP and SCFP to generate the initial population of meta-heuristic which encode candidate solutions to an optimization problem, evolves toward better solutions. 19
- 20.
- 21. A) LCFP (LongestCloudlet to Fastest Processor) 1. Sort the cloudlets in descending order of length. 2. Sort the processors in descending order of processing power. 3. Map the cloudlets from sorted list to the sorted list of processors on one-to-one mapping basis. 21
- 22. B) SCFP (SmallestCloudlet to Fastest Processor) 1. Sort the cloudlets in ascending order of length. 2. Sort the processors in descending order of processing power. 3. Map the jobs from sorted list to the sorted list of processors on one-to-one mapping basis. 22
- 23. The crossoveroperators are the most important ingredient of any evolutionary-like algorithm. Indeed, by selecting individuals from the parental generation and interchanging their genes, new individuals (descendants) are obtained. The aim is to obtain descendants of better quality that will feed the next generation and enable the search to explore new regions of solution space not explored yet. 23
- 24.
- 25. There are severalmutation operators based on the permutation based representation of the schedule like Move, Swap, Move & Swap and Rebalancing. 25 Evaluation Evaluation is based on the execution time and execution cost. Those schedules will be selected for next generation whose makespan( execution time of all cloudlets) and execution cost is less than thestandard genetic algorithm (SGA)
- 26. The twoalgorithms are implemented on Intel core i5 machine with 500 GB HDD and 4 GB RAM on Windows 7 OS, Eclipse with Java version 1.6, with the help of JGAP (Java based Genetic Algorithm Package) 1. Standard Genetic Algorithm (SGA) 2. Modified Genetic Algorithm (MGA) 26
- 27. A goodscheduling algorithm is that which leads to better resource utilization, less average Make-span and better system throughput. Make-span refers to the completion time of all cloudlets in the list. To formulate the problem we considered cloudlets ( C1, C2,C3…..Cn) run on processors (P1, P2, P3…..Pn). The speed of processors is expressed in MIPS (Million instructions per second) and length of job can be expressed as number of instructions to be executed. 27
- 28. All thealgorithms are tested by -Varying the number of cloudlets. -Randomly varying the length of cloudlets. Experimental results show that under heavy loads our proposed algorithm that is modified Genetic Algorithm exhibits a very good performance. 28
- 29. The figureshows the Makespan refers to execution time calculated in seconds of all cloudlets in each of two algorithms. Experimental resulting values show that our proposed algorithm takes less execution time as compared to existing SGA which is based on the random generation of schedules. 29
- 30. 0 100 200 300 400 500 600 10 15 2025 30 SGA MGA 30 MAKESPAN Number of Cloudlets
- 31. 0 2000 4000 6000 8000 10000 12000 10 15 2025 30 SGA MGA 31 Cost(Rs)
- 32. Above figurecompared the execution cost of two algorithms. Resulting values show that performance of proposed algorithm is better than the existing algorithm and keep on increasing with increase in workloads. 32
- 33. Experimental resultsshow that, under the heavy loads, the proposed algorithm exhibits a good performance. 33
- 34. [1] Kaur,P.D., Chana, I. ―Unfolding the distributed computing paradigm‖ ,In: International Conference on Advances in Computer Engineering, pp. 339-342 (2010) [2] Mei, L., Chan, W.K., Tse, T.H., ―A Tale of Clouds: Paradigm Comparisons and Some Thoughts on Research Issues‖, In: APSCC 2008, pp. 464-469 (2008) [3] Silva, J.N., Veiga, L., Ferreira, P.: ―Heuristics for Resource Allocation on Utility Computating Infrastructures. In: 6th International Workshop on Middleware for Grid Computing, New York (2008) [4] Mell, P., Grance, T., ―The NIST Definition of Cloud Computing‖, Version 15, 10-7-09. National Institute of Standard and Technology, Information technology Laboratory (2009) 34
- 35.