Abstract
Multi-cluster environments are composed of multiple clusters that act collaboratively, thus allowing computational problems that require more resources than those available in a single cluster to be treated. However, the degree of complexity of the scheduling process is greatly increased by the resources heterogeneity and the co-allocation process, which distributes the tasks of parallel jobs across cluster boundaries.
In this paper, the authors propose a new MIP model which determines the best scheduling for all the jobs in the queue, identifying their resource allocation and its execution order to minimize the overall makespan. The results show that the proposed technique produces a highly compact scheduling of the jobs, producing better resources utilization and lower overall makespan. This makes the proposed technique especially useful for environments dealing with limited resources and large applications.
Chapter PDF
Similar content being viewed by others
References
Javadi, B., Akbari, M.K., Abawajy, J.H.: A performance Model for Analysis of Heterogeneous Multi-Cluster Systems. Parallel Computing 32(11-12), 831–851 (2006)
Bucur, A.I.D., Epema, D.H.J.: Schedulling Policies for Processor Coallocation in Multicluster Systems. IEEE TPDS 18(7), 958–972 (2007)
Jones, W., Ligon, W., Pang, L., Stanzione, D.: Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters. Journal of Supercomputing 34(2), 135–163 (2005)
Yang, C., Tung, H., Chou, K., Chu, W.: Well-Balanced Allocation Strategy for Multiple-Cluster Computing. In: IEEE Int. Conf. FTDCS 2008, pp. 178–184 (2008)
Naik, V.K., Liu, C., Yang, L., Wagner, J.: Online Resource Matching for Heterogeneous Grid Environments. In: Int. Conf. CCGRID 2005, vol. 2, pp. 607–614 (2005)
Lérida, J.L., Solsona, F., Giné, F., García, J.R., Hernández, P.: Resource Matching in Non-dedicated Multicluster Environments. In: Palma, J.M.L.M., Amestoy, P.R., Daydé, M., Mattoso, M., Lopes, J.C. (eds.) VECPAR 2008. LNCS, vol. 5336, pp. 160–173. Springer, Heidelberg (2008)
Shmueli, E., Feitelson, D.G.: Backfilling with Lookahead to Optimize the Packing of Parallel Jobs. J. Parallel Distrib. Comput. 65(9), 1090–1107 (2005)
Blanco, H., Lérida, J.L., Cores, F., Guirado, F.: Multiple Job Co-Allocation Strategy for Heterogeneous Multi-Cluster Systems Based on Linear Programming. Journal of Supercomputing 58(3), 394–402 (2011)
Feitelson, D.G., Rudolph, L., Schwiegelshohn, U.: Parallel Job Scheduling — A Status Report. In: Feitelson, D.G., Rudolph, L., Schwiegelshohn, U. (eds.) JSSPP 2004. LNCS, vol. 3277, pp. 1–16. Springer, Heidelberg (2005)
Tsafrir, D., Etsion, Y., Feitelson, D.G.: Backfilling using system-generated predictions rather than user runtime estimates. IEEE TPDS 18(6), 789–803 (2007)
Hussain, S., Qureshi, K.: Optimal job packing, a backfill scheduling optimization for a cluster of workstations. Journal of Supercomputing 54(3), 381–399 (2010)
Zhang, W., Cheng, A.M.K., Hu, M.: Multisite co-allocation algorithms for computational grid. In: IPDPS 2006, pp. 335–335 (2006)
Feng, H., Song, G., Zheng, Y., Xia, J.: A Deadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Dependent Tasks in Grid Computing. In: Li, M., Sun, X.-H., Deng, Q., Ni, J. (eds.) GCC 2003. LNCS, vol. 3033, pp. 113–120. Springer, Heidelberg (2004)
Buyya, R., Murshed, M., Abramson, D., Venugopal, S.: Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost-time optimization algorithm. Softw. Pract. Exper. 35(5), 491–512 (2005)
Munir, E.U., Li, J., Shi, S.: QoS sufferage heuristic for independent task scheduling in grid. Information Technology Journal 6(8), 1166–1170 (2007)
Garg, S., Buyya, R., Siegel, H.: Time and cost trade-off management for scheduling parallel applications on Utility Grids. Future Generation Computer Systems 26(8), 1344–1355 (2010)
Ernemann, C., Hamscher, V., Schwiegelshohn, U., Yahyapour, R., Streit, A.: On Advantages of Grid Computing for Parallel Job Scheduling. In: Int. Conf. CCGRID 2002 (2002)
Li, H., Groep, D., Wolters, L.: Workload Characteristics of a Multi-cluster Supercomputer. In: Feitelson, D.G., Rudolph, L., Schwiegelshohn, U. (eds.) JSSPP 2004. LNCS, vol. 3277, pp. 176–193. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blanco, H., Guirado, F., Lérida, J.L., Albornoz, V.M. (2013). MIP Model Scheduling for Multi-Clusters. In: Caragiannis, I., et al. Euro-Par 2012: Parallel Processing Workshops. Euro-Par 2012. Lecture Notes in Computer Science, vol 7640. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36949-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-36949-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36948-3
Online ISBN: 978-3-642-36949-0
eBook Packages: Computer ScienceComputer Science (R0)