The Load Balancing Algorithm for the Star Interconnection Network

Authors: Ahmad M. Awwad, Jehad Al-Sadi

Abstract:

The star network is one of the promising interconnection networks for future high speed parallel computers, it is expected to be one of the future-generation networks. The star network is both edge and vertex symmetry, it was shown to have many gorgeous topological proprieties also it is owns hierarchical structure framework. Although much of the research work has been done on this promising network in literature, it still suffers from having enough algorithms for load balancing problem. In this paper we try to work on this issue by investigating and proposing an efficient algorithm for load balancing problem for the star network. The proposed algorithm is called Star Clustered Dimension Exchange Method SCDEM to be implemented on the star network. The proposed algorithm is based on the Clustered Dimension Exchange Method (CDEM). The SCDEM algorithm is shown to be efficient in redistributing the load balancing as evenly as possible among all nodes of different factor networks.

Keywords: Interconnection networks, Load balancing, Star network.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1337916

References:

[1] S. B. Akers, D. Harel and B. Krishnamurthy, “The Star Graph: An Attractive Alternative to the n-Cube” Proc. Intl. Conf. Parallel Processing, 1987, pp. 393-400.
[2] K. Day and A. Tripathi, “A Comparative Study of Topological Properties of Hypercubes and Star Graphs”, IEEE Trans. Parallel & Distributed Systems, vol. 5.
[3] Kaled Day and Abdel-Elah Al-Ayyoub, “Node-ranking schemes for the star networks”, Journal of parallel and Distributed Computing, Vol. 63 issue 3, March 2003, pp 239-250.
[4] B.A. Mahafzah and B.A. Jaradat, “The Load Balancing problem in OTIS-Hypercube Interconnection Network”, J. of Supercomputing (2008) 46, 276-297.
[5] S. B. Akers, and B. Krishnamurthy, “A Group Theoretic Model for Symmetric Interconnection Networks,” Proc. Intl. Conf. Parallel Proc., 1986, pp. 216-223.
[6] K. Day and A. Al-Ayyoub, “The Cross Product of Interconnection Networks”, IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 2, Feb. 1997, pp. 109-118.
[7] A. Al-Ayyoub and K. Day, “A Comparative Study of Cartesian Product Networks”, Proc. of the Intl. Conf. on Parallel and Distributed Processing: Techniques and Applications, vol. I, August 9-11, 1996, Sunnyvale, CA, USA, pp. 387-390.
[8] I. Jung and J. Chang, “Embedding Complete Binary Trees in Star Graphs,” Journal of the Korea Information Science Society, vol. 21, no. 2, 1994, pp. 407-415.
[9] Berthome, P., A. Ferreira, and S. Perennes, “Optimal Information Dissemination in Star and Panckae Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 12, Aug. 1996, pp. 1292-1300.
[10] P. Fragopoulou and S. Akl, “A Parallel Algorithm for Computing Fourier Transforms on the Star Graph,” IEEE Trans. Parallel & Distributed Systems, vol. 5, no. 5, 1994, pp. 525-31.
[11] Mendia V. and D. Sarkar, “Optimal Broadcasting on the Star Graph,” IEEE Trans. Parallel and Distributed Systems, Vo;. 3, No. 4, 1992, pp. 389-396.
[12] S. Rajasekaran and D. Wei, “Selection, Routing, and Sorting on the Star Graph,” J. Parallel & Distributed Computing, vol. 41, 1997, pp. 225-33.
[13] S. Lakshmivarahan, and S.K. Dhall, “Analysis and Design of Parallel Algorithms Arithmetic and Matrix Problems,” McGraw-Hill Publishing Company, 1990.
[14] N. Imani et al, “Perfect load balancing on star interconnection network”, J. of supercomputers, Volume 41 Issue 3, September 2007. pp. 269 – 286.
[15] Jehad Al-Sadi, “Implementing FEFOM Load Balancing Algorithm on the Enhanced OTIS-n-Cube Topology”, Proc. of the Second Intl. Conf. on Advances in Electronic Devices and Circuits - EDC 2013, 47-5.
[16] K. Day and A. Al-Ayyoub, “The Cross Product of Interconnection Networks”, IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 2, Feb. 1997, pp. 109-118.
[17] Ranka, Y. Won, S. Sahni, “Programming a Hypercube Multicomputer”, IEEE Software, 5 (5): 69 – 77, 1998.
[18] Zhao C, Xiao W, Qin Y (2007), “Hybrid diffusion schemes for load balancing on OTIS networks”, In: ICA3PP, pp 421–432
[19] G. Marsden, P. Marchand, P. Harvey, and S. Esener, “Optical Transpose Interconnection System Architecture,” Optics Letters, 18(13), 1993, pp. 1083-1085.
[20] Qin Y, Xiao W, Zhao C (2007), “GDED-X schemes for load balancing on heterogeneous OTIS networks”, In: ICA3PP, pp 482–492.
[21] A. Menn and A.K. Somani, “An Efficient Sorting Algorithm for the Star Graph Interconnection Network,” Proc. Intl. Conf. on Parallel Processing, 1990, pp.1-8.