Multi-objective parallel extremal optimization in processor load balancing for distributed programs

The paper concerns multi-objective methodology applied to parallel Extremal Optimization (EO) used in processor load balancing in execution of distributed programs. When load imbalance is detected in executive processors then EO algorithms are used to find best tasks migration leading to imbalance reduction and improvement of program execution time. For this a special multi-objective version of parallel EO is applied. It is based on the EO Guided Search (EO-GS) approach which employs problem knowledge to search for the best next solution state in solution improvement. In this EO version, additional fitness function is used in stochastic selection of next solution state based on computation and communication assessment of task migration targets. In the multi-objective EO approach we jointly control three objectives relevant in processor load balancing for distributed applications. They are: computational load balance in execution of distributed applications, volume of communication between tasks on different processors and task migration parameters which fight imbalance of processor loads. The proposed algorithms are assessed by simulated execution of distributed programs macro data flow graphs.