Dynamic scheduling of scientific workflow applications on the grid: a case study

ABSTRACT

The existing Grid workflow scheduling projects do not handle recursive loops which are characteristic to many scientific problems. We propose a hybrid approach for scheduling Directed Graph (DG)-based workflows in a Grid environment with dynamically changing computational and network resources. Our dynamic scheduling algorithm is based on the iterative invocation of classical static Directed Acyclic Graphs (DAGs) scheduling heuristics generated using well-defined cycle elimination and task migration techniques. We approach the static scheduling problem as an application of a modular optimisation tool using genetic algorithms. We report successful implementation and experimental results on a pilot real-world material science workflow application.

REFERENCES

• 1: P. Blaha, K. Schwarz, G. Madsen, D. Kvasnicka, and J. Luitz. WIEN 2k: An Augmented Plane Wave plus Local Orbitals Program for Calculating Crystal Properties. Institute of Physical and Theoretical Chemistry, Vienna University of Technology, 2001.
• 2: Ewa Deelman et. al. Mapping abstract complex workflows onto grid environments. Journal of Grid Computing, 1:25--39, 2003.
• 3: Ken Kennedy et. al. New Grid Scheduling and Rescheduling Methods in the GrADS Project. In International Parallel and Distributed Processing Symposium, Workshop for Next Generation Software. IEEE Computer Society Press, April 2004.
• 4: Thomas Fahringer , Alexandru Jugravu , Sabri Pllana , Radu Prodan , Clovis Seragiotto, Jr. , Hong-Linh Truong, ASKALON: a tool set for cluster and Grid computing: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.143-169, February 2005 [doi>10.1002/cpe.v17:2/4]
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: Yu-Kwong Kwok , Ishfaq Ahmad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, v.47 n.1, p.58-77, Nov. 25, 1997 [doi>10.1006/jpdc.1997.1395 ]
• 7: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 8: Radu Prodan , Thomas Fahringer, ZENTURIO: a grid middleware-based tool for experiment management of parallel and distributed applications, Journal of Parallel and Distributed Computing, v.64 n.6, p.693-707, June 2004 [doi>10.1016/j.jpdc.2003.10.004]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods; Scheduling

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
genetic algorithms, grid computing, optimisation, performance steering, scheduling, scientific workflows