nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Multi-Objective Extremal Optimization in Processor Load Balancing for Distributed Programs

verfasst von : Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek Tudruj

Erschienen in: Parallel Processing and Applied Mathematics

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The paper presents a multi-objective load balancing algorithm based on Extremal Optimization in execution of distributed programs. The Extremal Optimization aims in defining task migration as a means for improving balance in loading executive processors with program tasks. In the proposed multi-objective approach three objectives relevant in processor load balancing for distributed applications are jointly optimized. These objectives include: balance in computational load of distributed processors, total volume of inter-processor communication between tasks and task migration metrics. In the proposed Extremal Optimization algorithms a special approach called Guided Search is applied in selection of a new partial solution to be improved. It is supported by some knowledge of the problem in terms of computational and communication loads influenced by task migration. The proposed algorithms are assessed by simulation experiments with distributed execution of program macro data flow graphs.

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

Vorheriges Kapitel Dynamic Load Balancing Algorithm for Heterogeneous Clusters

Nächstes Kapitel Pardis: A Process Calculus for Parallel and Distributed Programming in Haskell

Boettcher, S., Percus, A.G.: Extremal optimization: methods derived from co-evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999). Morgan Kaufmann, San Francisco, pp. 825–832 (1999)

Barker, K., Chrisochoides, N.: An evaluation of a framework for the dynamic load balancing of highly adaptive and irregular parallel applications. In: Proceedings of the ACM/IEEE Conference on Supercomputing, Phoenix. ACM Press (2003)

De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Load balancing in distributed applications based on extremal optimization. In: Esparcia-Alcázar, A.I. (ed.) EvoApplications 2013. LNCS, vol. 7835, pp. 52–61. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37192-9_6 CrossRef

De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Improving extremal optimization in load balancing by local search. In: Esparcia-Alcázar, A.I., Mora, A.M. (eds.) EvoApplications 2014. LNCS, vol. 8602, pp. 51–62. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45523-4_5

De Falco, I., Laskowski, E., Olejnik, R., Scafuri, U., Tarantino, E., Tudruj, M.: Extremal optimization applied to load balancing in execution of distributed programs. Appl. Soft Comput. 30, 501–513 (2015)CrossRef

Taxicab geometry. https://en.wikipedia.org/wiki/Taxicab_geometry. Accessed 20 Nov 2017

Xu, C., Lau, Francis C.M.: Load Balancing in Parallel Computers: Theory and Practice. Kluwer Academic Publishers, Dordrecht (1997)MATH

Khan, R.Z., Ali, J.: Classification of task partitioning and load balancing strategies in distributed parallel computing systems. Int. J. Comput. Appl. 60(17), 48–53 (2012)

Mishra, M., Agarwal, S., Mishra, P., Singh, S.: Comparative analysis of various evolutionary techniques of load balancing: a review. Int. J. Comput. Appl. 63(15), 8–13 (2013)

10.

Sneppen, K., et al.: Evolution as a self-organized critical phenomenon. Proc. Nat. Acad. Sci. 92, 5209–5213 (1995)CrossRef

11.

Zeigler, B.: Hierarchical, modular discrete-event modelling in an object-oriented environment. Simulation 49(5), 219–230 (1987)CrossRef

12.

Roig, C., Ripoll, A., Guirado, F.: A new task graph model for mapping message passing applications. IEEE Trans. Parallel Distrib. Syst. 18(12), 1740–1753 (2007)CrossRef

13.

Collette, Y., Siarry, P.: Multi-objective Optimization: Principles and Case Studies. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-662-08883-8. p. 293MATH

14.

Ehrgott, M.: Multi-criteria Optimization. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-27659-9. p. 324MATH

15.

Coello Coello, C.A.: Evolutionary multi-objective optimization: a historical view of the field. IEEE Comput. Intell. Mag. 1, 28–36 (2006)CrossRef

16.

Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, Boston (2007). https://doi.org/10.1007/978-0-387-36797-2. p. 800MATH

17.

Chen, M.-R., Lu, Y.-Z.: A novel elitist multi-objective optimization algorithm: multi-objective extremal optimization. Shanghai Jiao Tong University

18.

Ahmed, E., Elettreby, M.F.: On multi-objective evolution model. Int. J. Mod. Phys. C 15(9), 1189–1195 (2004)CrossRef

19.

Gómez-Meneses, P., Randall, M., Lewis, A.: A hybrid multi-objective extremal optimisation approach for multi-objective combinatorial optimisation problems. Bond University, Griffith University, Australia (2010)

20.

Galski, R.L., de Sousa, F.L., Ramos, F.M., Muraoka, I.: Spacecraft thermal design with the generalized extremal optimization algorithm. In: Proceedings of Inverse Problems, Design and Optimization Symposium, Rio de Janeiro, Brazil, 2004

21.

Chen, M., Lu, Y., Yang, G.: Multi-objective extremal optimization with applications to engineering design. J. Zhejiang Univ. Sci. A 8(12), 1905–1911 (2007)CrossRefMATH

22.

De Falco, I., Della Cioppa, A., Maisto, D., Scafuri, U., Tarantino, E.: A multiobjective extremal optimization algorithm for efficient mapping in grids. In: Mehnen, J., Köppen, M., Saad, A., Tiwari, A. (eds.) Applications of Soft Computing. Advances in Intelligent and Soft Computing. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-89619-7_36

Titel: Multi-Objective Extremal Optimization in Processor Load Balancing for Distributed Programs
verfasst von: Ivanoe De Falco
Eryk Laskowski
Richard Olejnik
Umberto Scafuri
Ernesto Tarantino
Marek Tudruj
Verlag: Springer International Publishing
Buch: Parallel Processing and Applied Mathematics
Print ISBN: 978-3-319-78053-5

Electronic ISBN: 978-3-319-78054-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78054-2_17

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"