Task Graph Based Scheduling And Resource Monitoring In Grid Computing

Task Graph Based Scheduling And Resource Monitoring In Grid Computing

1S. Gokuldev, 2 Lija Anna Mathew

1Associate Professor, 2PG Scholar

1&2Department of Computer Science and Engineering

1&2SNS College of Engineering, Coimbatore, India

Abstract Grid computing is a form of distributed systems that enables the sharing of resources from various administrative domains to solve a particular problem. Job scheduling is used to schedule the applications submitted by the user. It allows choosing best match of resource for a particular job and thus increases the job throughput and resource utilization. The process of monitoring refers to systematically gather information about present or past status of all resources of interest. Due to the dynamic behaviour of grid systems, the monitoring components are becoming necessary in order to utilize different types of distributed resources and provide consistent and unified services to the user. In this paper task graph concept is used for resource monitoring and job scheduling there by reducing the overall execution time.

Index Terms Grid computing, Job scheduling, Resource monitoring, Particle Swarm Optimization.

1. INTRODUCTION

   Grid is a shared collection of reliable and unreliable resources and interactively communicating resources of different virtual organizations. It is a type of parallel and distributed systems that enables sharing, selection and aggregation of distributed autonomous resources during run-time based on their respective efficiency, capability and performance. Grid system controls and coordinates the integrity of the grid by balancing the usage of reliable and unreliable resources among its participants providing better quality of service. Grid computing is a form of distributed computing where by resources of many computers in a network is used at the same time, to solve a single problem. Grid technologies promise to change the way organizations tackle complex computational problems.

   Grid computing got its name because it strives for an ideal scenario in which the CPU cycles and storage of millions of systems across a worldwide network function as a flexible, easily accessible pool.Grid computing contains task scheduling, security problems, resource management, and information management and so on. Task scheduling is an important problem in grid computing. There are large number of task are computed on the grid environment. So that large number of scheduling algorithm must be adopted for minimum completion time.This task scheduling is based on NP-complete problem in grid environment. If one considers the internet as network for communication, grid computing can be considered as a network of computation [6].

   Grid systems are designed for collaborative sharing of resources and for interconnecting virtual organizations with various forms of resources and different types of services. So the grid system is very dynamic and highly unstable. The grid

   systems are classified into three types.They are computational grid, data grid and service grid. The computational grid category denotes systems that have a higher aggregate computational capacity available for single applications than the capacity of any consistent machine in the system. This computational grid is a collection of distributed heterogeneous resources which can be used as an ensemble to execute large scale applications. The data grid category deals with the controlled sharing and management of large amount of distributed data and also provide an infrastructure for synthesizing new information from data repositories such as digital libraries or data warehouses that are distributed in wide area networks. The service grid category provides services that are not provided by a single machine.

   The two important function available in the grid computing are job scheduling and resource allocation. These functions are based upon the adequate information of available resources also depends on sufficient information of available resources. Timely acquiring resources are great importance in ensuring overall performance in grid computing system.

   The basic function used in most of the computing systems is resource monitoring. Grid resource state monitoring is all about the running state, distribution and malfunction of resources in grid system by means of monitoring strategy. There are large number of monitoring tools are to be used for monitor the single clusters and the individual personal computers. The monitoring service is deployed on computing resource node.

   Grid resource condition prediction focuses on the variation trend and running track of resources in grid system by means of modelling and analyzing historical monitoring data. Historical information and future variation generated by monitoring and prediction are combined to be fed into the grid system for analyzing performance, eliminating bottleneck, diagnose error, and maintaining dynamic load balancing. Thus it helpful for the grid users to obtain desired computing results by efficiently utilizing the system resources to

   minimize cost, maximize performance and tradeoff between the cost and performance.

   The rest of the paper is organized as follows. Section II reviews the related work in literature. Section III outlines the problem formulation. Section IV briefly introduces all the job scheduling and resource monitoring algorithms. Section V describes the proposed task graph concept in detail. Section VI focuses on the setup of the simulation and the experimental results. Finally the conclusion is given in Section VII.

