Dynamic Load Balancing Based on Multi-Objective Extremal Optimization

Ivanoe De Falco³, Eryk Laskowski¹, Richard Olejnik⁴, Umberto Scafuri³, Ernesto Tarantino³, Marek Tudruj^1,2
1Institute of Computer Science PAS, 01-248 Warsaw, Jana Kazimierza 5, Poland {laskowsk,tudruj} @ ipipan waw pl
²Polish-Japanese Institute of Information Technology, ul. Koszykowa 86, 02-008 Warsaw, Poland tudruj @ pjwstk edu pl
³Institute of High Performance Computing and Networking, CNR, Naples, Italy {ivanoe.defalco,umberto.scafuri,ernesto.tarantino} @ icar cnr it
⁴Universit Lille — CRISTAL, CNRS, Lille, France richard.olejnik @ univ-lille1 fr

Abstract: Multi-objective algorithms based on nature-inspired approach of Extremal Optimization (EO) used in distributed processor load balancing have been studied in the paper. EO defines task migration aiming at processor load balancing in execution of graph-represented distributed programs. In the
multi-objective EO approach, three objectives relevant to distributed processor load balancing are simultaneously controlled: the function dealing with the computational load imbalance in execution of application tasks on processors, the function concerned with the communication between tasks
placed on distinct computing nodes and the function related to the task migration number. An important aspect of the proposed multi-objective approach is the method for selecting the best solutions from the Pareto set. Pareto front analysis based on compromise solution approach, lexicographic approach and hybrid approach (lexicographic + numerical threshold) has been performed in dependence on the program graph features, the executive system characteristics and the
experimental setting. The algorithms are assessed by simulation experiments with macro data flow graphs of programs run in distributed systems. The experiments have shown that the multi-objective EO approach included into the load balancing algorithms visibly improves the quality of program execution.

Keywords: load balancing, multi-objective optimization, extremal optimization, program modeling.