贪心线性推移负载平衡算法  

Greedy Linear Shift Load Balance Algorithm

作　　者：吴荣腾[1] 

机构地区：[1]闽江学院计算机科学系,福州350108

出　　处：《计算机工程》2010年第20期90-92,105,共4页Computer Engineering

基　　金：福建省教育厅A类基金资助项目(JA09187);闽江学院启动基金资助项目(YKQ08002)

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]