Improving Extremal Optimization in Load Balancing by Local Search

Ivanoe De Falco 1 Eryk Laskowski 2 Richard Olejnik 3 Umberto Scafuri 1 Ernesto Tarantino 1 Marek Tudruj 2, 4
1 ICAR - Institute of High Performance Computing and Networking
2 Institute of Computer Science [Warszawa]
3 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
4 PJIIT - Polish-Japanese Institute of Information Technology
Abstract : The paper concerns the use of Extremal Optimization (EO) technique in dynamic load balancing for optimized execution of distributed programs. EO approach is used to periodically detect the best candidates for task migration leading to balanced execution. To improve the quality of load balancing and decrease time complexity of the algorithms, we have improved EO by a local search of the best computing node to receive migrating tasks. The improved guided EO algorithm assumes a two-step stochastic selection based on two separate fitness functions. The functions are based on specific program models which estimate relations between the programs and the executive hardware. The proposed load balancing algorithm is compared against a standard EO-based algorithm with random placement of migrated tasks and a classic genetic algorithm. The algorithm is assessed by experiments with simulated load balancing of distributed program graphs and analysis of the outcome of the discussed approaches.
Keywords : Distributed program design Extremal optimization Load balancing
Type de document :
Article dans une revue
Lecture notes in computer science, springer, 2014, Applications of Evolutionary Computation, 8602, pp.12. 〈10.1007/978-3-662-45523-4_5〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01243170
Contributeur : Richard Olejnik <>
Soumis le : lundi 14 décembre 2015 - 15:56:13
Dernière modification le : mardi 3 juillet 2018 - 11:48:08

Identifiants

Collections

CRISTAL-EMERAUDE | CRISTAL | INRIA

Citation

Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, et al.. Improving Extremal Optimization in Load Balancing by Local Search. Lecture notes in computer science, springer, 2014, Applications of Evolutionary Computation, 8602, pp.12. 〈10.1007/978-3-662-45523-4_5〉. 〈hal-01243170〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

150

Contact


archive-ouverte@inria.fr