nach oben

Cluster Computing

Erschienen in:

01.06.2014

DA-TC: a novel application execution model in multicluster systems

verfasst von: Zhifeng Yun, Zhou Lei, Gabrielle Allen, Daniel S. Katz, J. Ramanujam

Erschienen in: Cluster Computing | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The availability of a large number of separate clusters has given rise to the field of multicluster systems in which these resources are coupled to obtain their combined benefits to solve large-scale compute-intensive applications. However, it is challenging to achieve automatic load balancing of the jobs across these participating autonomic systems. We developed a novel user space execution model named DA-TC to address the workload allocation techniques for the applications with large number of sequential jobs in multicluster systems. Through this model, we can achieve dynamic load balancing for task assignment, and slower resources become beneficial factors rather than bottlenecks for application execution. The effectiveness of this strategy is demonstrated through theoretical analysis. This model is also evaluated through extensive experimental studies and the results show that when compared with the traditional method, the proposed DA-TC model can significantly improve the performance of application execution in terms of application turnaround time and system reliability in multicluster circumstances.

Vorheriger Artikel High efficient sedimentary basin simulations on hybrid CPU-GPU clusters

Nächster Artikel Software quality in the clouds: a cloud-based solution

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Task clustering technologies can partially remove the inter-task communication.

Some clusters may be overloaded by other users and take a long time to allocate resources for its assigned TCs.

We only consider the single CPU per node. It can be easily extended to multicore system if job is scheduled at the core level.

A system is said to be greedy if it never leaves any resource idle unless there is no job waiting for that resource.

Multiple tasks are merged into one single job.

The experiment can easily be extended on heterogeneous participating clusters with different local scheduling systems and access methods.

Abawajy, J., Dandamudi, S.: Parallel job scheduling on multicluster computing system. In: Proceedings of 2003 IEEE International Conference on Cluster Computing, pp. 11–18. IEEE Computer Society Press, Los Alamitos (2003). doi:10.1109/CLUSTR.2003.1253294

Aumage, O.: Heterogeneous multi-cluster networking with the Madeleine III communication library. In: Proceedings of 2002 IEEE International Parallel and Distributed Processing Symposium, vol. 2, pp. 85–96. IEEE Computer Society Press, Los Alamitos (2002). doi:10.1109/IPDPS.2002.1015658

Banawan, S.A., Zeidat, N.M.: A comparative study of load sharing in heterogeneous multicomputer systems. In: Proceedings of the 25th Annual Symposium on Simulation, ANSS’92, pp. 22–31. IEEE Computer Society Press, Los Alamitos (1992). http://portal.acm.org/citation.cfm?id=306902.306921 CrossRef

Banen, S., Bucur, A.I.D., Epema, D.H.J.: A measurement-based simulation study of processor co-allocation in multicluster systems. In: Scheduling Strategies for Parallel Processing, pp. 105–128. Springer, Berlin (2003) CrossRef

Barreto, M., Avila, R., Navaux, P.: The multicluster model to the integrated use of multiple workstation clusters. In: Proc. of the 3rd Workshop on Personal Computer-based Networks of Workstations, pp. 71–80 (2000)

Berten, V., Goossens, J., Jeannot, E.: On the distribution of sequential jobs in random brokering for heterogeneous computational grids. IEEE Trans. Parallel Distrib. Syst. 17(2), 113–124 (2006) CrossRef

Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Nashua (1996)

Brevik, J., Nurmi, D., Wolski, R.: Predicting bounds on queuing delay for batch-scheduled parallel machines. In: Proceedings of the Eleventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’06, pp. 110–118. ACM Press, New York (2006). doi:10.1145/1122971.1122989

Chow, Y.C., Kohler, W.: Models for dynamic load balancing in a heterogeneous multiple processor system. IEEE Trans. Comput. C-28(5), 354–361 (1979). doi:10.1109/TC.1979.1675365 CrossRefMathSciNet

10.

Chu, M., Fan, K., Mahlke, S.: Region-based hierarchical operation partitioning for multicluster processors. In: Proc. of the SIGPLAN’03 Conference on Programming Language Design and Implementation, pp. 300–311 (2003)

11.

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

12.

