多目标迁移机制的动态负载平衡算法

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

针对并行计算中的负载失衡现象,提出一种新型动态负载平衡算法,将重载节点和轻载节点间需要交流的进程数目信息包括在负载平衡消息中,并视情况扩展目标节点的搜索范围,使重载节点能在算法的一次执行中外迁进程到多个目标节点,还提出3条规则以减少消息传播的路由耦合现象.通过矩阵运算和求素数这2个典型的并行计算实验,比较了4种动态负载平衡算法的性能.结果表明,提出的算法因多目标迁移机制而具有最少的迭代执行次数,并能在一次执行中发现最多的轻载节点,有效缩减了系统对计算密集型任务的平均响应时间.

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.