A distributed diffusion method for dynamic load balancing on parallel computers

Parallel applications can be divided into tasks that can be executed simultaneously in different processors. Depending on prior knowledge about computational requirements of the problem, the assignment of tasks to processors can be guided in two ways: static and dynamic. We propose a new dynamic load balancing algorithm based on the diffusion approach which employs overlapping balancing domains to achieve global balancing. Since current diffusion methods consider discrete units, the algorithms may produce solutions which, although they are locally balanced prove to be globally unbalanced. Our method solves this problem taking into account the load maximum difference between two processors within each domain, providing a more efficient load balancing process