A Genetic Exploration of Dynamic Load Balancing Algorithms

Abstract

Evolutionary algorithms provide ways to explore wide search spaces. Thus, it is possible to get some conclusions about the characteristics of these spaces in order to aid in the determination of the best alternatives to solve the problem at hand. We have applied a genetic algorithm to assess the problem of distributed load balancing in parallel processing. To do that, we propose a classification of the space of design of distributed load balancing algorithms that takes into account the different alternatives for each dimension of the algorithm. This classification allows the codification of each load balancing strategy, thus making possible to apply a genetic search to determine the distributed load balancing procedure that provides the best performance for the type of parallel application at hand and the parallel platform where it is implemented. As an example, in this paper we provide the results corresponding to the parallel multiplication of matrices implemented in a cluster.