A TAXONOMY OF TASK SCHEDULING ALGORITHMS IN THE GRID
Abstract
One motivation of Grid computing is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To achieve this goal, efficient task scheduling algorithms are essential. However, scheduling algorithms in the Grid present high diversities that need to be classified. In this paper, with the help of an abstract scheduling architecture, some key features of the task scheduling problem in the Grid are discussed, followed by a taxonomy of the scheduling algorithms. Some typical examples are given in each category to present a picture of the current research and help to find new research problems.
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
A. Abraham , R. Buyya and B. Nath , Nature's Heuristics for Scheduling Jobs on Computational Grids, Proc. 8th IEEE International Conference on Advanced Computing and Communications (2000) pp. 45–52. Google ScholarA. H. Alhusaini , V. K. Prasanna and C. S. Raghavendra , A Unified Resource Scheduling Framework for Heterogeneous Computing Environments, Proc. the 8th Heterogeneous Computing Workshop (HCW) (1999) pp. 156–165. Google ScholarM. Arora , S. K. Das and R. Biswas , A Decentralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments, Proc. International Conference on Parallel Processing (ICPP) (2002) pp. 499–505. Google Scholar- J. Software-Practice & Experience 32(15), 1437 (2002). Crossref, ISI, Google Scholar
- , chapter in The Grid: Blueprint for a Future Computing Infrastructure , eds.
I. Foster and C. Kesselman ( Morgan Kaufmann Publishers , 1998 ) . Google Scholar - IEEE Trans., on Parallel and Distributed Systems 14(4), 369 (2003). Crossref, ISI, Google Scholar
J. Blythe , Task Scheduling Strategies for Workflow-based Applications in Grids, Proc. the 5th IEEE International Symp. on Cluster Computing and the Grid (CCGrid) (2005) pp. 759–767. Google Scholar- J. Parallel and Distributed Computing 61(6), 810 (2001). Crossref, ISI, Google Scholar
R. Buyya , J. Giddy and D. Abramson , An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications, Proc. the 2nd International Workshop on Active Middleware Services (2000) pp. 221–230. Google Scholar- Proc. the IEEE 93(3), 698 (2005). Crossref, ISI, Google Scholar
H. Casanova , Heuristics for Scheduling Parameter Sweep Applications in Grid Environments, Proc. HCW 2000 (2000) pp. 349–363. Google Scholar-
C. Cavanaugh , Quality of Service Negotiation for Distributed, Dynamic Real-Time Systems , Proc. the 14th IEEE International Parallel & Distributed Processing Symposium (IPDPS) ( 2000 ) . Google Scholar S. J. Chapin , The Legion Resource Management System, Proc. the 5th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP) (1999) pp. 162–178. Google ScholarK. Cooper , New Grid Scheduling and Rescheduling Methods in the GrADS Project, Proc. the IPDPS 2004 (2004) pp. 199–206. Google ScholarK. Czajkowski , A Resource Management Architecture for Metacomputing Systems, Proc. JSSPP 1998,LNCS 1459 (1998) pp. 62–82. Google ScholarK. Czajkowski , Grid Information Services for Distributed Resource Sharing, Proc. the 10th IEEE International Symposium on High-Performance Distributed Computing (HPDC) (2001) pp. 181–194. Google ScholarH. Dail , H. Casanova and F. Herman , A Decoupled Scheduling Approach for the GrADS Environment, Proc. the SuperComputing 2002 (2002) pp. 1–14. Google Scholar- J. Grid Computing 1(1), 9 (2003). ISI, Google Scholar
E. Deelman , Pegasus: Mapping Scientific Workflows onto the Grid, Proc. Grid Computing: Second European AcrossGrids Conference (2004) pp. 11–26. Google Scholar- J. Grid Computing 4(1), 19 (2006). Crossref, Google Scholar
F. Dong and S. Akl , A Joint Data and Computation Scheduling Algorithm for the Grid, Proc. Euro-Par 2007,LNCS 4681 (2007) pp. 587–597. Google Scholar-
F. Dong and S. Akl , PFAS: A Resource-performance-fluctuation-aware Workflow Scheduling Algorithm for Grid Computing , Proc. HCW 2007 ( 2007 ) . Google Scholar -
F. Dong and S. Akl , A Mobile Agent Based Workflow Rescheduling Approach for the Grid , Proc. the 19th International Conference on Parallel and Distributed Computing and Systems (PDCS) ( 2007 ) . Google Scholar -
F. Dong and S. Akl , Distributed Two-phase Computation-data Combinational Workflow Scheduling Algorithms for the Grid , Proc. ICPP 2007 ( 2007 ) . Google Scholar -
H. El-Rewini , T. Lewis and H. Ali , Task Scheduling in Parallel and Distributed Systems ( PTR Prentice Hall , 1994 ) . Google Scholar I. Foster , Globus Toolkit Version 4: Software for Service-Oriented Systems, Proc. IFIP International Conference on Network and Parallel Computing,LNCS 3779 (2005) pp. 2–13. Google ScholarJ. Gehring and T. Preiss , Scheduling a Metacomputer with Uncooperative Sub-schedulers, Proc. the JSSPP 1999,LNCS 1659 (1999) pp. 179–201. Google ScholarV. Hamscher , Evaluation of Job-Scheduling Strategies for Grid Computing, Proc. the 1st IEEE/ACM International Workshop on Grid Computing (Grid),LNCS 1971 (2000) pp. 191–202. Google Scholar- J. of Computer Science and Technology 18(4), 442 (2003). Crossref, ISI, Google Scholar
E. Heymann , Adaptive Scheduling for Master-Worker Applications on the Computational Grid, Proc. Grid 2000,LNCS 1971 (2000) pp. 214–227. Google Scholar- J. Grid Computing 4(4), 373 (2006). Crossref, Google Scholar
-
T. Ma and R. Buyya , Critical-Path and Priority based Algorithms for Scheduling Workflows with Parameter Sweep Tasks on Global Grids , Proc. the 17th International Symposium on Computer Architecture and High Performance Computing ( 2005 ) . Google Scholar -
J. MacLaren , Towards Service Level Agreement Based Scheduling on the Grid , Proc. the 2nd European Across Grids Conference ( 2004 ) . Google Scholar - IEEE Trans. Comput. 55(6), 757 (2006). Crossref, ISI, Google Scholar
- J. Grid Computing 5(2), 197 (2007). Crossref, ISI, Google Scholar
- International J. High Performance Computing Applications 17(3), 209 (2003). Crossref, ISI, Google Scholar
S. McGough , Workflow Enactment in ICENI, Proc. UK e-Science All Hands Meeting (2004) pp. 894–900. Google ScholarS. Park and J. Kim , Chameleon: a Resource Scheduler in a Data Grid Environment, Proc. CCGrid 2003 (2003) pp. 253–260. Google ScholarK. Ranganathan and I. Foster , Identifying Dynamic Replication Strategies for a High Performance Data Grid, Proc. Grid 2001,LNCS 2242 (2001) pp. 75–86. Google ScholarK. Ranganathan and I. Foster , Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications, Proc. HPDC 2002 (2002) pp. 352–361. Google Scholar- IEE Proc. on Computer and Digital Techniques 141(1), l (1994). Google Scholar
F. D. Sacerdoti , Wide area cluster monitoring with Ganglia, Proc. IEEE International Conference on Cluster Computing (Cluster) (2003) pp. 289–298. Google Scholar- J. of Scientific Programming 12(4), 253 (2004). Crossref, ISI, Google Scholar
J. Schopf and F. Berman , Stochastic Scheduling, Proc. SuperComputing 1999 (1999) pp. 48–68. Google Scholar- J. Schopf, Ten Actions When SuperScheduling, document of Scheduling Working Group, Global Grid Forum, http://www.ggf.Org/documents/GFD.4.pdf, July 2001 . Google Scholar
-
H. Shan , Scheduling in Heterogeneous Grid Environments: The Effects of Data Migration , Proc. 2004 International Conference on Advanced Computing and Communication ( 2004 ) . Google Scholar - ACM Computing Surveys 28(1), 237 (1996). Crossref, ISI, Google Scholar
S. Song , Y. Kwok and K. Hwang , Security-Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling, Proc. IPDPS 2005 (2005) pp. 65–74. Google Scholar- International J. High Performance Computing Applications 13(3), 253 (1999). Crossref, ISI, Google Scholar
J. Subhlok , P. Lieu and B. Lowekamp , Automatic Node Selection for High Performance Applications on Networks, Proc. the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (1999) pp. 163–172. Google ScholarX. Sun and M. Wu , Grid Harvest Service: A System for Long-term Application-level Task Scheduling, Proc. 17th IPDPS (2003) pp. 25–32. Google ScholarA. Takefusa , A Study of Deadline Scheduling for Client-Server Systems on the Computational Grid, Proc. the HPDC 2001 (2001) pp. 406–415. Google Scholar- IEEE Trans. Parallel and Distributed Systems 13(3), 260 (2002). Crossref, ISI, Google Scholar
- ACM SIGMOD Record 34(3), 56 (2005). Crossref, ISI, Google Scholar
- J. Future Generation Computing Systems 15(5-6), 757 (1999). Crossref, Google Scholar
-
D. Wright , Cheap Cycles from the Desktop to the Dedicated Cluster: Combining Opportunistic and Dedicated Scheduling with Condor , Proc. Conference on Linux Clusters: the HPC Revolution ( 2001 ) . Google Scholar M. Wu and X. Sun , A General Self-Adaptive Task Scheduling System for Non-Dedicated Heterogeneous Computing, Proc. Cluster 2003 (2003) pp. 354–361. Google Scholar- International J. High Performance Computing and Networking 2(2), 186 (2004). Crossref, Google Scholar
L. Young , Scheduling Architecture and Algorithms within the ICENI Grid Middleware, Proc. UK e-Science All Hands Meeting (2003) pp. 5–12. Google Scholar-
J. Yu , R. Buyya and C. K. Tham , QoS-based Scheduling of Workflow Applications on Service Grids , Proc. the 1st IEEE International Conference on e-Science and Grid Computing ( 2005 ) . Google Scholar - J. Grid Computing 3(3-4), 171 (2005). Crossref, ISI, Google Scholar
-
Z. Yu and W. Shi , An Adaptive Rescheduling Strategy for Grid Workflow Applications , Proc. IPDPS 2007 ( 2007 ) . Google Scholar - http://www.globus.org . Google Scholar
- http://www.openpbs.org . Google Scholar
- http://www.cs.wise.edu/condor . Google Scholar


