A Novel Graph Based Approach for Automatic Composition of High Quality Grid Workflows

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 Re-search 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 Func-tions (AFs), defined by ontologies and composes them into Grid workflows using AF Data Dependence (ADD) graphs. The compo-sition process consists of three phases: ADD graph creation, work-flow extraction, and workflow optimization. The worst case com-plexity of our algorithm is quadratic in the number of AFs. An ex-tension of our algorithm to compose Grid workflows with branches and loops is also presented. Experimental results illustrate the ef-fectiveness 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 meteorol-ogy Grid workflow application MeteoAG with our algorithm takes approximate half a second; and (iii) the execution time of the Me-teoAG 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