The Load Balancing Algorithm for the Star Interconnection Network

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.

• Ahmad M. Awwad
• Jehad Al-Sadi

• Interconnection networks
• Load balancing
• Star network.

[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.