计算机工程 ›› 2010, Vol. 36 ›› Issue (20): 90-92.doi: 10.3969/j.issn.1000-3428.2010.20.032

• 软件技术与数据库 • 上一篇    下一篇

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

吴荣腾   

  1. (闽江学院计算机科学系,福州 350108)
  • 出版日期:2010-10-20 发布日期:2010-10-18
  • 作者简介:吴荣腾(1971-),男,博士,主研方向:并行分布式计算,计算机网络
  • 基金项目:

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

Greedy Linear Shift Load Balance Algorithm

WU Rong-teng   

  1. (Department of Computer Science, Minjiang University, Fuzhou 350108, China)
  • Online:2010-10-20 Published:2010-10-18

摘要:

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

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

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

中图分类号: