Perfect load balancing on the star interconnection network

被引：0
作者：
N. Imani
H. Sarbazi-Azad
S. G. Akl
机构：
[1] IPM School of Computer Science,
[2] Sharif University of Technology & IPM,undefined
[3] Queens University,undefined
来源：
The Journal of Supercomputing | 2007年 / 41卷
关键词：
Multicomputers; Interconnection networks; Star graph; Load balancing; Hierarchical algorithm; Tree embedding;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3n(n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25n2−3n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms.
引用
收藏
页码：269 / 286
页数：17
相关论文
共 31 条
[1]  
Al-Ayyoub A(2003)Node ranking schemes for the star networks J Parallel Distrib Comput 63 239-250
[2]  
Day K(1996)Embedding an arbitrary binary tree into the star graph IEEE Trans Comput 45 475-481
[3]  
Bagherzadeh N(1996)Balanced spanning trees in complete and incomplete star graphs IEEE Trans Parallel Distrib Syst 7 717-723
[4]  
Dowd M(2005)Optimal broadcasting on incomplete star graph interconnection networks J Syst Architect 51 143-150
[5]  
Nassif N(2002)Diffusion schemes for load balancing on heterogeneous networks Theory Comput Syst 35 305-320
[6]  
Chen TS(2003)An efficient algorithm for perfect load balancing on hypercube multiprocessors J Supercomput 25 5-15
[7]  
Tseng YC(1991)Embedding of cycles and grids in star graphs J Circ Syst Comput 1 43-74
[8]  
Sheu JP(1994)Load balancing, selection, and sorting on the star and pancake interconnection networks Parallel Algorithm Appl 2 27-42
[9]  
Chen TS(2004)Dynamic load balancing by diffusion in heterogeneous systems J Parallel Distrib Comput 64 481-497
[10]  
Wang NC(1996)Two ranking schemes for efficient computation on the star interconnection network IEEE Trans Parallel Distrib Syst 7 321-327
1234