A novel graph based approach for automatic composition of high quality grid workflows

ABSTRACT

The workflow paradigm is one of the most important programming models for the Grid. The composition of Grid workflows has been widely studied in the Grid community. However, there is still a lack of a general and efficient approach for automatic composition of Grid workflows. In this paper, we present a STRIPS (Stanford Research Institute Problem Solver) based formal definition of the Grid workflow composition problem, followed by a novel graph based algorithm for automatic composition of high quality (portable, fault tolerant and optimized) Grid workflows. Our algorithm searches for semantic descriptions of workflow activities, i.e., Activity Functions (AFs), defined by ontologies and composes them into Grid workflows using AF Data Dependence (ADD) graphs. The composition process consists of three phases: ADD graph creation, workflow extraction, and workflow optimization. The worst case complexity of our algorithm is quadratic in the number of AFs. An extension of our algorithm to compose Grid workflows with branches and loops is also presented. Experimental results illustrate the effectiveness and efficiency of our approach: (i) the measured worst case execution time of our algorithm further proofs the analyzed time complexity; (ii) the composition of the real world meteorology Grid workflow application MeteoAG with our algorithm takes approximate half a second; and (iii) the execution time of the MeteoAG workflow when running on the Austrian Grid is reduced by up to 25% and the speedup is increased by up to 2.24 by applying our workflow optimization techniques.

REFERENCES

