Abstract:
Grid systems are inter connected collections of heterogeneous and geographically distributed resource connected together to satisfy various needs of the users. Scheduling an application in such a heterogeneous Grid system is a challenging issue because target resources are heterogeneous and their load and availability may vary with time. It requires an effective scheduling and load balancing algorithm that should properly exploit the existing resources of heterogeneous Grid environment.
There are various scheduling and load balancing techniques that have been proposed for locally distributed multiprocessor systems. When these techniques are extended to a Grid environment, they all suffer from significant deficiencies. Some uses centralized approach that makes the algorithm unscalable, when it is used for scheduling in Grid environment, while others assume the overhead involved in searching for appropriate resources to be negligible. Here we propose an adaptive de-centralized scheduling and load balancing algorithm for a generalized Grid model of N-resource nodes that not only takes into account the node and network heterogeneity, but also considers the overhead involved in coordinating among the nodes. This algorithm also considers the current load of each node before scheduling a job. Our algorithm is de-centralized, scalable, and overlaps the node coordination time with that of the actual processing of ready jobs, thus saving valuable clock cycles needed for making decisions
