Abstract
In its broadest sense, scheduling of Grid applications can be viewed as a negotiation process between a scheduling service optimising user-centric objectives such as execution time, and a resource manager optimising provider-centric metrics such as resource utilisation or fairness. In this paper we enhance an existing list scheduling algorithm designed for minimising the workflow makespan with advance reservation-based negotiation functionality. As an instantiation of the new negotiation phase, we investigate two advance reservation functionality from the resource provider perspective: attentive and progressive. We illustrate through real-world experiments a two-fold benefit of our approach: improved execution predictability from the user’s perspective, and higher resource utilisation fairness through a new progressive allocation strategy from the provider’s perspective.
Similar content being viewed by others
References
Aida, K., Casanova, H.: Scheduling mixed-parallel applications with advance reservations. In: 17th International Symposium on High Performance Distributed Computing. IEEE Computer Society Press, CA (2008)
Dumitrescu, C.L., Raicu, I., Foster, I.: The design, usage, and performance of GRUBER: a Grid usage service level agreement based brokering infrastructure. J. Grid Computing 5(1), 99–126 (2007)
Elmroth, E., Tordsson, J.: A Grid resource broker supporting advance reservations and benchmark-based resource selection. In: State-of-the-art in Scientific Computing. LNCS, vol. 3732, pp. 1077–1085. Springer, Berlin (2005)
Fahringer, T., Prodan, R., Duan, R., Hofer, J., Nadeem, F., Nerieri, F., Stefan Podlipnig, J.Q., Siddiqui, M., Truong, H.L., Villazon, A., Wieczorek, M.: Askalon: a development and Grid computing environment for scientific workflows. In: Taylor, I.J., Deelman, E., Gannon, D.B., Shields, M. (eds.) Scientific Workflows for Grids, Workflows for e-Science, Frameworks and Tools: Workflow Generation, Refinement and Execution, pp. 450–471. Springer, Berlin (2007)
Fahringer, T., Qin, J., Hainzer, S.: Specification of Grid workflow applications with AGWL: an abstract Grid workflow language. In: International Symposium on Cluster Computing and the Grid. IEEE Computer Society Press, CA (2005)
Foster, I., Kesselman, C.: Globus: a metacomputing infrastructure toolkit. Int. J. Supercomput. Appl. High Perform. Comput. 11(2), 115–128 (1997)
Foster, I., Kesselman, C., Lee, C., Lindell, R., Nahrstedt, K., Roy, A.: A distributed resource management architecture that supports advance reservations and co-allocation. In: International Workshop on Quality of Service, pp. 27–36. IEEE Computer Society Press, CA (1999)
Hudert, S., Ludwig, H., Wirtz, G.: Negotiating SLAs—an approach for a generic negotiation framework for WS-Agreement. J. Grid Computing 7(2), 225–246 (2009)
Kennedy, K., Blythe, J., Jain, S., Deelman, E., Gil, Y., Vahi, K., Mandal, A.: Task scheduling strategies for task scheduling strategies for workflow-based applications in Grids. IEEE Computer Society Press, CA (2005)
McGough, A.S., Afzal, A., Darlington, J., Furmento, N., Mayer, A., Young, L.: Making the Grid predictable through reservation and performance modelling. Comput. J. 48(3), 358–368 (2005)
Nadeem, F., Yousaf, M., Prodan, R., Fahringer, T.: Soft benchmarks-based application performance prediction using a minimum training set. In: International Conference on e Science and Grid Computing. IEEE Computer Society Press, CA (2006)
Prodan, R., Fahringer, T.: Dynamic scheduling of scientific workflow applications on the Grid using a modular optimisation tool: a case study. In: 20th Symposion of Applied Computing. ACM, New York (2005)
Prodan, R., Fahringer, T.: Grid computing. Experiment Management, Tool Integration, and Scientific Grid Workflows. LNCS, Scientific Grid Workflows, vol. 4340, chap. 317, pp. 203–269. Springer, Berlin (2007)
Prodan, R., Fahringer, T.: Overhead analysis of scientific workflows in Grid environments. IEEE Trans. Parallel Distrib. Syst. 19(3), 378–393 (2008)
Pugliese, A., Talia, D., Yahyapour, R.: Modeling and supporting Grid scheduling. J. Grid Computing 6(2), 195–213 (2008)
Röblitz, T., Reinefeld, A.: Co-reservation with the concept of virtual resources. In: International Conference on Cluster Computing and the Grid, pp. 398–406. IEEE Computer Society Press, CA (2005)
Schwarz, K., Blaha, P., Madsen, G.K.H.: Electronic structure calculations of solids using the wien2k package for material sciences. Comput. Phys. Commun. 147(71) (2002)
Siddiqui, M., Villazón, A., Fahringer, T.: Grid capacity planning with negotiation-based advance reservation for optimized qos. In: Supercomputing Conference, p. 103. ACM, New York (2006)
Singh, G., Kesselman, C., Deelman, E.: Application-level resource provisioning on the Grid. In: 2nd International Conference on e-Science and Grid Computing, p. 83. IEEE Computer Society Press, CA (2006)
Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13, 260–274 (2002)
Volkert, J.: Austrian Grid: overview on the project with focus on parallel applications. In: International Symposium on Parallel and Distributed Computing, p. 14. Timisoara, Romania (2006)
Wieczorek, M., Prodan, R., Fahringer, T.: Scheduling of scientific workflows in the ASKALON Grid environment. Special issue on scientific workflows. SIGMOD Rec. 34(3), 56–62 (2005)
Wieczorek, M., Prodan, R., Fahringer, T.: Comparison of workflow scheduling strategies on the Grid. In: International Conference on Parallel Processing and Applied Mathematics. LNCS, vol. 3911, pp. 792–800. Springer, Berlin (2006)
Zhao, H., Sakellariou, R.: Advance reservation policies for workflows. In: 12th International Workshop on Job Scheduling Strategies for Parallel Processing. LNCS, vol. 4376, pp. 47–67. Springer (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Prodan, R., Wieczorek, M. Negotiation-Based Scheduling of Scientific Grid Workflows Through Advance Reservations. J Grid Computing 8, 493–510 (2010). https://doi.org/10.1007/s10723-010-9165-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10723-010-9165-9