Extremal optimization with guided state changes in load balancing of distributed programs

The paper concerns methods for using ExtremalOptimization (EO) for processor load balancing during executionof distributed programs. A load balancing algorithm for clustersof multicore processors is presented and discussed. In thisalgorithm the EO approach is used to periodically detect thebest tasks as candidates for migration and for a guided selectionof the best processors to receive the migrated tasks. To decreasethe complexity of selection for migration, we propose a guidedEO algorithm which assumes a two step stochastic selectionduring the solution improvement based on two separate fitnessfunctions. The functions are based on specific program modelswhich estimate relations between the programs and the executivehardware. The proposed load balancing algorithm is assessedby experiments with simulated load balancing of distributedprogram graphs. The algorithm is compared against an EO - based algorithm with random placement of migrated tasks anda classic genetic algorithm. © 2014 IEEE.