Parallel extremal optimization in processor load balancing for distributed applications

Abstract : The paper concerns parallel methods for extremal optimization (EO) applied in processor load balancingin execution of distributed programs. In these methods EO algorithms detect an optimized strategy oftasks migration leading to reduction of program execution time. We use an improved EO algorithmwith guided state changes (EO-GS) that provides parallel search for next solution state during solutionimprovement based on some knowledge of the problem. The search is based on two-step stochasticselection using two fitness functions which account for computation and communication assessment ofmigration targets. Based on the improved EO-GS approach we propose and evaluate several versions ofthe parallelization methods of EO algorithms in the context of processor load balancing. Some of them usethe crossover operation known in genetic algorithms. The quality of the proposed algorithms is evaluatedby experiments with simulated load balancing in execution of distributed programs represented as macrodata flow graphs. Load balancing based on so parallelized improved EO provides better convergence ofthe algorithm, smaller number of task migrations to be done and reduced execution time of applications.
Type de document :
Article dans une revue
Applied Soft Computing, Elsevier, 2016, 46, pp.16. 〈Elsevier〉. 〈10.1016/j.asoc.2016.04.033〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01384618
Contributeur : Richard Olejnik <>
Soumis le : jeudi 20 octobre 2016 - 11:35:11
Dernière modification le : vendredi 13 avril 2018 - 01:27:44

Identifiants

Collections

Citation

Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, et al.. Parallel extremal optimization in processor load balancing for distributed applications. Applied Soft Computing, Elsevier, 2016, 46, pp.16. 〈Elsevier〉. 〈10.1016/j.asoc.2016.04.033〉. 〈hal-01384618〉

Partager

Métriques

Consultations de la notice

97