Home // International Journal On Advances in Software, volume 2, number 1, 2009 // View article

A Heuristic Approach to the Allocation of DifferentWorkloads in Computational Grid Environments

Authors:
Javier Díaz
Sebastián Reyes
Camelia Muñoz-Caro
Alfonso Niño

Keywords: Self-Scheduling Algorithms, Heuristic Scheduling, Computational Grid.

Abstract:
Self-scheduling algorithms can achieve a good balance between workload and communication overhead in computational systems. In particular, Quadratic Self-Scheduling (QSS) and Exponential Self-Scheduling (ESS) are flexible enough to adapt to distributed systems. Thus, they are of interest for application in Internet-based Grids of computers. We have tackled the problem of scheduling a set of independent tasks in a computational Grid using a simulator and a heuristic approach based in simulated annealing. To test this approach, we have considered different workload distributions. We find that the optimal Simulated Annealing (SA) results permit to reduce the overall computing time of a set of tasks up to a 16%, with respect to results obtained with previous values of the parameters experimentally determined. In addition, the time to obtain the SA optimized parameters by simulation is negligible compared with that needed using experimental measures. Moreover, after the optimization, the heuristic approach provides equivalent performance for different workloads (random, increasing, decreasing) and different number of tasks. These results show the high adaptability of the QSS and ESS selfscheduling algorithms, which can be fully exploited thanks to the heuristic approach here presented.

Pages: 1 to 10

Copyright: Copyright (c) to authors, 2009. Used with permission.

Publication date: June 7, 2009

Published in: journal

ISSN: 1942-2628