nach oben

Cluster Computing

Erschienen in:

01.09.2015

MOMTH: multi-objective scheduling algorithm of many tasks in Hadoop

verfasst von: Mihaela-Catalina Nita, Florin Pop, Cristiana Voicu, Ciprian Dobre, Fatos Xhafa

Erschienen in: Cluster Computing | Ausgabe 3/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A real challenge sits in front of the business solutions these days, in the context of the big amount of data generated by complex software applications: efficiently using the given limited resources to accomplish specific operations and tasks. Depending on the type of application dealing with, when trying to deliver a certain service in a specific time and with a limited budget, a sequential application may be redesigned in a convenient way so that it will become scalable and able to run on multiple resources. Many task computing model brings together loosely coupled applications, composed of many dependent/independent tasks, which will work together for a common result. When asking for a certain service, the most frequently constraints addressed by the user are deadline and budget. This paper elaborates on a multi-objective scheduling algorithm of many tasks in Hadoop for big data processing, named MOMTH. We consider objective functions related to users and resources in the same time with constraints like deadline (scheduling in due time) and budget. The algorithm evaluation was realized in scheduling load simulator, a tool integrated in Hadoop. MobiWay, a collaboration platform that expose interoperability between a large number of sensing mobile devices and a wide-range of mobility applications, was chosen for performance analysis of MOMTH. We compared the proposed algorithm with first in first out and fair schedulers and we obtained similar performance for our approach.

Vorheriger Artikel Community structure mining in big data social media networks with MapReduce

Nächster Artikel The dispatch time aligning I/O scheduling for parallel file systems

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

Thanks to The scheduling zoo: A searchable bibliography on scheduling by Peter Brucker and Sigrid Knust, http://www-desir.lip6.fr/~durrc/query/.

Abrishami, S., Naghibzadeh, M., Dick, H.J.: Epema. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Gener. Comput. Syst. 29(1):158–169 (2013). Including Special section: AIRCC-NetCoM 2009 and Special section: Clouds and Service-Oriented Architectures

Baptiste, P., Brucker, P., Knust, S., Timkovsky, V.: Ten notes on equal-execution-time scheduling. 4OR, 2:111–127 (2004)

Baptiste, P.: Scheduling equal-length jobs on identical parallel machines. Discret. Appl. Math. 103(1), 21–32 (2000)MathSciNetCrossRefMATH

Baptiste, P.: A note on scheduling multiprocessor tasks with identical processing times. Comput. Oper. Res. 30(13), 2071–2078 (2003)MathSciNetCrossRefMATH

Bart, I.L.: Urban sprawl and climate change: a statistical exploration of cause and effect, with policy options for the EU. Land Use Policy 27(2), 283–292 (2010). Forest transitions Wind power planning, landscapes and publicsCrossRef

Bessis, N., Sotiriadis, S., Pop, F., Cristea, V.: Optimizing the energy efficiency of message exchanging for service distribution in interoperable infrastructures. In: 2012 4th International Conference on Intelligent Networking and Collaborative Systems (INCoS), pp. 105–112 Sept 2012

Bessis, N., Sotiriadis, S., Pop, F., Cristea, V.: Using a novel message-exchanging optimization (meo) model to reduce energy consumption in distributed systems. Simul. Model. Pract. Theory 39(0), 104–120 (2013). S.I.Energy efficiency in Grids and CloudsCrossRef

Błażewicz, J., Liu, Z.: Scheduling multiprocessor tasks with chain constraints. Eur. J. Oper. Res. 94(2), 231–241 (1996)CrossRefMATH

Bourdena, A., Mavromoustakis, C.X., Kormentzas, G., Pallis, E., Mastorakis, G.: A resource intensive traffic-aware scheme using energy-aware routing in cognitive radio networks. Future Gener. Comput. Syst. 39(0), 16–28 (2014). Special Issue on Ubiquitous Computing and Future Communication SystemsCrossRef

10.

Du, J., Leung, J.Y.-T.: Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2(4), 473–487 (1989)MathSciNetCrossRefMATH

11.

Du, J., Leung, J.Y.-T., Young, G.H.: Scheduling chain-structured tasks to minimize makespan and mean flow time. Inf. Comput. 92(2), 219–236 (1991)MathSciNetCrossRefMATH

12.

Dufour, B., Driesen, K., Hendren, L., Verbrugge, C.: Dynamic metrics for java. SIGPLAN Not. 38(11), 149–168 (2003)CrossRef

13.

