Dynamic Load Balancing Based on Multi-Objective Extremal optimization

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 multiobjective 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.