[1] Liu Bin, Shi Feng, Gao Yujin, et al. Dynamic load balancing based on restricted multicast treein triplet-based hierarchical interconnection network [J]. Journal of Southeast University (English Edition), 2008, 24 (1): 33-37. [doi:10.3969/j.issn.1003-7985.2008.01.008]

Copy

Dynamic load balancing based on restricted multicast treein triplet-based hierarchical interconnection network()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

24

Issue:

2008 1

Page:

33-37

Research Field:

Computer Science and Engineering

Publishing date:

2008-03-30

Info

Title:

Dynamic load balancing based on restricted multicast treein triplet-based hierarchical interconnection network

Author(s):

Liu Bin¹;  2;  Shi Feng¹;  Gao Yujin¹;  Ji Weixing¹;  Song Hong¹

¹School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China
²College of Economics and Management, Hebei University of Science and Technology, Shijiazhuang 050018, China

Keywords:

triplet-based hierarchical interconnection network;  dynamic load balancing;  multicast tree

PACS:

TP311

DOI:

10.3969/j.issn.1003-7985.2008.01.008

Abstract:

To solve the load balancing problem in a triplet-based hierarchical interconnection network(THIN)system, a dynamic load balancing(DLB)algorithm—THINDLBA, which adopts multicast tree(MT)technology to improve the efficiency of interchanging load information, is presented.To support the algorithm, a complete set of DLB messages and a schema of maintaining DLB information in each processing node are designed.The load migration request messages from the heavily loaded node(HLN)are spread along an MT whose root is the HLN.And the lightly loaded nodes(LLNs)covered by the MT are the candidate destinations of load migration; the load information interchanged between the LLNs and the HLN can be transmitted along the MT.So the HLN can migrate excess loads out as many as possible during a one time execution of the THINDLBA, and its load state can be improved as quickly as possible.To avoid wrongly transmitted or redundant DLB messages due to MT overlapping, the MT construction is restricted in the design of the THINDLBA.Through experiments, the effectiveness of four DLB algorithms are compared, and the results show that the THINDLBA can effectively decrease the time costs of THIN systems in dealing with large scale compute-intensive tasks more than others.

References:

[1] Shi Feng, Ji Weixing, Qiao Baojun, et al.A triplet based computer architecture supporting parallel object computing[C]//Proceedings of IEEE the 18th International Conference on Application-Specific Systems, Architectures and Processors.Montreal, Canada, 2007:192-197.
[2] Shi Feng, Ji Weixing, Qiao Baojun, et al.A new non von Neumann architecture TriBA [J].Transactions of Beijing Institute of Technology, 2006, 26(10):847-849.(in Chinese)
[3] Ji Weixing, Shi Feng, Qiao Baojun, et al.Study on an interconnection network for complex embedded systems [J].Chinese High Technology Letters, 2007, 17(9):886-890.(in Chinese)
[4] Dhakal S, Hayat M M, Pezoa J E, et al.Dynamic load balancing in distributed systems in the presence of delays:a regeneration-theory approach [J].IEEE Transactions on Parallel and Distributed Systems, 2007, 18(4):485-497.
[5] Kameda H, Fathy El-Z S, Ryu I, et al.A performance comparison of dynamic vs.static load balancing policies in a mainframe-personal computer network model [C]//Proceedings of the 39th IEEE Conference on Decision and Control.Sydney, 2000:1415-1420.
[6] Yang Ming, Yang Yuanyuan.Constructing minimum cost dynamic multicast trees under delay constraint [C]//Proceedings of the 14th International Conference on Computer Communications and Networks.San Diego, 2005:133-138.
[7] Adjih C, Georgiadis L, Jacquet P, et al.Multicast tree structure and the power law [J].IEEE Transactions on Information Theory, 2006, 52(4):1508-1521.
[8] Lee Busung.Dynamic load balancing in a message passing virtual parallel machine [R].Singapore:Division of Computer Engineering of School of Applied Science of Nanyang Technological University, 1995.
[9] Eager D L, Lazowska E D, Zahorjan J.Adaptive load sharing in homogeneous distributed systems [J].IEEE Transactions on Software Engineering, 1986, 12(5):662-675.
[10] Cortes A, Ripoll A, Senar M A, et al.On the performance of nearest-neighbors load balancing algorithms in parallel systems [C]//Proceedings of the Seventh Euromicro Workshop on Parallel and Distributed Processing.Funchal, 1999:170-177.

Memo

Memo:

Biographies: Liu Bin(1975—), male, graduate, lecturer, geegle@tom.com;Shi Feng(corresponding author), male, doctor, professor, shifengyoujian@tom.com.
Foundation item: The National Natural Science Foundation of China(No.69973007).
Citation: Liu Bin, Shi Feng, Gao Yujin, et al.Dynamic load balancing based on restricted multicast tree in triplet-based hierarchical interconnection network[J].Journal of Southeast University(English Edition), 2008, 24(1):33-37.

Common functions