Summary
In this paper we present the design and implementation of an hyper-heuristic for efficiently scheduling independent jobs in Computational Grids. An efficient scheduling of jobs to Grid resources depends on many parameters, among others, the characteristics of the resources and jobs (such as computing capacity, consistency of computing, workload, etc.). Moreover, these characteristics change over time due to the dynamic nature of Grid environment, therefore the planning of jobs to resources should be adaptively done. Existing ad hoc scheduling methods (batch and immediate mode) have shown their efficacy for certain types of resource and job characteristics. However, as stand alone methods, they are not able to produce the best planning of jobs to resources for different types of Grid resources and job characteristics. In this work we have designed and implemented a hyper-heuristic that uses a set of ad hoc (immediate and batch mode) scheduling methods to provide the scheduling of jobs to Grid resources according to the Grid and job characteristics. The hyper-heuristic is a high level algorithm, which examines the state and characteristics of the Grid system (jobs and resources), and selects and applies the ad hoc method that yields the best planning of jobs. The resulting hyper-heuristic based scheduler can be thus used to develop network-aware applications that need efficient planning of jobs to resources. The hyper-heuristic has been tested and evaluated in a dynamic setting through a prototype of a Grid simulator. The experimental evaluation showed the usefulness of the hyper-heuristic for planning of jobs to resources as compared to planning without knowledge of the resource and job characteristics.
See the full content of this document
Extract
A Hyper-Heuristic for Adaptive Scheduling in Computational Grids
1. Introduction
During the last years, Grid computing has motivated the development of large scale applications that need the large computing capacity offered by the Computational Grids (CGs). Among the most interesting features of CGs is their parallel nature. A CG is a "type of parallel and distributed system that enables the sharing, selection, and aggregation of geographically distributed autonomous resources dynamically depending on their availability, capability, performance, cost, and users' QoS requirements" [6, 7]. It is precisely the parallel and distributed nature of CGs that was first exploited for solving computationally hard combinatorial optimization problems [4, 17, 13].In order to achieve the Grid as a single computational unit many complex issues are nowadays being investigated. One key issue is to efficiently benefit from the parallel nature of Grid systems. The large computing capacity offered by Grids not necessarily yields to high performance applications. Indeed, efficient techniques that allocate jobs/applications to Grid resources are necessary. The resource allocation problem is known to be computationally hard [9]. Although scheduling problems are among most studied problems in combinatorial optimization, the heterogenous and dynamic characteristics of Grids makes the problem very complex for Grid environments. For instance, a Grid can connect PCs, LANs and Supercomputers and jobs of very different workload can arrive in the Grid. Moreover...See the full content of this document
Sponsored links