Downey, A.: Using queue time predictions for processor allocation. In: Feitelson, D., Rudolph, L. (eds.) Job Scheduling Strategies for Parallel Processing. Lecture Notes in Computer Science, vol. 1291, pp. 35–57. Springer, Berlin/Heidelberg (1997) CrossRef

13.

Downey, A.B.: Predicting queue times on space-sharing parallel computers. In: Proceedings of the 11th International Symposium on Parallel Processing, IPPS’97, pp. 209–218. IEEE Computer Society Press, Los Alamitos (1997). http://portal.acm.org/citation.cfm?id=645607.661350 CrossRef

14.

Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: enabling scalable virtual organizations. Int. J. High Perform. Comput. Appl. 15, 200–222 (2001). doi:10.1177/109434200101500302. http://portal.acm.org/citation.cfm?id=1080644.1080667 CrossRef

15.

Frey, J., Tannenbaum, T., Livny, M., Foster, I., Tuecke, S.: Condor-g: a computation management agent for multi-institutional grids. In: Proceedings of 10th IEEE International Symposium on High Performance Distributed Computing, pp. 55–63 (2001). doi:10.1109/HPDC.2001.945176 CrossRef

16.

He, L., Jarvis, S.A., Spooner, D.P., Chen, X., Nudd, G.R.: Hybrid performance-based workload management for multiclusters and grids. IEE Proc., Softw. 151(5), 224–231 (2004) CrossRef

17.

He, L., Jarvis, S.A., Spooner, D.P., Jiang, H., Dillenberger, D.N., Nudd, G.R.: Allocating non-real-time and soft real-time jobs in multiclusters. IEEE Trans. Parallel Distrib. Syst. 17, 99–112 (2006). doi:10.1109/TPDS.2006.18 CrossRef

18.

He, L., Jarvis, S.A., Spooner, D.P., Nudd, G.R.: Optimising static workload allocation in multiclusters. In: Proceedings of 18th IEEE International Parallel and Distributed Processing Symposium (IPDPS’04), pp. 26–30. IEEE Computer Society Press, Los Alamitos (2004)

19.

Jobs, P.: http://www.sysadmin.hep.ac.uk/wiki/pilot_jobs

20.

Kee, Y.S., Kesselman, C., Nurmi, D., Wolski, R.: Enabling personal clusters on demand for batch resources using commodity software. In: Parallel and Distributed Processing Symposium, International, pp. 1–7 (2008). doi:10.1109/IPDPS.2008.4536167

21.

Khalid, O., Anthony, R.J., Nilsson, P., Keahey, K., Schulz, M., Parrot, K., Petridis, M.: Enabling and optimizing pilot jobs using xen based virtual machines for the hpc grid applications. In: VTDC’09: Proceedings of the 3rd International Workshop on Virtualization Technologies in Distributed Computing, pp. 1–8. ACM Press, New York (2009) CrossRef

22.

Kleinrock, L.: Queueing System. Wiley, New York (1975)

23.

Leslie, R., McKenzie, S.: Evaluation of loadsharing algorithms for heterogeneous distributed systems. Comput. Commun. 22(4), 376–389 (1999). http://dblp.uni-trier.de/db/journals/comcom/comcom22.html#LeslieM99 CrossRef

24.

MacLaren, J.: Harc: the highly-available resource co-allocator. In: Proceedings of the 2007 OTM Confederated International Conference on the Move to Meaningful Internet Systems: CoopIS, DOA, ODBASE, GADA, and is, vol. Part II, OTM’07, pp. 1385–1402. Springer, Berlin, Heidelberg (2007). http://portal.acm.org/citation.cfm?id=1784707.1784731 CrossRef

25.

Nelson, R.: Probability, Stochastic Processes, and Queueing Theory. Springer, Berlin (1995) CrossRefMATH

26.

Nilsson, P.: Experience from a pilot based system for atlas. J. Phys. Conf. Ser. 119(6), 062,038 (2008) CrossRefMathSciNet

27.

Nurmi, D., Brevik, J., Wolski, R.: Qbets: queue bounds estimation from time series. In: Proceedings of Job Scheduling Strategies for Parallel Processing (JSSPP), pp. 76–101 (2007)

