An improved diffusion algorithm for dynamic load balancing

Abstract Diffusion type algorithms [1, 3, 11] are some of the most popular algorithms for scheduling in dynamic load balancing. It is known however that this type of algorithm can suffer from slow convergence. In this paper the performance of the diffusion type algorithms is improved, while retaining the nearest neighbour communication requirement, through the use of Chebyshev polynomials. It is also proved that both the diffusion algorithm and the improved diffusion algorithm have an optimal property in terms of the amount of load migrated. Numerical results are given comparing the algorithm with the diffusion algorithm as well as a fast algorithm that requires global communication.