衡过程，充当类似集中式策略中央节点的功能。第i层的根处理器参与由第i+1层(层的序号由底至上递增)的头节点控制的负载均衡过程，但第i层各节点的子节点不参与第i+1层的负载均衡过程。与HBM不同的是，HybridLB可在不同的层采用不同的策略，并最小化任务传输的距离和数量以优化负载均衡的通讯开销[22]。

论文[22]中列举以上三种调度常用算法和算法性能比较，此处不再详述。

4 总结

本文通过负载均衡技术分类方式、负载均衡技术和负载均衡算法三个方面对负载均衡做了介绍。其中，DLB(动态负载均衡)是现在应用最广泛的一种方式，随着新兴的多/众核相关技术和应用的出现及进一步发展，DLB技术的重要性日益凸显。但是现有的动态负载平衡算法不尽完善，比如有些DLB算法每次运行只选择一个符合条件( 负载最轻[23]、距离最近[24]、其他约束条件[25]) 的轻载节点作为负载迁移的目标节点，负载迁移后, 若重载节点仍过载，则再次运行算法，直至负载平衡，增加了负载平衡的时空开销和系统对任务的平均响应时间。针对此问题，论文[26]中将多个轻载节点作为负载迁移目标节点的多目标迁移机制，对DLB的性能做了改善。未来对于DLB研究主要集中在以下几个层面：在系统层次上，通过考虑拓扑结构来优化通讯可提高DLB 策略的性能[27, 28, 29, 30]；在节点组层面上进行通讯开销优化：考虑到节点内的通讯速度远快于节点间通讯的事实[31]，研究如何将更多的节点间通讯密集的任务划分到同一节点内可进一步优化通讯性能；在节点层面上研究细粒度划分与数据依赖性对性能的影响，设计适应于统一多核计算模型和异构体系结构的负载均衡策略来提高策略的计算性能、可扩展性和可移植性，为提高并行性引入的同步开销代价大于收益以及计算具有较大粒度并行性和依赖度的问题时，需要多少处理器节点才是恰当的等问题。

致谢 在此，感谢给予本文支持的所有著作的作者，尤其要感谢南京大学软件学院葛季栋副教授对本论文的指导。

References:

[1] Liu XH. Research on Load Balancing Technology. Science & Technology Information, 2007, No12:173~174(in Chinese with

English abstract).

[2] Sun JC, Zhang LB, Chi XB, eds. Network parallel computing and distributed programming environment. Beijing: Science press,

2003.30~36.

[3] Xue J, Li ZZ, Wang YL. The development of load balancing [J]. Mini micro computer system, 2003, 24(12):2100~2103.

[4] Xiao JB, Wang Y. Application of DNS to achieve load balancing Web cluster service [J]. Computing Systems, 2003(10):59~62.

[5] Hu ZA, Wang L. The relationship between Algorithm, network topology with scheduling frequency and dynamic load balancing

[J].Computer engineering and science,2000,22(1):104~107.

[6] Yin F. Distributed system dynamic load distribution algorithm research [J].Microcomputer information, 2009 (18): 91~93.

[7] Wang S, Xiu BX, Xiao WD. The Web server cluster load balancing algorithms [J]. Computer engineering, 2004, 40(25):78~80.

[8] Dahlin M.Interpreting Stale Load Information[C].In: Proc of the 19th Intl Conf on Distributed Computing Systems, 1999-05.

[9] Mitzenmacher M.How Useful is Old Information[C].In: Proc of the 15th Annual ACM.

[10] Mao M, Pan J. Dynamic Load Balancing Self-adapting Algorithm in Multi-Processor Systems and Its Improvements [J]. Power of

intelligence, 2002(2): 55~58.

[11] Zhu SP. A new way of dynamic load balancing algorithm design [J]. Computer engineering, 1995,16(3):26~28.

[12] Hesham El-Rewini, Theodore G Lewis, Hesham H Ali. Task scheduling. Englewood Cliffs, New Jersey: PTR Prentice Hall, 1994.

[13] Joosen W, Pollet J.The efficient management of task clusters in a dynamic load balancer. In: Proceedings of the International

Conference'94 on Parallel Distributed Systems. Hsinchu, Taiwan, Dec. 1994. 19~21.

[14] Feng MD, Yuen CK. Dynamic load balancing on a distributed system. In: Proceeding s of the 6th Symposium on Parallel and

Distributed Processing. Dallas, Texas, Oct. 1994. 26~29.

[15] Gene Eu Jan, Ming-Bo Lin. Effective load balancing on highly parallel multicomputers based on super concentrators. In:

Proceedings of the International Conference'94 on Parallel Distributed Systems. Hsinchu, Taiwan, Dec. 1994. 19~21.