Word Files
Reference for Downloading Educational Files
  2. Computer Engineering
  3. Presenting an efficient scheduling algorithm in grid computing network with the aim of reducing total completion time and load balancing

Presenting an efficient scheduling algorithm in grid computing network with the aim of reducing total completion time and load balancing

Number of pages: 73 File Format: word File Code: 31013
Year: 2013 University Degree: Master's degree Category: Computer Engineering
Tags/Keywords: Algorithm - Computational grade - Computing networks - Efficient scheduling algorithm - Evolutionary algorithms - Genetic algorithm - Grid computing network - Scheduling algorithm
  • Part of the Content
  • Contents & Resources

  • Summary of Presenting an efficient scheduling algorithm in grid computing network with the aim of reducing total completion time and load balancing

    Master's thesis in the field of

    Computer Engineering (Software)

    Abstract

    Torino computing networks (GRID) have provided a context in which heterogeneous resources in different geographic locations can be used to solve complex scientific, engineering and business problems. Timing operation plays a key role in grid performance. In this thesis, using the advantages of genetic algorithm, five scheduling algorithms are presented for optimal mapping of manual tasks on machines, which examines the entire search space of the scheduling problem and creates a load balance on all machines. The results of the implementation of the presented algorithms show an average reduction of 13.23% in the completion time of the last task compared to the previous algorithms.

    Keywords: computing grid, scheduling, load balancing.

    1-1 Introduction

    Today's computers, like the human brain, usually use a small part of their capabilities and are often inactive and waiting for input information. they stay Imagine what a powerful device we would have if the hardware resources of all these inactive computers were used and all gathered into one computer. Computing networks (Grid) [1] have provided a basis to use the (computer) resources of other systems as well. Most of the complex scientific, engineering and business problems require a large amount of resources to be implemented, the best solution for such problems is to use the grid [1]. Users continuously send their requests to the grid environment, and the resource management department [2] assigns these tasks to the computing nodes [3] in the network. How to allocate these requests on different computing nodes is called scheduling[4].

    The application of different policies for scheduling operations will have different results, which policies are adopted according to the goals specified for the grid. Scheduling operations in different policies use different factors to allocate tasks on different resources. It is possible that a factor has a determining role in one of the policies, but it is not considered at all in the other policy, therefore, the goal of each algorithm is to optimize the desired policy.

    1-2 Objectives of the thesis

    Given the high impact of the scheduling operation in the optimal performance of the grid and the advantages that were mentioned for the grid in the previous section, providing an efficient scheduling method can have a great impact in solving major problems in different branches.

    In computing grades, the goal is to increase the percentage of resource usage while reducing the time to complete the last task. In this research plan, we are pursuing the same goals and we are trying to provide a mapping of tasks that will increase the productivity of resources and have the least amount of time to complete the last task. 1-3 stages of completing the thesis To complete the thesis, first the concepts of grades and existing methods were studied and reviewed, and after the comparison of different methods, the genetic algorithm was chosen to produce the mapping. In addition to the genetic algorithm, we presented an algorithm that helps to balance the load on the resources, and using the advantages of the two mentioned algorithms, we obtained the optimal mapping for the tasks. Java programming language is used to implement the algorithms.

    1-4 thesis structure

    In the second chapter of the genetic algorithm, the parameters effective in this algorithm and the basic concepts of scheduling are examined. In the third chapter, we will review previous research. The proposed algorithms are presented in the fourth chapter, and in the fifth chapter, the results of the evaluation and comparison of the proposed algorithms are given. 2- Thematic literature 2-1 Introduction In this chapter, we first examine the genetic algorithm. In this review, we specify the general structure of the genetic algorithm and the parameters affecting the performance of this algorithm. In the following, we will describe the Grid computing network environment and examine the available terms and definitions. We explain the different scheduling methods and examine the types of work queues.

    Genetic algorithm, an inspiration from genetic science and evolution theory.

    The genetic algorithm is inspired by genetics and Darwin's theory of evolution and is based on survival of the fittest or natural selection. A common application of genetic algorithm is to use it as an optimizing function. Genetic algorithm is a useful tool in pattern recognition, feature selection, image understanding and machine learning [3-8]. In the genetic algorithm [5], the genetic evolution of living organisms is simulated.

    Although work was done by a biologist named Fraser in the field of modeling evolution in biological systems in the 60s, the genetic algorithm for engineering applications and in its current form was first proposed by John Holland [9], a computer science specialist at the University of Michigan in 1975. His work is the beginning of all efforts to use genetic algorithm in engineering. After that, the works of Dejong [10] in 1975 in the field of review and comparison of several genetic algorithm methods provided the theoretical foundations of the discussion. This algorithm, inspired by nature, is based on the evolutionary principle of "sustainability of the best" [6]. Although the genetic algorithm was proposed after the evolutionary strategy algorithm, it is the most famous method among the evolutionary algorithms. In a genetic algorithm, a population of people survives according to their desirability in the environment. People with superior capabilities will find more chances of marriage and reproduction. Therefore, after a few generations, children with better performance are born. In the genetic algorithm, each person from the population is introduced as a chromosome. Chromosomes become more complete over several generations. In each generation, chromosomes are evaluated and they are allowed to survive and reproduce according to their value. Gene generation in the discussion of genetic algorithm is done with mating 3 and mutation 4 operators. The best parents are selected based on a fitness function.

    In each step of the genetic algorithm execution, a group of search space points are randomly processed. In this way, a sequence of characters is attributed to each point and genetic operators are applied to these sequences. Then the obtained sequences are decoded to obtain new points in the search space. Finally, based on the value of the objective function at each of the points, the probability of their participation in the next stage is determined [11-14]. Genetic algorithm can be considered a directional random optimization method that gradually moves towards the optimal point. Regarding the characteristics of the genetic algorithm compared to other optimization methods, it can be said that it is an algorithm that can be applied to any problem without having any knowledge of the problem and any restrictions on the type of variables, and it has a proven efficiency in finding the overall optimum [7]. The ability of this method is to solve complex optimization problems that classical methods are not applicable or reliable to find the general optimum [15].

    2-2 Structure of genetic algorithm

    Generally, genetic algorithm consists of the following components:

    chromosome[8]

    In genetic algorithm, each chromosome represents a point in the search space and a possible solution. for the problem in question. The chromosomes themselves (solutions) consist of a fixed number of genes [9] (variable). Binary encodings (bit strings) are usually used to represent chromosomes.

    Population[10]

    A set of chromosomes form a population. With the effect of genetic operators on each population, a new population with the same number of chromosomes is formed. Fitness function[11] In order to solve any problem using genetic algorithms, a fitness function must first be devised for that problem. For each chromosome, this function returns a non-negative number that indicates the individual competence or ability of that chromosome.

    Genetic operators

    In the genetic algorithm, genetic operators are used during the reproduction stage[12]. With the effect of these operators on a population, the next generation [13] of that population is produced. Selection, mating, and mutation operators are usually the most used in genetic algorithms. 2-3 genetic operators In the previous section, it was mentioned that selection, mating, and mutation operators are usually used in genetic algorithms for reproduction. In this section, each of the above operators is introduced separately:

    Selection operator

    This operator selects a number of chromosomes for reproduction among the chromosomes in a population.

  • Contents & References of Presenting an efficient scheduling algorithm in grid computing network with the aim of reducing total completion time and load balancing

    List:

    1- Introduction. 1

    1-1 Introduction. 1

    1-2 The purpose of the thesis. 2

    1-3 stages of completing the thesis. 2

    1-4 thesis structure. 3

    2- Thematic literature. 4

    2-1 Introduction. 4

    2-2 Genetic algorithm structure. 6

    2-3 genetic operators. 7

    2-4 general process of genetic algorithm. 8

    2-5 Algorithm termination condition. 10

    2-6 Some applications of genetic algorithm. 10

    2-7 Definitions. 11

    2-8 Advantages of parallel execution. 12

    2-9 scheduling steps in the grid. 16

    2-10 types of timers. 17

    2-11 types of scheduling. 18

    2-12 How to schedule (static and dynamic). 19

    2-13 schedule structure. 19

    2-14 types of work queues. 21

    2-15 computational complexity of scheduling. 22

    2-16 summary. 22

    3- Research background. 23

    3-1 Introduction. 23

    3-2 greedy algorithms. 23

    3-3 evolutionary algorithms. 26

    3-3-1 solutions based on local search. 26

    3-3-2 population-based solutions. 28

    3-4 summary. 31

    4- Suggested algorithms. 33

    4-1 Introduction. 33

    4-2 Assumptions and definitions. 34

    4-3 Asuffrage Algorithm. 35

    4-4 MaxSuffrage algorithm. 36

    4-5 Balance algorithm version one. 38

    4-6 Balance Algorithm Version Two. 40

    4-7 genetic algorithm and load balancing. 41

    4-8 Summary. 46

    5- The results of the evaluation. 47

    5-1 Introduction. 47

    5-2 Brown evaluation criteria. 47

    5-3 Evaluation of Asuffrage Algorithm. 49

    5-4 MaxSuffrage algorithm evaluation. 51

    5-5 evaluation of the balance algorithm version one. 53

    5-6 of the evaluation of the balance algorithm version two. 54

    5-7 Evaluation of genetic algorithm along with load balancing. 55

    5-8 suggestions for the future.  57

    6- Sources. 58

     

    Source:

    [1] Lorpunmanee S., Sap M. N., Abdullah A. H. and Chompoo-inwai C. (2007), "An Ant Colony Optimization For Dynamic Job Scheduling In Grid Environment", International Journal of Computer and Information Science and Engineering, Vol. 3, No. 1, pp. 207-214.

    [2] Jacob, B., Brown, M., Fukui, K., and Trivedi, N. (2005), “Introduction to Grid Computing”, International Business Machines Corporation.

    [3] Tseng, L.Y. and Yang, S. (1997), "Genetic algorithms for clustering, feature selection and classification", IEEE Int. Conference on Neural Networks, pp.1612-1616.

    [4] Bala, J., Huary, J., Vafaie, H., De jong, K. and Wechslev, H. (1995), "Hybrid learning using genetic algorithms and decision trees for pattern classification", IJCAI conference, Montreal, August 19-25.

    [5] Siedlecki, W. and Sklansky, J. (1989), "A note on genetic algorithms for large scale pattern selection", Pattern Recognition Letters, vol.10, pp. 335-347.

    [6] Vafaie, H. and De Jong, K. (1993), "Robust feature selection algorithms", Proc. of the fifth conference on tools for artificial intelligence, Boston, MA: IEEE Computer Society Press., pp. 356-363.

    [7] Vafaie, H., and De Jong, K. (1992), "Genetic algorithms as a tool for feature selection in machine learning", Proc. of the 4th Int. conference on tools with artificial intelligence, pp.200-204 Arlington, VA.

    [8] Vafaie, H. and Imam, I. (1994), "Feature selection methods: genetic algorithms vs. greedy-like search". Proc. of the Int. conference on fuzzy and intelligent control systems.

    [9] J. H. Holland, (1975), “Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence”, University of Michigan Press.

    [10] K. A. De Jong, (1975), “An analysis of the behavior of a class of genetic adaptive systems”, [PhD Thesis] University of Michigan Ann Arbor, MI, USA.

    [11] M. Mitchell, (1996), “An Introduction to Genetic Algorithms”, MIT Press, Cambridge, MA.

    [12] D. Beasley, D. Bull and R. Martin,Martin, (1993), “An Overview of Genetic Algorithms: Part 1 Fundamentals”, University of Cardiff, Cardiff.

    [13] D. Beasley, D. Bull and R. Martin, (1993), “An Overview of Genetic Algorithms: Part 2 Research Topics”, University of Cardiff, Cardiff.

    [14] D. E. Goldberg, (1989), “Genetic Algorithms in Search, Optimization and Machine Learning", Addison Wesley, Reading, MA.

    [15] Fogel, D.B, (2000), "What is Evolutionary Computation?" IEEE Spectrum, pp. 26-32.

    [16] Back, T, (1996), “Evolutionary Algorithms in Theory & Practice”, Oxford University Press.

    [17] I. Foster, C. Kesselman, and S. Tuecke, (2001), “The anatomy of the grid: Enabling scalable virtual organizations”, International journal of high performance computing applications, vol. 15, no. 3, pp. 200-222. [18] F. Xhafa, and A. Abraham, (2010), "Computational models and heuristic methods for grid scheduling problems", Future generation computer systems, vol. 26, no. 4, pp. 608-621.

    [19] I. Rodero, F. Guim, J. Corbalan et al., (2010), "Grid broker selection strategies using aggregated resource information," Future Generation Computer Systems, vol. 26, no. 1, pp. 72-86.

    [20] B. Plale, P. Dinda, and G. von Laszewski, (2002), "Key concepts and services of a grid information service", in Proceedings of the 15th International Conference on Parallel and Distributed Computing Systems (PDCS), pp. 437-442.

    [21] J. Yu, and R. Buyya, (2005), "A taxonomy of workflow management systems for grid computing," Journal of Grid Computing, vol. 3, no. 3-4, pp. 171-200.

    [22] J. Cao, S. A. Jarvis, S. Saini et al., (2003), “Gridflow: Workflow management for grid computing,” in 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, Tokyo, Japan, pp. 198-205.

    [23] H.-b. ZHANG, L.-s. TANG, and L.-x. LIU, (2009), "Survey of grid scheduling," Computer Engineering and Design, vol. 9, pp. 026.

    [24] V. Subramani, R. Kettimuthu, S. Srinivasan et al., (2002), “Distributed job scheduling on computational grids using multiple simultaneous requests,” in 11th IEEE International Symposium on High Performance Distributed Computing, Edinburgh, Scotland, pp. 359-366.

    [25] D. G. Feitelson, and L. Rudolph, (1998), "Metrics and benchmarking for parallel job scheduling," in Job Scheduling Strategies for Parallel Processing, New York, NY, pp. 1-24.

    [26] Fernandef D., (1989), "Allocating Modules To Processor In A Distributed System", IEEE Transactions on Software Engineering, Vol. 15, No. 11, pp. 1427-1436.

    [27] Braun T.D., Siegel H.J., Beck N., Boloni L.L., Maheswaran M., Reuther A.L., Robertson J.P. and Theys M.D., Yao B., (2001), "A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems", Journal of Parallel and Distributed Computing, Vol. 61, No. 6, pp. 810-837.

    [28] Ritchie G. and Levine J. (2003), “A Fast, Effective Local Search For Scheduling Independent Jobs In Heterogeneous Computing Environments”, Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group, March 15-20, Glasgow Scotland, PP. 59-65.

    [29] YarKhan A. and Dongarra J. (2002), "Experiments With Scheduling Using Simulated Annealing In A Grid Environment", In Proceedings of the 3rd International Workshop on Grid Computing, July 12-15, Baltimore USA, PP. 232-242.

    [30] Ritchie G. (2003), “Static Multi-Processor Scheduling With Ant Colony Optimization& Local Search”, Master of Science thesis, University of Edinburgh.

    [31] Zomaya A. Y. and Teh Y. H. (2001), “Observations On Using Genetic Algorithms For Dynamic Load-Balancing”, IEEE Transactions on Parallel and distributed systems, Vol. 12, No. 2, pp. 899-911.

    [32] Xhafa F., Alba E., Dorronsoro B., Duran B. and Abraham, A.