2. RELATED WORK

   Job is an atomic unit of work or a collection of jobs. The job scheduling system is responsible for selecting the best suitable resources in grid for user jobs. Job scheduling is generated by the management and scheduling system and job schedules for each machine in the grid by taking static restrictions and dynamic parameters of jobs and machines into consideration. It is very cumbersome in large grids and it determines the efficiency of the grid.

   There are different types of monitoring tools are being designed for monitoring individual personal computer or single cluster, so that they can't be used in grid systems directly. The monitoring technologies employed and the resource sensors realized are reusable for grid systems. Moreover, these tools are being evolved to support grid system.

   A new dynamic scheduling algorithm which is the combination of heuristic search algorithm and traditional Shortest Job First (SJF) algorithm called swift scheduler [10]. The algorithm takes care of jobs memory and CPU requirements along with the priority of jobs and resources.

   In a grid scheduler, an independent jobs are in optimized manner and the mapping of grid resources is so hard. So the combination of uninformed search and informed search to provide the good optimal solution for mapping resources and jobs, to minimize turnaround time with minimum cost and average waiting times of the jobs in the queue.

   Particle Swarm Optimization (PSO) algorithm [1] is a global optimization algorithm and it is a population based stochastic global optimization method. This algorithm is adopted for solving task scheduling problem in grid environment. PSO algorithm is considered to be a very fast algorithm and is emerging as a widely used algorithm for optimization problems. Particle Swarm Optimization algorithm work that having a population named as swarm and candidate solution called a particles. It is based on a special management of memory, due to the memory characteristics f PSO algorithm. It works better and there is no need of having the knowledge of other particles. This PSO is one of the latest evolutionary optimization techniques by nature. The PSO has the better ability for global searching and has been successfully applied to many areas such as, neural

   network training etc. It is used for direct search methods, to find an optimal solution to an objective function in a search space. Also this Particle Swarm Optimization algorithm converges in the fast rate and it is much suited for task scheduling. The task scheduling based PSO algorithm can be applied only in a computational grid environment.

   PH-PSO algorithm [2] is used for grid resource monitoring and machine learing based prediction. The monitoring is caring about the running state, distribution and malfunctions of resource in grid system. Grid resource state prediction focuses on the variation trend and running track of resources in a grid system. The prediction is also used for modelling and analyzing historical monitoring data. Historical information is generated by monitoring and future variation generated by prediction stage.

   The design and prototype implementation of a long term application performance prediction and task scheduling system called as Grid Harvest Service (GHS) [4]. This GHS is used for performance evaluation and task scheduling applications in the grid environment. It is based on novel performance prediction model and a set of task scheduling algorithm. The GHS support three classes for task scheduling they are single task, parallel processing, and meta task. The GHS uses an adaptive measurement methodology to monitor the resource usage pattern.

   Ganglia project [5] aims at monitoring cluster information including host name, identification, memory capacity, name and version of operating system, file system data, the processor load, and so on through carrying on the monitoring to the cluster.

3. PROBLEM FORMULATION

   The grid system is a large scale distributed environment which provides a high number of powerful resources to its users. It differs from classical distributed systems by their heterogeneous and dynamic nature. While resources are nearly identical and stable in a classical distributed system,the grid system resources are highly heterogeneous and dynamic in terms of both stability and dynamicity of their properties. Grid systems provide many types of resources such as computing resources (CPU cycles, storage, network bandwidth, memory etc.) and services (access to specific data, shared software etc.). Web services in this area are very popular software entities that offer an easy and standard way to access functionalities of different kinds of platforms.

   Grid resource monitoring and grid resource prediction are two mechanisms for acquiring information of grid resources. Grid resource state monitoring focus on running state, distribution and malfunction of resources in a grid system by means of monitoring strategies. Grid resource state prediction concentrate on the variation trend and running track of resources in a grid system by means of modeling and analyzing historical monitoring data. The historical information and future variation are combined together

   and is fed in to grid system for analyzing performance, eliminate bottleneck, diagnosing error, and maintaining dynamic load balancing, thereby helping the grid users obtain desired computing results by efficiently utilizing system resources in terms of minimized cost, maximized performance, and trade-offs between cost and performance.

   A computing grid is a complex distributed system, and its resource monitoring and prediction system is a distributed system that dynamically processes grid resource state information. The main parameters consider for developing the existing system are:

   • Responsiveness and robustness

   • Modularity and extensibility

   • Efficiency and transparency

     The service distribution is based on the resource information which is managed using a hierarchical structure. This includes the services such as monitoring service, prediction service, evaluation service, and information services.

     The main drawbacks are:

   • Monitoring and prediction of grid tasks is not feasible.

   • Grid resources classification and evaluation is not considered.

   • Evaluation of grid tasks is not employed.

