Practical Scheduling of Bag-of-Tasks Applications on Grids with Dynamic Resilience
- 30 April 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 56 (6) , 815-825
Abstract
Over the past decade, the grid has emerged as an attractive platform to tackle various large-scale problems, especially in science and engineering. One primary issue associated with the efficient and effective utilization of heterogeneous resources in a grid is scheduling. Grid scheduling involves a number of challenging issues, mainly due to the dynamic nature of the grid. There are only a handful of scheduling schemes for grid environments that realistically deal with this dynamic nature that have been proposed in the literature. In this paper, two novel scheduling algorithms, called the shared-input-data-based listing (SIL) algorithm and the multiple queues with duplication (MQD) algorithm for bag-of-tasks (BoT) applications in grid environments are proposed. The SIL algorithm targets scheduling data-intensive BoT (DBoT) applications, whereas the MQD algorithm deals with scheduling computationally intensive BoT (CBoT) applications. Their common and primary forte is that they make scheduling decisions without fully accurate performance prediction information. Another point to note is that both scheduling algorithms adopt task duplication as an attempt to reduce serious schedule increases. Our evaluation study employs a number of experiments with various simulation settings. The results show the practicability and competitiveness of our algorithms when compared to existing methodsKeywords
This publication has 20 references indexed in Scilit:
- A Grid Scheduling Algorithm for Bag-of-Tasks Applications Using Multiple Queues with Duplication2006
- An evaluation of the close-to-files processor and data co-allocation policy in multiclusters2005
- Evolving Toward the Perfect Schedule: Co-scheduling Job Assignments and Data Replication in Wide-Area Systems Using a Genetic Algorithm2005
- Scheduling strategies for master-slave tasking on heterogeneous processor platformsIEEE Transactions on Parallel and Distributed Systems, 2004
- Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems2003
- Scheduling distributed applications: the SimGrid simulation framework2003
- A better model for generating test networks2002
- Simgrid: a toolkit for the simulation of application scheduling2002
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977