摘要：

针对环与线性阵列的负载平衡速度较慢与迁移量较大的问题，提出一种贪心线性推移平衡算法。该算法适用于任何具有哈密尔顿通路的图结构网络。其平衡过程的负载迁移量一般不大，平衡负载速度较快。对二维网状网等网络结构的贪心线性推移平衡算法进行改进，得到分二阶段的贪心线性推移平衡算法。实验结果表明，此类改进在平衡条件减弱时能较大地提高算法的时间性能。

关键词: 负载平衡, 互连网络, 任务调度, 异构系统, 负载迁移

Abstract:

Greedy linear shift balancing algorithm is presented for ring or linear array to reduce balancing time and the amount of the transferred load. The algorithm can be used for balancing any system in which internetwork contains at least one Hamilton path. It need not a large amount of load transferred among nodes or a large amount of the consumed time. In addition, two-stage greedy linear shift balancing algorithm is presented to improve the greedy linear shift balancing algorithm for mesh etc. Experimental results show that the two-stage linear shift balancing algorithm can reduce execution time when the balancing condition is weaken.

Key words: load balance, interconnection network, task scheduling, heterogeneous system, load transfer

中图分类号: 

• TP311