• 1: Austrian Grid. http://www.austriangrid.at.
• 2: Ilkay Altintas , Chad Berkley , Efrat Jaeger , Matthew Jones , Bertram Ludascher , Steve Mock, Kepler: An Extensible System for Design and Execution of Scientific Workflows, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.423, June 21-23, 2004 [doi>10.1109/SSDBM.2004.44]
• 3: J. L. Ambite and D. Kapoor. Automatically Composing Data Workflows with Relational Descriptions and Shim Services. In Proceedings of 6th International Semantic Web Conference and 2nd Asian Semantic Web Conference (ISWC 2007 + ASWC 2007), Busan, Korea, November 2007. Springer.
• 4: José Luis Ambite , Matthew Weathers, Automatic composition of aggregation workflows for transportation modeling, Proceedings of the 2005 national conference on Digital government research, May 15-18, 2005, Atlanta, Georgia
• 14: Chad Berkley , Shawn Bowers , Matthew Jones , Bertram Ludäscher , Mark Schildhauer , Jing Tao, Incorporating semantics in scientific workflow authoring, Proceedings of the 17th international conference on Scientific and statistical database management, p.75-78, June 27-29, 2005, Santa Barbara, CA
• 15: Avrim L. Blum , Merrick L. Furst, Fast planning through planning graph analysis, Artificial Intelligence, v.90 n.1-2, p.281-300, Feb. 1997 [doi>10.1016/S0004-3702(96)00047-1]
• 16: W. R. Cotton, R. A. Pielke, R. L. Walko, G. E. Liston, C. J. Tremback, H. Jiang, R. L. McAnelly, J. Y. Harrington, M. E. Nicholls, G. G. Carrio, and J. P. McFadden. RAMS 2001: Current status and future directions. Meteorology and Atmospheric Physics, 82:5--29, 2003.
• 17: Ewa Deelman , Gurmeet Singh , Mei-Hui Su , James Blythe , Yolanda Gil , Carl Kesselman , Gaurang Mehta , Karan Vahi , G. Bruce Berriman , John Good , Anastasia Laity , Joseph C. Jacob , Daniel S. Katz, Pegasus: A framework for mapping complex scientific workflows onto distributed systems, Scientific Programming, v.13 n.3, p.219-237, July 2005
• 18: Ziyang Duan , Arthur Bernstein , Philip Lewis , Shiyong Lu, Semantics Based Verification and Synthesis of BPEL4WS Abstract Processes, Proceedings of the IEEE International Conference on Web Services, p.734, June 06-09, 2004 [doi>10.1109/ICWS.2004.98]
• 19: T. Fahringer, R. Prodan, R. Duan, J. Hofer, F. Nadeem, F. Nerieri, S. Podlipnig, J. Qin, M. Siddiqui, H.-L. Truong, A. Villazon, and M. Wieczorek. Workflows for eScience, Scientific Workflows for Grids, chapter ASKALON: A Development and Grid Computing Environment for Scientific Workflows. Springer Verlag, 2007.
• 20: T. Fahringer , J. Qin , S. Hainzer, Specification of grid workflow applications with AGWL: an Abstract Grid Workflow Language, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.676-685, May 09-12, 2005
• 21: R. E. Fikes and N. J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2:189--208, 1971.
• 22: Ian T. Foster , Jens-S. Vöckler , Michael Wilde , Yong Zhao, Chimera: AVirtual Data System for Representing, Querying, and Automating Data Derivation, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.37-46, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029704]
• 23: Y. Gil. Workflows for e-Science - Scientific Workflows for Grids, chapter Workflow Composition: Semantic Representations for Flexible Automation. Springer Verlag, 2007.
• 24: Y. Gil, V. Ratnakar, E. Deelman, G. Mehta, and J. Kim. Wings for Pegasus: Creating Large-Scale Scientific Applications Using Semantic Representations of Computational Workflows. In Proceedings of the Nineteenth Conference on Innovative Applications of Artificial Intelligence (IAAI-07), Vancouver, British Columbia, Canada, July 2007.
• 25: Thomas R. Gruber, A translation approach to portable ontology specifications, Knowledge Acquisition, v.5 n.2, p.199-220, June 1993 [doi>10.1006/knac.1993.1008]
• 26: T. Gubala, D. Here¸ Ùzlak, M. Bubak, and M. Malawski. Constructing Abstract Workflows of Applications with Workflow Composition Tool. In Proceedings of Cracow Grid Workshop (CGW'06), 2006.
• 27: Tomasz Gubala , Daniel Herezlak , Marian Bubak , Maciej Malawski, Semantic Composition of Scientific Workflows Based on the Petri Nets Formalism, Proceedings of the Second IEEE International Conference on e-Science and Grid Computing, p.12, December 04-06, 2006 [doi>10.1109/E-SCIENCE.2006.127]
• 28: J. Hoffmann and B. Nebel. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research, 14:253--302, 2001.
• 29: Jena Team. Jena Semantic Web Framework API. http://jena.sourceforge.net/.
• 30: F. Lautenbacher and B. Bauer. A Survey on Workflow Annotation & Composition Approaches. In Proceedings of the Workshop on Semantic Business Process and Product Lifecycle Management (SemBPM) in the context of the European Semantic Web Conference (ESWC), Innsbruck, Austria, 2007.
• 31: M. Lelarge, Z. Liu, and A. V. Riabov. Automatic Composition of Secure Workflows. Technical Report W0607-005, IBM Research Division, July 2006.
• 32: M. Lemos, M. A. Casanova, L. F. B. Seibel, J. A. F. de Macedo, and A. B. de Miranda. Ontology-Driven Workflow Management for Biosequence Processing Systems. In Proceedings of 15th International Conference Database and Expert Systems Applications (DEXA 2004), Zaragoza, Spain, 2004.
• 33: P. Lord, P. Alper, C. Wroe, and C. Goble. The Semantic Web: Research and Applications, chapter Feta: A Light-Weight Architecture for User Oriented Semantic Service Discovery, pages 17--31. Springer, 2005.
• 34: H. Meyer and M. Weske. Automated Service Composition using Heuristic Search. In Proceedings of the Fourth International Conference on Business Process Management (BPM 2006), Vienna, Austria, 2006.
• 35: Jun Qin , Thomas Fahringer, A novel domain oriented approach for scientific grid workflow composition, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
• 36: L. Salayandia, P. P. da Silva, A. Q. Gates, and A. Rebellon. A Model-Based Workflow Approach for Scientific Applications. In Proceedings of the 6th OOPSLA Workshop on Domain-Specific Modeling, 2006.
• 37: F. Schüller, J. Qin, F. Nadeem, R. Prodan, T. Fahringer, and G. Mayr. Performance, Scalability and Quality of the Meteorological Grid Workflow MeteoAG. In Proceedings of 2nd Austrian Grid Symposium, Innsbruck, Austria, September 21-23, 2006. OCG Verlag.
• 38: Mumtaz Siddiqui , Alex Villazon , Jurgen Hofer , Thomas Fahringer, GLARE: A Grid Activity Registration, Deployment and Provisioning Framework, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.52, November 12-18, 2005 [doi>10.1109/SC.2005.30]
• 39: The Object Management Group (OMG). UML 2 Activity Diagram. http://www.omg.org/spec/UML/2.1.2/Superstructure/PDF/.
• 40: Z. Wu, A. Ranabahu, K. Gomadam, A. P. Sheth, and J. A. Miller. Automatic Composition of Semantic Web Services using Process and Data Mediation. Technical report, LSDIS lab, University of Georgia, February 2007.
• 41: Jianting Zhang, Ontology-Driven Composition and Validation of Scientific Grid Workflows in Kepler: a Case Study of Hyperspectral Image Processing, Proceedings of the Fifth International Conference on Grid and Cooperative Computing Workshops, p.282-289, October 21-23, 2006 [doi>10.1109/GCCW.2006.68]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
automatic workflow composition, grid computing, grid workflow, workflow synthesis