SpringerLink
Log in

Towards the Scheduling of Multiple Workflows on Computational Grids

  • Published:
Journal of Grid Computing Aims and scope Submit manuscript

Abstract

The workflow paradigm has become the standard to represent processes and their execution flows. With the evolution of e-Science, workflows are becoming larger and more computational demanding. Such e-Science necessities match with what computational Grids have to offer. Grids are shared distributed platforms which will eventually receive multiple requisitions to execute workflows. With this, there is a demand for a scheduler which deals with multiple workflows in the same set of resources, thus the development of multiple workflow scheduling algorithms is necessary. In this paper we describe four different initial strategies for scheduling multiple workflows on Grids and evaluate them in terms of schedule length and fairness. We present results for the initial schedule and for the makespan after the execution with external load. From the results we conclude that interleaving the workflows on the Grid leads to good average makespan and provides fairness when multiple workflows share the same set of resources.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adzigogov, L., Soldatos, J., Polymenakos, L.: EMPEROR: an OGSA Grid meta-scheduler based on dynamic resource predictions. J Grid Computing 3(1–2), 19–37 (2005)

    Article  Google Scholar 

  2. Amir, Y., Awerbuch, B., Barak, A., Borgstrom, R.S., Keren, A.: An opportunity cost approach for job assignment in a scalable computing cluster. IEEE Trans. Parallel Distrib. Syst. 11(7), 760–768 (2000)

    Article  Google Scholar 

  3. Annis, J., Zhao, Y., Voeckler, J., Wilde, M., Kent, S., Foster, I.: Applying Chimera virtual data concepts to cluster finding in the Sloan Sky Survey. In: Supercomputing ’02: Proceedings of the 2002 ACM/IEEE Conference on Supercomputing, pp. 1–14, Los Alamitos, CA, USA. IEEE Computer Society Press, Silver Spring (2002)

    Google Scholar 

  4. Bajaj, R., Agrawal, D.P.: Improving scheduling of tasks in a heterogeneous environment. IEEE Trans. Parallel Distrib. Syst. 15(2), 107–118 (2004)

    Article  Google Scholar 

  5. Batista, D.M., da Fonseca, N.L.S., Miyazawa, F.K.: A set of schedulers for Grid networks. In: SAC ’07: Proceedings of the 2007 ACM Symposium on Applied Computing, pp. 209–213, Seul, Korea. ACM, New York (2007)

    Chapter  Google Scholar 

  6. Bittencourt, L.F., Madeira, E.R.M.: Fulfilling task dependence gaps for workflow scheduling on Grids. In: 3rd IEEE International Conference on Signal-Image Technology and Internet Based Systems, Shanghai, China (2007)

  7. Bittencourt, L.F., Madeira, E.R.M.: A performance-oriented adaptive scheduler for dependent tasks on Grids. Concurrency and Computation: Practice and Experience 20(9), 1029–1049 (2008)

    Article  Google Scholar 

  8. Boeres, C., Filho, J.V., Rebello, V.E.F.: A cluster-based strategy for scheduling task on heterogeneous processors. In: 16th Symposium on Computer Architecture and High Performance Computing, pp. 214–221, Foz do Iguacu, Brazil. IEEE, Piscataway (2004)

    Chapter  Google Scholar 

  9. Cao, J., Jarvis, S.A., Saini, S., Nudd, G.R.: Gridflow: workflow management for Grid computing. In: 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2003), Tokyo, Japan (2003)

  10. Casanova, H., Zagorodnov, D., Berman, F., Legrand, A.: Heuristics for scheduling parameter sweep applications in Grid environments. In: HCW ’00: Proceedings of the 9th Heterogeneous Computing Workshop, p. 349, Washington, DC, USA. IEEE Computer Society, Los Alamitos (2000)

    Google Scholar 

  11. Chen, H., Maheswaran, M.: Distributed dynamic scheduling of composite tasks on Grid computing systems. In: 11th IEEE Heterogeneous Computing Workshop, pp. 119–128, Washington, DC, USA. IEEE Computer Society, Los Alamitos (2002)

    Google Scholar 

  12. Chun-Ho Liu, C.-M.W., Leung, D.Y.C.: Performance analysis of a linux pc cluster using a direct numerical simulation of fluid turbulence code. Int. J. High Perform. Comput. Appl. 19(4), 365–374 (2005)

    Article  Google Scholar 

  13. Cicerre, F.R.L., Madeira, E.R.M., Buzato, L.E.: A hierarchical process execution support for Grid computing. Concurrency and Computation: Practice and Experience 18(6), 581–594 (2006)

    Article  Google Scholar 

  14. Cooper, K., Dasgupta, A., Kennedy, K., et al.: New Grid scheduling and rescheduling methods in the grads project. In: IPDPS Next Generation Software Program — NSFNGS — PI Workshop, pp. 199, 206. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  15. Corrêa, R.C., Ferreira, A., Rebreyend, P.: Integrating list heuristics into genetic algorithms for multiprocessor scheduling. In: SPDP ’96: Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP ’96), p. 462, Washington, DC, USA. IEEE Computer Society, Los Alamitos (1996)

    Chapter  Google Scholar 

  16. de Oliveira Lucchese, F., Yero, E.J.H., Sambatti, F.S., Henriques, M.A.A.: An adaptive scheduler for Grids. J Grid Computing 4(1), 1–17 (2006)

    Article  Google Scholar 

  17. Deelman, E., Kesselman, C., Mehta, G., Meshkat, L., Pearlman, L., Blackburn, K., Ehrens, P., Lazzarini, A., Williams, R., Koranda, S.: GriPhyN and LIGO, building a virtual data Grid for gravitational wave scientists. In: HPDC ’02: Proceedings of the 11th IEEE International Symposium on High Performance Distributed Computing, p. 225, Washington, DC, USA. IEEE Computer Society, Los Alamitos (2002)

    Chapter  Google Scholar 

  18. Deelman, E., Singh, G., Su, M.-H., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., Vahi, K., Berriman, G.B., Good, J., Laity, A., Jacob, J.C., Katz, D.S.: Pegasus: a framework for map** complex scientific workflows onto distributed systems. Sci. Program. 13(3), 219–237 (2005)

    Google Scholar 

  19. Derbal, Y.: Entropic Grid scheduling. J Grid Computing 4(4), 373–394 (2006)

    Article  MATH  Google Scholar 

  20. Dogan, A.,Özgüner, F.: Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems. Comput. J. 48(3), 300–314 (2005)

    Article  Google Scholar 

  21. Dong, F., Akl, S.G.: Scheduling algorithms for Grid computing: state of the art and open problems. Technical report, Queen’s University School of Computing, Kingston, Canada (2006)

  22. Duran, B., Xhafa, F.: The effects of two replacement strategies on a genetic algorithm for scheduling jobs on computational Grids. In: SAC ’06: Proceedings of the 2006 ACM Symposium on Applied Computing, pp. 960–961, Dijon, France. ACM, New York (2006)

    Chapter  Google Scholar 

  23. El-Rewini, H., Ali, H.H., Lewis, T.G.: Task scheduling in multiprocessing systems. IEEE Computer 28(12), 27–37 (1995)

    Google Scholar 

  24. Foster, I.: Globus toolkit version 4: software for service oriented systems. In: IFIP International Conference on Network and Parallel Computing, pp. 2–13 (2005)

  25. Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the Grid: enabling scalable virtual organization. Int. J. High Perform. Comput. Appl. 15(3), 200–222 (2001)

    Article  Google Scholar 

  26. Frey, J.: Condor DAGMan: handling inter-job dependencies. http://www.cs.wisc.edu/condor/dagman/ (2002)

  27. Fujimoto, N., Hagihara, K.: Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational Grid. In: 2nd International Symposium on Parallel and Distributed Computing, Slovenia, pp. 80–87. IEEE, Piscataway (2003)

    Chapter  Google Scholar 

  28. Fujimoto, N., Hagihara, K.: A comparison among Grid scheduling algorithms for independent coarse-grained tasks. In: Symposium on Applications and the Internet Workshops, pp. 674–680, January 2004, Tokyo, Japan. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  29. Goldchleger, A., Kon, F., Goldman, A., Finger, M., Bezerra, G.C.: InteGrade: object-oriented Grid middleware leveraging idle computing power of desktop machines. Concurrency and Computation: Practice and Experience 16(5), 449–459 (2004)

    Article  Google Scholar 

  30. Grajcar, M.: Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system. In: DAC ’99: Proceedings of the 36th ACM/IEEE Conference on Design Automation, pp. 280–285, New York, NY, USA. ACM, New York (1999)

    Chapter  Google Scholar 

  31. Hagras, T., Janeček, J.: An approach to compile-time task scheduling in heterogeneous computing systems. In: 33rd International Conference on Parallel Processing Workshops, pp. 182–189. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  32. Hakem, M., Butelle, F.: Dynamic critical path scheduling parallel programs onto multiprocessors. In: 19th International Parallel and Distributed Processing Symposium. IEEE Computer Society, Los Alamitos (2005)

    Google Scholar 

  33. Harchol-Balter, M., Downey, A.B.: Exploiting process lifetime distributions for dynamic load balancing. ACM Trans. Comput. Syst. 15(3), 253–285 (1997)

    Article  Google Scholar 

  34. He, X., Sun, X., von Laszewski, G.: Qos guided min-min heuristic for Grid task scheduling. J. Comput. Sci. Technol. 18(4), 442–451 (2003)

    Article  MATH  Google Scholar 

  35. Hou, E.S.H., Ansari, N., Ren, H.: A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distrib. Syst. 5(2), 113–120 (1994)

    Article  Google Scholar 

  36. Jain, R., Chiu, D., Hawe, W.: A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report TR-301, DEC Research (1984)

  37. Kwok, Y.-K., Ahmad, I.: Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parallel Distrib. Syst. 7(5), 506–521 (1996)

    Article  Google Scholar 

  38. Kwok, Y.-K., Ahmad, I.: Benchmarking the task graph scheduling algorithms. In: IPPS/SPDP, pp. 531–537 (1998)

  39. Litzkow, M.J., Livny, M., Mutka, M.W.: Condor: a hunter of idle workstations. In: Proceedings of the 8th International Conference on Distributed Computing Systems, USA, pp. 104–111 (1988)

  40. Phillips, C., Stein, C., Wein, J.: Task scheduling in networks. SIAM J. Discrete Math. 10(4), 573–598 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  41. Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer, New York (2008)

    MATH  Google Scholar 

  42. Prodan, R., Fahringer, T.: Dynamic scheduling of scientific workflow applications on the Grid: a case study. In: SAC ’05: Proceedings of the 2005 ACM Symposium on Applied Computing, pp. 687–694, New York, NY, USA. ACM, New York (2005)

    Chapter  Google Scholar 

  43. Rahman, M., Venugopal, S., Buyya, R.: A dynamic critical path algorithm for scheduling scientific workflow applications on global Grids. In: E-SCIENCE ’07: Proceedings of the Third IEEE International Conference on e-Science and Grid Computing (e-Science 2007), pp. 35–42, Washington, DC, USA. IEEE Computer Society, Los Alamitos (2007)

    Chapter  Google Scholar 

  44. Sakellariou, R., Zhao, H.: A hybrid heuristic for dag scheduling on heterogeneous systems. In: 13th Heterogeneous Computing Workshop, pp. 111, 123. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  45. Taylor, I.J., Deelman, E., Gannon, D.B., Shields, M. (eds.): Workflows for e-Science. Scientific Workflows for Grids. Springer, New York (2007)

    Google Scholar 

  46. Thain, D., Tannenbaum, T., Livny, M.: Condor and the Grid. In: Berman, F., Fox, G., Hey, T. (eds.) Grid Computing: Making the Global Infrastructure a Reality. Wiley, New York (2002)

    Google Scholar 

  47. Theobald, K.B., Kumar, R., Agrawal, G., Heber, G., Thulasiram, R.K., Gao, G.R.: Develo** a communication intensive application on the earth multithreaded architecture. In: Euro-Par ’00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing, pp. 625–637, London, UK. Springer, Los Alamitos (2000)

    Google Scholar 

  48. Topcuoglu, H., Hariri, S., Wu, M.-Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260–274 (2002)

    Article  Google Scholar 

  49. Vianna, B.A., Fonseca, A.A., Moura, N.T., Menezes, L.T., Mendes, H.A., Silva, J.A., Boeres, C., Rebello, V.E.F.: A tool for the design and evaluation of hybrid scheduling algorithms for computational Grids. In: Proceedings of the 2nd Workshop on Middleware for Grid Computing, pp. 41–46, New York, NY, USA. ACM, New York (2004)

    Chapter  Google Scholar 

  50. Yang, T., Gerasoulis, A.: Dsc: scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5(9), 951–967 (1994)

    Article  Google Scholar 

  51. Yu, J., Buyya, R.: A taxonomy of scientific workflow systems for Grid computing. SIGMOD Records 34(3), 44–49 (2005)

    Article  Google Scholar 

  52. Zhang, S., Zong, Y., Ding, Z., Liu, J.: Workflow-oriented Grid service composition and scheduling. In: International Symposium on Information Technology: Coding and Computing, vol. 2, pp. 214–219, April 2005, Las Vegas, Nevada, USA. IEEE Computer Society, Los Alamitos (2005)

    Google Scholar 

  53. Zhao, H., Sakellariou, R.: Scheduling multiple dags onto heterogeneous systems. In: 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Rohdes Island, Greece. IEEE, Piscataway (2006)

    Google Scholar 

  54. Zhao, Y., Dobson, J., Foster, I., Moreau, L., Wilde, M.: A notation and system for expressing and executing cleanly typed workflows on messy scientific data. SIGMOD Records 34(3), 37–43 (2005)

    Article  Google Scholar 

  55. Zhao, Y., Hategan, M., Clifford, B., Foster, I., von Laszewski, G., Nefedova, V., Raicu, I., Stef-Praun, T., Wilde, M.: Swift: fast, reliable, loosely coupled parallel computation. In: IEEE Congress on Services, pp. 199–206, Los Alamitos, CA, USA. IEEE Computer Society, Los Alamitos (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computing, University of Campinas—UNICAMP, P. O. 6176, Campinas, São Paulo, Brazil

    Luiz Fernando Bittencourt & Edmundo R. M. Madeira

Authors
  1. Luiz Fernando Bittencourt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edmundo R. M. Madeira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luiz Fernando Bittencourt.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bittencourt, L.F., Madeira, E.R.M. Towards the Scheduling of Multiple Workflows on Computational Grids. J Grid Computing 8, 419–441 (2010). https://doi.org/10.1007/s10723-009-9144-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10723-009-9144-1

Keywords

Search

Navigation