4. SCHEDULING AND RESOURCE MONITORING

   Grid computing is mainly focus on resource sharing in grid. Every node can apply resources from any other nodes. The computational grid can be used to solve large scale problems in science and engineering. It involves sharing of heterogeneous resources such as hardware platform, software architectures and computer languages. The grid system can be used for the open standard protocol interface to provides high quality services. It is designed for collaborative with other organizations for sharing resources and it is scalable.

   Job scheduling is mainly used to finding the best suitable resource in a grid to execute user jobs. The scheduling process is done in one resources or more than one resource that is available at the time of scheduling. The job scheduling is mainly used to schedule the user jobs to appropriate resources in grid environment. There are mainly three types of scheduling strategies in grid they are centralized, hierarchical and decentralized.Centralized scheduling contain single job scheduler, here all jobs are to be collected. The hierarchical contain two job schedulers, one at the global level and another at the local level. The last one is decentralized scheduling, in this scheduling distributed schedulers are interact with each other. The main objective for the scheduling is minimizing the processing time or minimizing the cost and the goal of resource allocation is to optimize the use of resources and then maximize the revenue.

   Monitoring [11] is an important process in grid system. It can be effectively monitor resources and collect important information based on the current or past status of the resources. There are large number of monitoring tools are used for monitoring a single clusters or the individual personal computers. The monitoring service is deployed on computing resource node. This resource node manages resource sensors and generates the resource monitoring data. In grid resource,the monitoring cares about the status, distribution and fault situation of resources in grid environment. Historical information is generated from the monitoring stage. Timely acquiring resource status information is very important in ensuring overall performance of grid computing.

   A. Algorithms Used in Scheduling and Resource Monitoring

   1. First- Come, First-Served Scheduling

      First come first served is the simplest algorithm [3]. It is based on the theory that resources are assigned to the primary proposed tasks. The first task is finished and then the resource is reassigned to the next proposed task. This process uses the order of executed tasks in the order of submission. If a significant amount of time is essential to complete the first task, the same amount of time is used up waiting for the execution of the next task. As a result, a convey result is created and the whole system performance will be reduced. One of the major drawbacks of this scheme is that the average time is often quite long.

   2. Genetic Algorithm (GA)

      Genetic Algorithm (GA) is a search heuristic. It mimics the process of natural evolution. This algorithm is routinely used to generate useful solution for optimization and search problems.

   3. Parallel Hybrid Particle Swarm Optimization algorithm

      The Parallel Hybrid Particle Swarm Optimization (PH-PSO) [2] algorithm is used for grid resource monitoring and machine learning based prediction. The monitoring is caring about the running state, distribution and malfunctions of resource in grid system. Grid resource state prediction focuses on the variation trend and running track of resources in a grid system.This prediction is also used for modeling and analyzing historical monitoring data. Historical information is generated by monitoring and a future variation generated by prediction which is joint as one to feed a grid system for analyze performance, eliminating bottleneck and diagnose error.

   4. Particle Swarm Optimization

   The PSO algorithm was proposed as a population based stochastic global optimization method. The population is called swarm in PSO, and it is made up of particles. The ith particle has such properties as fitness fi, position xi, and velocity vi. The PSO [9] start by initializing the particle positions xi and velocities vi and computes the corresponding fitness fi. Then

   particles fly across the search space, indicates a series of iteration is performed. The following rule shows the fitness of all particle that is updated for each iteration,

   k+1 k k

   k+1 k k

   Vi =w Vi +c1 r1(Pi-Xi)+c2r2(Pg-Xi) (1)

   X k+1=X k+V k+1 (2)

   i i i

   where the superscripts k, k+1 are iteration numbers r1 and r2 are two random factors in the interval [0,1] wk is the inertia weight and c1 and c2 are constants representing the "cognitive" and "social" components of information, respectively. Each particle remember its best position (cognitive knowledge), which is denoted as Pi.The knowledge of the best position is achieved across the entire swarm, which is denoted as Pg, is shared between particles (social knowledge). The rules drive particles are updated towards the optimal region and, all particles tend to group around the global optimum until a solution is finally found.

5. TASK GRAPH BASED SCHEDULING

   The main objective of task graph concept is time optimization. Task graph is used for allocating the suitable resources to the grid environment. Resource allocation and job scheduling have great importance in grid computing. Adequate information of available resources is based on these functions. Timely get resource status information is of great importance in ensuring overall performance of grid computing. In order to minimize the execution time in grid environment task graph concept is used.

   A processor completes the execution of the assigned task and the next task event is generated. At this event, the global scheduler assigns the outgoing communications of the finished task to channels. Each of the task having its own fixed execution time [8]. If anyone gets completed before the fixed time, then the remaining time gets wasted. To avoid this, online scheduling was used.

   Figure 1 shows the working principle of task graph. Initially the user sends a job to the grid system. The monitoring system monitor the job based on the job details and the resource details. The monitor service is monitoring the resource node. Then it manages the resource sensors and generates the resource monitoring data. At the same time the information systems predict the resource for job. The information node interacts with the users and runs the storage and query. The task details executes only in its specified time. If any task finished its execution before or after its fixed execution time it means that the scheduling is not efficient. After this applying the task graph mapping to the grid system and allocate the tasks based upon resources free in the grid system.

   Fig. 1 Architecture of Task Graph