Durillo, J.J., Nae, V., Prodan, R.: Multi-objective energy-efficient workflow scheduling using list-based heuristics. Future Gener. Comput. Syst. 36(0):221–236 (2014). Special Section: Intelligent Big Data Processing Special Section: Behavior Data Security Issues in Network Information Propagation Special Section: Energy-efficiency in Large Distributed Computing Architectures Special Section: eScience Infrastructure and Applications

14.

EU Parliament. Resolution of 10 september 2013 on promoting a european transport-technology strategy for europe’s future sustainable mobility. http://bit.ly/1vJm2Ho. Oct 2014

15.

Facebook. Under the hood: Scheduling mapreduce jobs more efficiently with corona. http://goo.gl/XW9nD7. Oct 2012

16.

Fan, Y., Wei, W., Gao, Y., Wu, W.: Introduction and analysis of simulators of mapreduce. Trustworthy Comput. Serv. pp 345–350. Springer, (2014)

17.

Garey, M.R., Johnson, D.S.: “Strong” NP-completeness results: motivation, examples, and implications. J. Assoc. Comput. Mach. 25(3), 499–508 (1978)MathSciNetCrossRefMATH

18.

Guo, Z., Fox, G.: Improving mapreduce performance in heterogeneous network environments and resource utilization. In: Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (Ccgrid 2012), CCGRID ’12, pp. 714–716, Washington 2012. IEEE Computer Society

19.

Guo, L., Zhao, S., Shen, S., Jiang, C.: Task scheduling optimization in cloud computing based on heuristic algorithm. J. Netw. 7(3), 547–553 (2012)

20.

Ibrahim, S., Phan, T.-D., Carpen-Amarie, A., Chihoub, H.-E., Moise, D., Antoniu, G.: Governing energy consumption in hadoop through CPU frequency scaling: an analysis. Future Gener. Comput. Syst. http://www.sciencedirect.com/science/article/pii/S0167739X15000060 (2015)

21.

Kc, K., Anyanwu, K.: Scheduling hadoop jobs to meet deadlines. In: Proceedings of the 2010 IEEE Second International Conference on Cloud Computing Technology and Science, CLOUDCOM ’10, pp. 388–392, Washington, DC, USA, 2010. IEEE Computer Society

22.

Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B.: Sequencing and Scheduling: Algorithms and Complexity, Volume 4 of Operations Research and Managment Science. CWI, Amsterdam (1989)

23.

Mavromoustakis, C.X., Dimitriou, C., Mastorakis, G., Bourdena, A., Pallis, E.: Using traffic diversities for scheduling wireless interfaces for energy harvesting in wireless devices. In Resource Management in Mobile Computing Environments, volume 3 of Modeling and Optimization in Science and Technologies, pp 481–496. Springer International Publishing (2014)

24.

Mavromoustakis, C.X., Pallis, E., Mastorakis, G.: Resource Management in Mobile Computing Environments. Springer, Berlin (2014)

25.

Nguyen, P., Simon, T., Halem, M., Chapman, D., Le, Q.: A hybrid scheduling algorithm for data intensive workloads in a mapreduce environment. In: Proceedings of the 2012 IEEE/ACM Fifth International Conference on Utility and Cloud Computing, UCC ’12, pp. 161–167, Washington, DC, USA, 2012. IEEE Computer Society

26.

Nita, M.-C., Chilipirea, C., Dobre, C., Pop, F.: A sla-based method for big-data transfers with multi-criteria optimization constraints for iaas. In: Roedunet International Conference (RoEduNet), 2013 11th, pp 1–6 (2013)

27.

Nita, M.-C., Pop, F., Cristea, V.: Scheduling service with sla assurance for private cloud systems. In: 2012 IEEE International Conference on Intelligent Computer Communication and Processing (ICCP), pp. 331–334, Aug 2012

28.

Pandey, S., Buyya, R.: Scheduling workflow applications based on multi-source parallel data retrieval in distributed computing networks. Comput. J. 55(11), 1288–1308 (2012)CrossRef

29.

Raicu, I., Foster, I.T., Zhao, Y.: Many-task computing for grids and supercomputers. In: Workshop on Many-Task Computing on Grids and Supercomputers, 2008. MTAGS 2008. pp. 1–11 (2008)

30.

Rong, G., Yang, X., Yan, J., Sun, Y., Wang, B., Yuan, C., Huang, Y.: Shadoop: improving mapreduce performance by optimizing job execution mechanism in hadoop clusters. J. Parallel Distrib. Comput. 74(3), 2166–2179 (2014)