Presenting an efficient scheduling algorithm in grid computing network with the aim of reducing total completion time and load balancing
How To Access The File
Related Contents:
Number of pages: 81 Category: Computer Engineering

Dissertation of the master's course in computer engineering, software orientation. Abstract The necessity of increasing use of distributed data in computer networks is clear to everyone. A large number of computing and storage resources are placed together and form the grid. In recent years, grid technology has grown significantly, so that it has been used in most scientific ...

Number of pages: 85 Category: Computer Engineering

Master's Thesis in Computer Engineering Abstract: In recent years, due to the growing number of requests and the joining of new customers to the world of computing, computer systems Computing should also change and be more powerful and flexible than before. In the meantime, cloud computing was presented as a model beyond a system that currently has the ability to respond to most ...

Number of pages: 73 Category: Computer Engineering

Master's thesis in the field of computer engineering (Torin Computational Networks Abstract Software (GRID) has provided a context that heterogeneous resources can be used in different geographic locations to solve complex scientific, engineering and business problems. Scheduling operations play a key role in GRID's performance. Due to the dynamics of resources and imprecise ...

Number of pages: 75 Category: Computer Engineering

Abstract The evolution of computing is such that it can be assumed as the fifth basic element after water, electricity, gas and telephone. In recent years, increasing attention has been paid to cloud computing. Cloud computing is a large-scale distributed model that provides customers with a scalable and virtualized pool of managed computing power, storage, and services over the ...

