Optimizing execution time predictions of scientific workflow applications in the Grid through evolutionary programming

Planning for execution of scientific workflow applications in the Grid requires in advance prediction of workflow execution time for optimized execution of these applications. However, predicting execution times of such applications is very complex mainly due to different structures of workflows, possible parallel execution of workflow tasks on multiple resources and the dynamic and heterogeneous nature of the Grid. In this paper, we describe an optimized method (in extension to a previous work by Nadeem et al. (2009) [4]) for execution time prediction of workflow applications in the Grid. We characterize workflows in terms of attributes describing their structures and performance during different stages of their execution. Overall, performance of the workflows is modeled through templates of workflow attributes. An optimized method exploiting evolutionary programming is employed to search for suitable templates. Three different induction models are employed to generate predictions and later compared for their accuracy. The results from our experiments for three real-world workflow applications on a real Grid are presented to show the effectiveness of our approach. We also compare the proposed approach with our previous method based on supervised exhaustive search by Nadeem and Fahringer (2009) [4].

► Workflows are considered in terms of their static and runtime information. ► Suitable templates are searched through a method based on Evolutionary Programming. ► Our templates consider different relationships between workflow attributes. ► Our approach is evaluated through experiments for three real-world workflows. ► The overheads of the proposed approach are quite small.