A Hybrid Efficient Load Balancing Algorithm on Biswapped Network
TONG Chao-nan, SUN Li-ting
1. School of Automation, University of Science and Technology Beijing, Beijing 100083, China;
2. Key Laboratory of Advanced Control of Iron and Steel Process (Ministry of Education), Beijing 100083, China
Abstract：In view of the large hierarchical Network Biswapped Network(BSN),paper suggests a simple and effective load balancing strategy CDE-X.This new scheme overcomes the unworthiness of the large-scale hierarchical network's traditional scheme in which the calculation of the complex high order Laplacian matrix's eigenvalues.In the new method,most load balancing iterations are carried out in the factor network,therefore,CDE-X only needs to know the factor network's structure and the Laplacian eigenvalues,which improves the iterative convergence speed in the process of iterative balancing,and reduces the calculation complexity of the flows,and reduce the communication flows.According to the comparison theory,CDE-X not only reduces the computational complexity,but also reduces the iteration steps,which is more simple and effective than the traditional strategy X,and more applicable to the large scale hierarchical network BSN.
[1] 蒋江,张民选,廖湘科.基于多种资源的负载均衡算法的研究[J].电子学报,2002,30(8):1148-1152. Jiang Jiang,Zhang Min-xuan,Liao Xiang-ke.Study on load balancing algorithms based on multiple resources[J].Acta Electronica Sinica,2002,30(8):1148-1152.(in Chinese)[2] 杨际祥,谭国真,王荣生.并行与分布式计算动态负载均衡策略综述[J].电子学报,2010,38(5):1122-1130. Yang Ji-xiang,Tan Guo-zhen,Wang Rong-sheng.A survey of dynamic load balancing strategies for parallel and distributed computing[J].Acta Electronica Sinica,2010,38(5):1122-1130.(in Chinese)[3] Cybenko George.Dynamic load balancing for distributed memory multiprocessors.Journal of Parallel and Distributed Computing,1989,7(2):279-301.[4] Muthukrishnan S,Ghosh Bhaskar,Schultz Martin H.First and second order diffusive methods for rapid,coarse,distributed load balancing[A].Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures,1996[C].USA:Springer-Verlag,1996.[5] Ralf Diekmann,Andreas Frommer,Burkhard Monien.Efficient schemes for nearest neighbor load balancing[J].Parallel Computing,1999,25(7):789-812.[6] Robert Elsasser,Andreas Frommer,Burkhard Monien,et al.Optimal and alternating-direction load balancing schemes[A].Proceedings of Euro-Par'99,1999[C].Berlin:Springer-Verlag,1999.[7] Robert Elsasser,Burkhard Monien,Robert Preis.Diffusive load balancing schemes on heterogeneous networks[A].Proceedings of twelfth ACM Symposium on Parallel Algorithms and Architectures,2000[C].New York:ACM,2000.[8] Rotaru Tiberiu,Negeli Hans-Heinrich.Dynamic load balancing by diffusion in heterogeneous systems[J].Journal of Parallel and Distributed Computing,2004,64(4):481-97.[9] 杨际祥,谭国真,王凡,等.一种大规模分布式负载均衡策略[J].电子学报,2012,40(11):2226-2231. Yang,Ji-xiang,Tan Guo-zhen,Wang Fan,et al.A load balancing strategy for large-scale distributed computing[J].Acta Electronica Sinica,2012,40(11):2226-2231.(in Chinese)[10] Parhami Behrooz.Swapped interconnection networks:Topological,performance,and robustness attributes[J].Journal of Parallel and Distributed Computing,2005,65(11):1443-1452.[11] Chen Wei-dong,Xiao Wen-jun,Parhami Behrooz.Swapped(OTIS)networks built of connected basis networks are maximally fault tolerant[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(3):361-366.[12] 陈卫东,肖文俊.Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性[J].计算机学报,2010,33(5):822-832. Chen Wei-dong,Xiao Wen-jun.Topological properties of biswapped networks(BSNs):node symmetry and maximal fault tolerance[J].Chinese Journal of Computers,2010.33(5):822-832.(in Chinese)[13] Xiao Wen-jun,Chen Wei-dong,He Ming-xin,et al.Biswapped networks and their topological properties[A]. Proceedings of Eighth ACIS International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,2007[C].Qingdao:Inst of Elec and Elec Eng Computer Society,2007.[14] Arndt,H.Load balancing:dimension exchange on product graphs[A].Proceedings of eighteenth International Parallel and Distributed Processing Symposium,2004[C].Los Alamitos:IEEE Comput Soc,2004.[15] Holger Arndt.On finite dimension exchange algorithms[J].Linear Algebra and Its Applications,2004,380:73-93.
2013, Vol. 41 