31.

Simon, T.A., Nguyen, P., Halem, M.: Multiple objective scheduling of hpc workloads through dynamic prioritization. In: Proceedings of the High Performance Computing Symposium, HPC ’13, pp. 13:1–13:8, San Diego, CA, USA, 2013. Society for Computer Simulation International

32.

Staples, G.: Torque resource manager. In: Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, SC ’06, New York, NY, USA, 2006. ACM

33.

Vasile, M.-A., Pop, F., Tutueanu, R.-I., Cristea, V., Kołodziej, J.: Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Gener. Comput. Syst. http://www.sciencedirect.com/science/article/pii/S0167739X14002532 (2014)

34.

Vavilapalli, V.K., Murthy, A.C., Douglas, C., Agarwal, S., Konar, M., Evans, R., Graves, T., Lowe, J., Shah, H., Seth, S., Saha, B., Curino, C., O’Malley, O., Radia, S., Reed, B., Baldeschwieler, E.: Apache hadoop yarn: Yet another resource negotiator. In: Proceedings of the 4th Annual Symposium on Cloud Computing, SOCC ’13, pp. 5:1–5:16, New York, NY, USA, 2013. ACM

35.

Voicu, C., Pop, F., Dobre, C., Xhafa, F.: Momc: Multi-objective and multi-constrained scheduling algorithm of many tasks in hadoo. In 3PGCIC-2014, The 9-th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing. IEEE Explore Nov 2014

36.

Wang, L., Khan, S.U., Chen, D., Kołodziej, J., Ranjan, R., Xu, C.Z., Zomaya, A.: Energy-aware parallel task scheduling in a cluster. Future Gener. Comput. Syst. 29(7):1661–1670, 2013. Including Special sections: cyber-enabled Distributed Computing for Ubiquitous Cloud and Network Services, Cloud Computing and Scientific Applications—Big Data, Scalable Analytics, and Beyond

37.

Wang, L., von Laszewski, G., Younge, A., He, X., Kunze, M., Tao, J., Cheng, F.: Cloud computing: a perspective study. New Gener. Comput. 28(2), 137–146 (2010)CrossRefMATH

38.

Wang, L., Tao, J., Ranjan, R., Marten, H., Streit, A., Chen, J., Chen, D.: G-hadoop: mapreduce across distributed data centers for data-intensive computing. Future Gener. Comput. Syst. 29(3), 739–750 (2013). Special Section: Recent Developments in High Performance Computing and SecurityCrossRef

39.

Xia, Y., Wang, L., Zhao, Q., Zhang, G.: Research on job scheduling algorithm in hadoop. J. Comput. Inf. Syst. 7(16), 5769–5775 (2011)

40.

Zaharia, M., Konwinski, A., Joseph, A.D., Katz, R., Stoica, I.: Improving mapreduce performance in heterogeneous environments. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI’08, pp. 29–42, Berkeley, CA, USA, 2008. USENIX Association

41.

Zhang, F., Cao, J., Li, K., Khan, S.U., Hwang, K.: Multi-objective scheduling of many tasks in cloud platforms. Future Gener. Comput. Syst. 37(0):309–320 (2014). Special Section: Innovative Methods and Algorithms for Advanced Data-Intensive Computing Special Section: Semantics, Intelligent processing and services for big data Special Section: Advances in Data-Intensive Modelling and Simulation Special Section: Hybrid Intelligence for Growing Internet and its Applications

42.

Zhao, J., Wang, L., Tao, J., Chen, J., Sun, W., Ranjan, R., Kolodziej, J., Streit, A., Georgakopoulos, D.: A security framework in g-hadoop for big data computing across distributed cloud data centres. J. Comput. Syst. Sci. 80(5):994–1007 (2014). cited By (since 1996)0

Titel: MOMTH: multi-objective scheduling algorithm of many tasks in Hadoop
verfasst von: Mihaela-Catalina Nita
Florin Pop
Cristiana Voicu
Ciprian Dobre
Fatos Xhafa
Publikationsdatum: 01.09.2015
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 3/2015
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-015-0454-8

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 3/2015

Hybrid service matchmaking in ambient assisted living environments based on context-aware service modeling

The dispatch time aligning I/O scheduling for parallel file systems

A network approach for managing and processing big cancer data in clouds

A virtualization mechanism for real-time multimedia-assisted mobile food recognition application in cloud computing

GRAPPE : a system for determining optimal connecting route to target person based on mutual intimacy index

Large scale graph processing systems: survey and an experimental evaluation