28.

Nurmi, D., Wolski, R., Brevik, J.: Probabilistic advanced reservations for batch-scheduled parallel machines. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP’08, pp. 289–290. ACM Press, New York (2008). doi:10.1145/1345206.1345260

29.

Nurmi, D.C., Wolski, R., Brevik, J.: Varq: virtual advance reservations for queues. In: Proceedings of the 17th International Symposium on High Performance Distributed Computing, HPDC’08, pp. 75–86. ACM Press, New York (2008). doi:10.1145/1383422.1383433 CrossRef

30.

Jobs, P.: Web page. http://wiki.egee-see.org/index.php/Grid_Interactivity,_Pilot_Jobs,_and_Job_Pooling

31.

Sfiligoi, I.: Making science in the grid world: using glideins to maximize scientific output. In: Nuclear Science Symposium Conference Record, 2007. NSS’07, vol. 2, pp. 1107–1109. IEEE Press, New York (2007) CrossRef

32.

Smith, W., Taylor, V.E., Foster, I.T.: Using run-time predictions to estimate queue wait times and improve scheduler performance. In: Proceedings of the Job Scheduling Strategies for Parallel Processing, IPPS/SPDP’99/JSSPP’99, pp. 202–219. Springer, London (1999). http://portal.acm.org/citation.cfm?id=646380.689540 CrossRef

33.

Snell, Q., Clement, M.J., Jackson, D.B., Gregory, C.: The performance impact of advance reservation meta-scheduling. In: Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, IPDPS’00/JSSPP’00, pp. 137–153. Springer, London (2000). http://portal.acm.org/citation.cfm?id=646381.689675 CrossRef

34.

Tang, X., Chanson, S.T.: Optimizing static job scheduling in a network of heterogeneous computers. In: International Conference on Parallel Processing, p. 373. IEEE Computer Society Press, Los Alamitos (2000). doi:10.1109/ICPP.2000.876153

35.

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)

36.

Tsaregorodtsev, A., Garonne, V., Stokes-Rees, I.: DIRAC: A scalable lightweight architecture for high throughput computing. In: IEEE/ACM International Workshop on Grid Computing, pp. 19–25 (2004) CrossRef

37.

Walker, E., Gardner, J., Litvin, V., Turner, E.: Creating personal adaptive clusters for managing scientific jobs in a distributed computing environment. In: IEEE Workshop on Challenges of Large Applications in Distributed Environments, Paris, France, pp. 95–103 (2006). doi:10.1109/CLADE.2006.1652061

38.

Xie, M., Yun, Z., Lei, Z., Allen, G.: Cluster abstraction: towards uniform resource description and access in multicluster grid. In: International Multi-Symposiums on Computer and Computational Sciences, pp. 220–227 (2007)

39.

Xu, M.: Effective metacomputing using LSF multicluster. In: Proceedings of IEEE International Symposium on Cluster Computing and the Grid(CCGrid01) (2001)

40.

Yoshimoto, K., Kovatch, P.A., Andrews, P.: Co-scheduling with user-settable reservations. In: Proceedings of Job Scheduling Strategies for Parallel Processing (JSSPP), pp. 146–156 (2005) CrossRef

41.

Zhang, Y., Koelbel, C., Cooper, K.: Batch queue resource scheduling for workflow applications. In: IEEE International Conference on Cluster Computing and Workshops (CLUSTER’09), pp. 1–10 (2009). doi:10.1109/CLUSTR.2009.5289186

Titel: DA-TC: a novel application execution model in multicluster systems
verfasst von: Zhifeng Yun
Zhou Lei
Gabrielle Allen
Daniel S. Katz
J. Ramanujam
Publikationsdatum: 01.06.2014
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 2/2014
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-012-0228-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2014

Mvmotion: a metadata based virtual machine migration in cloud

Service models and pricing schemes for cloud computing

Efficient load balancing on biswapped networks

Development of effective pre-visualization authoring tool using conversion technologies—based on film storyboard application

Energy-aware task scheduling in heterogeneous computing environments

CPU/GPU computing for a multi-block structured grid based high-order flow solver on a large heterogeneous system

Premium Partner