Number of pages: 90 Category: Computer Engineering

Dissertation for obtaining a master's degree in computer engineering, majoring in software. Abstract: Task scheduling algorithm, which is an NP-complete problem, plays a key role in cloud computing systems. The colonial competition algorithm is one of the newest evolutionary optimization algorithms. As its name suggests, this algorithm is based on the modeling of the ...

Number of pages: 85 Category: Computer Engineering

Dissertation for M.Sc. Abstract In this thesis, we have presented a new method in network processing with Ant algorithm. The model we used in the network space is a continuous two-way auction. Due to their simplicity and dynamics, these models are used in many algorithms used to control resources and schedule tasks. Many of these models have weaknesses in their response time ...

Number of pages: 81 Category: Electrical Engineering

Obtaining a master's degree in the field of electrical engineering, electronics, abstract, mechanization of tools is one of the most important and extensive fields used in production processes. Due to the complexity and uncertainty of machining processes, recently soft computing techniques [1] based on physical models have been preferred to predict the performance of machining ...

Number of pages: 79 Category: Electronic Engineering

Seminar for obtaining a master's degree in the field of electrical engineering, electronics, abstract mechanization of tools is one of the most important and extensive fields used in production processes. Due to the complexity and uncertainty of machining processes, recently soft computing techniques [1] based on physical models have been preferred to predict the performance of ...

Number of pages: 137 Category: Facilities - Mechanics

Mechanical Engineering (Tendency to Energy Conversion) Abstract: Investigating the disadvantages of urban water supply networks (as an example of the Langrod water network) and optimizing and designing the optimal network for a specific region using the HBMO honey bee matching algorithm. Due to the global water crisis, today a special approach to the design and optimal use of ...

Number of pages: 74 Category: Electrical Engineering

Master's Thesis of Electrical Engineering - Telecommunications Abstract With the rapid growth of Internet users and real-time services such as voice and video and the need to meet the quality of service required by users, the next generation of cellular networks is expected to provide access to mobile users everywhere. LTE is a new radio access technology proposed for a move ...