Dynamic load balancing algorithm based on a multi-destination migration mechanism

To reduce the load imbalance in parallel computing, a new dynamic load balancing (DLB) algorithm is proposed. The number of migrated processes that are needed to exchange information between heavily loaded nodes and lightly loaded nodes is included in the DLB messages, and the searching range for lightly loaded nodes is also extended according to the situation. The strategy helps the heavily loaded nodes migrate loads out to multiple destinations in one execution. Moreover, three extra rules are proposed to decrease the route coupling in the course of DLB message transmission. Two typical parallel computing experiments were carried out, including a matrix computation and an evaluation of prime numbers. The performances of four DLB algorithms were compared. The experimental results showed that, compared with the other three DLB algorithms, the proposed DLB algorithm has the least iteration number of executions and could find the most lightly loaded nodes in one execution due to multiple destination migration mechanism, helping it effectively decrease the average response time when a system Is dealing with large scale computation-intensive tasks.