Abstract

Scientific workflows epitomizing computation-intensive applications demand heterogeneous processing resources for attaining high performance. Generally, optimal scheduling of the tasks in workflow is well-acknowledged NP-complete problem. In the present work, a new makespan estimation model is proposed to estimate the bounds on the makespan of the workflows using minimal information. The performance of the proposed estimation model is evaluated using four scientific workflows and the estimation of the makespan computed by the model is compared with the actual makespan generated by the most-cited heuristic scheduling algorithms devised for heterogeneous processing systems. The experimental results revealed that the proposed estimation model is effective and can precisely estimate the makespan of the workflows with an error of over 10% and 26% for computation-intensive and data-intensive workflows respectively.

References

• M.R., and D.S.Johnson, “Computers and intractability: A guide to the theory of NP-completeness,” W.H.Freeman and Co., San Franisco, CA, 1979.
• H.Topcuoglu, S.Hariri, and M.Y.Wu, “Performance effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distributed Systems,vol.13 (3), pp.260–274, 2002.
• D.Sirisha, and G.Vijayakumari, “Minimal start time heuristics for scheduling workflows in heterogeneous processing systems, ” Distributed Computing and Internet Technology, Springer Lecture Notes in Computer Science, vol.9581, pp.199-212, 2016.
• E.B.Fernandez, and B.Bussell, “Bounds on the number of resources and time for multiresource optimal schedules,” IEEE Trans. Computers, vol.22(8), pp.745-751,1973.
• K. Jain Kumar, and V. Rajaraman, “Lower and upper bounds on time for multiresource optimal schedules,” IEEE Transactions on Parallel and Distributed Systems, vol.5(8), pp.879-886,1994.
• S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M.-H. Su, and K. Vahi, “Characterization of scientific workflows,” 3rd Workshop on Workflows in Support of Large-Scale Science, pp.1-10, Nov. 2008.
• E.Illavarasan, and P.Thambidurai, “Low complexity performance effective task scheduling algorithm for heterogeneous computing environments,” Journal of Computer Science, vol.3(2), pp.94-103, 2007.
• I. Pietri, G. Juve, E. Deelman and R. Sakellariou, "A Performance model to estimate execution time of scientific workflows on the cloud,” 9th Workshop on Workflows in Support of Large-Scale Science, New Orleans, LA, pp. 11-19, 2014.
• Berriman G, Laity A, Good J, Jacob J, Katz D, Deelman E, Singh G, Su M, Prince T., “Montage: The architecture and scientific applications of a national virtual observatory service for computing astronomical image mosaics,” Proceedings of Earth Sciences Technology Conference, 2006.
• Graves R, Jordan TH, Callaghan S, Deelman E, Field E, Juve G, Kesselman C, Maechling P, Mehta G, Milner K, “Cybershake: A physics-based seismic hazard model for southern california,” Pure and Applied Geophysics, vol. 168(3-4), pp.367–381,2011.
• Abramovici A, Althouse WE, Drever RW, G¨ursel Y, Kawamura S, Raab FJ, Shoemaker D, Sievers L, Spero RE, Thorne KS, “Ligo: The laser interferometer gravitational-wave observatory Science,” vol. 256 (5055), pp.325–333,1992.
• USC Epigenome Center. http :// epigenome.usc.edu. Accessed : October 2015.