6. EXPERIMENTAL RESULTS

   In grid environment, one of the most important problems is how to represent a solution for task scheduling. GridSim [7] has been used to create the simulation of grid computing environment. Gridsim is a java based toolkit for modeling and simulation of distributed resource management and scheduling for conventional grid environment.

   The proposed concept is implemented in java. The simulation is conducted in heterogeneous environment to verify the improvement of proposed model over other scheduling models. The scheduling algorithm is implemented on a laptop with core i2 and 2 GB RAM. The inputs to the simulations are the total number of randomly generated jobs.

   In this simulation the scheduling process uses 1 resource and 3 users. Here the grid completion id is 3. The time utilization can be finding by the difference between the end time and start time. The job submission can be depended upon the system time. Job can be processed only at the system time. There are many types of strategies are used in grid computing and here the optimize time strategy is used. This optimized time strategy is used for quick processing and the outputs are simulated in gridsim.

   Figure 2 shows the delay compare graph. It can be find out by the delay between the start time and the end time. This delay is also called as the time utilization. The figure 3 shows the time utilization of three users.

   Fig. 2. Delay Compare Graph

   Fig. 3 Time Utilization

7. CONCLUSION

Grid computing is a promising tendency to solve high demanding applications and all kinds of grid problems. The main objective of grid environment is to achieve high performance computing by optimal usage of geographically distributed and heterogeneous resources. The success of grid computing depends on the effective utilization of the system for various computing intensive job.Vast number of resources is available on the grid and the main problem is job scheduling and resource monitoring. The main objective of grid task scheduling is to raise the throughput based on the availability of resources. Effective job scheduling can be performed well with successive monitoring of grid resources. This paper addresses the problem of job scheduling and monitoring through the successive use of task graph concept with minimum execution time.

ACKNOWLEDGEMENT

It is with great pleasure that I wish to acknowledge people who have helped me tremendously during my career. Without their help, none of this work could have been possible. I wish to express my sincere gratitude to my project guide, Prof. S. Gokuldev for his guidance, encouragement, motivation, and continued support throughout my academic year. I would like to thank all friends and family for their valuable support.

REFERENCES

1. Kennedy J and R .C. Eberhart (1995) Particle Swarm Optimization Proc. IEEE Intl Conf. Neural Networks, pp. 1942-1948

2. Liang Hu, Xi-Long Che and Si-Qing Zheng (2012) Online System for Grid Resource Monitoring and Machine Learning-Based Prediction IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS Vol. 23 no. 1.

3. Merian Meddeber, Belabbas Yagoubi, Walid Kadri A Static Tasks Assignment for GridComputing

4. Ming Wu,Xian-He Sun (2006)Grid harvest service A Performance system of grid computing J. Parallel and Distributed Computing Vol. 66 No. 10 pp.1322-1337.

5. M.L.Massie, B.N. Chun and D.E Culler (2004),The Ganglia Distributed Monitoring System: Design ,Implementation,and Experience,Parallel Computing, vol 30 no 7.

6. Myer Thomas (may 2003) Grid computing: Conceptual Flyover for Developers, http://www.106/bm.com/developer works/gr-fly.html gridsrc.pdf

7. M.Murshed and R. Buyya (2002),Gridsim A tool kit for modelling and simulation of distributed management and scheduling for grid computing

8. Pravanjan Choudhury, P.P. Chakrabarti, Rajeev Kumar(2012)

   Online Scheduling of Dynamic Task Graphs with Communication and Contention for Multiprocessors IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 23, NO. 1.

9. Shi. Y and R.C. Eberhart (2000) A Modified Particle Swarm Optimizer Proc. IEEE Intl Conf. Evolutionary Computation pp. 69-73.

10. Somasundaram. K, S. Radhakrishnan(2009) Task Resource Allocation in Grid using Swift Scheduler Int. J. of Computer Communications & Control ISSN 1841-9836 E-ISSN 1841-9844 Vol. IV No. 2 pp. 158-166

11. Waheed Abdul Waren Smith, Jude George and Jerry Yan (2000) An Infrastructure for Monitoring and Management in Computational Grids Proc. Fifth Intl Workshop Languages Compilers and Run-Time Systems for Scalable Computers,Vol. 1915 pp. 235-245.