Effective processor load balancing using multi-objective parallel extremal optimization

The paper presents how Extremal Optimization can be used in a parallel multi-objective load balancing algorithm applied in execution of distributed programs. Extremal Optimization is used to find task migration which dynamically improves processor load balance in a distributed system. In the proposed multi-objective approach we use three objectives relevant to distributed processor load balancing in execution of program tasks. They are: computational load balance of processors, the volume of inter-processor communication and task migration metrics. In the algorithms additional criteria are used which are based on some knowledge on the influence of the computational and communication loads on task execution. The proposed algorithms are assessed by simulation experiments with distributed execution of program macro data flow graphs. Two methods of finding compromise solutions based on the Pareto front were used: one based on a geometric (Euclidean) distance of solutions and the second one based on the Manhattan (taxicab geometry) distance. The influence of the distance geometry on the final solutions is discussed.