Design and Development of Compile Time Task Scheduling Algorithm for Grids

Abstract

Grid Computing is an evolving computing infrastructure that promises to transform the way organizations and individuals compute, communicate and collaborate. It offers untapped processing cycles from networks of computers spanning vast geographical boundaries.

Grid Resource Scheduling falls under the realms of NP-Complete problems in Computer Science and Engineering. A wide variety of Grid Scheduling Algorithms have been proposed and implemented in the literature of context, each having its own pros and cons as only a heuristic and approximate solution is possible to NP-Complete problems.

Compile Time Task Scheduling follows a system-centric approach to Schedule Grid applications aiming for optimization of the overall performance of the Grid system. It follows a centralized and heuristic based approach to make Scheduling decisions under the Quality of Service constraints.

This thesis work focuses on the design, development and simulation of a Compile Time Task Scheduling Algorithm for Grid Computing Environment. The proposed Algorithm i.e. SCH takes into account the high degree of heterogeneity among the target Grid Computing Platforms and applications submitted to the Grid. It also takes into account the communication costs between Grid Nodes. The SCH Algorithm aims to minimize the job submission time to the Grid Nodes. The SCH Algorithm is simulated on Open Source GridSim Toolkit 4.0 and JCharts 0.7.5 API is employed for statistical trend visualization of simulation Data. The outcomes of the SCH Algorithm simulation on GridSim Toolkit under different test scenarios show that the Wait Time for job submission to the Grid can be optimized and thus become negligible by applying the heuristics of the SCH Algorithm.