Nibedita ADHIKARI, Chitta Ranjan TRIPATHY

Star-crossed cube: an alternative to star graph

This paper introduces a new interconnection network topology called the star-crossed cube (SCQ). The SCQ is observed to be superior to other contemporary networks in terms of various topological parameters such as diameter, cost, average distance, and message traffic density. The various performance metrics of the proposed network, including cost effectiveness and time-cost effectiveness, are found to be better. The optimal routing and broadcasting algorithms for the new network are also presented. Embedding properties for the proposed network are also studied.

Anahtar Kelimeler:

Interconnection networks, topology, traffic density, performance

Star-crossed cube: an alternative to star graph

Keywords:

Interconnection networks, topology, traffic density, performance,

PDF

___

T.Y. Feng, “A survey of interconnection networks”, Computers, Vol. 14, pp. 12–27, 1981.
L.N. Bhuyan, D.P. Agrawal, “Performance of multiprocessor interconnection network”, IEEE Transactions on Computers, Vol. 2, pp. 25–37, 1989.
J.P. Hayes, T.N. Mudge, “Hypercube super-computers”, Proceedings of the IEEE, Vol. 77, pp. 1829–1841, 1989. L.N. Bhuyan, D.P. Agarwal, “Generalized hypercube and hyperbus structures for a computer network”, IEEE Transactions on Computers, Vol. C-33, pp. 323–333, 1984.
Y. Saad, M.H. Schultz, “Topological properties of hypercubes”, IEEE Transactions on Computers, Vol. 37, pp. 867–872, 1988.
K. Efe, “The crossed cube architecture for parallel computation”, IEEE Transactions on Parallel and Distributed Systems, Vol. 3, pp. 513–524, 1992.
S.B. Akers, B. Krishnamurthy, “The fault-tolerance of star graphs”, Proceedings of the International Conference on Supercomputing, pp. 270–282, 1987.
S.B. Akers, D. Harel, B. Krishnamurthy, “The star graph: an attractive alternative to the n-cube”, International Conference on Parallel Processing, pp. 1249–1268, 1987.
C.R. Tripathy, “Star-cube: a new fault tolerant interconnection topology for massively parallel systems”, Journal of The Institution of Engineers (India), ETE Division, Vol. 84, pp. 83–92, 2004.
Y. Li, S. Peng, W. Chu, “Efficient collective communications in dual-cube”, The Journal of Super Computing, Vol. 28, pp. 71–90, 2004.
Y. Li, S. Peng, W. Chu, “Metacube: a new interconnection network for large parallel system”, Australian Computer Science Communications, Vol. 24, pp. 29–36, 2001.
N. Adhikari, C.R. Tripathy, “On a new interconnection network for large scale parallel systems”, International Journal of Computer Applications, Vol. 23, pp. 39–46, 2011.
N. Adhikari, C.R. Tripathy, “Extended crossed cube: an improved fault tolerant interconnection network”, IEEE International Conference on Networked Computing, pp. 86–91, 2009.
S. Latifi, N. Bagherzadeh, “Incomplete star: an incrementally scalable network based on the star graph”, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, pp. 97–102, 1994.
Y. Shi, Z. Hou, J. Song, “Study of general incomplete star interconnection network”, Journal of Computer Science and Technology, Vol. 17, pp. 356–361, 2002.
W. Shi, P.K. Srimani, “Hierarchical star: a new two level interconnection network”, Journal of Systems Architecture. Vol. 51, pp. 1–14, 2005.
H.O. Lee, J.S. Kim, E. Oh, H.S. Lim, “Hyper-star graph: a new interconnection network improving the network cost of the hypercube”, Lecture Notes in Computer Science, pp. 1–8, 2002.
D. Sarkar, “Cost and time cost effectiveness of multiprocessing”, IEEE Transaction on Parallel and Distributed Systems, Vol. 5, pp. 704–712, 1993.
S. Ranka, J. Wang, N. Yeh, “Embedding meshes on the star graph”, Proceedings of the IEEE Conference on Supercomputing, pp. 476–485, 1990.
Q. Dong, X. Yang, J. Zaho, Y.Y. Tang, “Embedding a family of disjoint 3D meshes into a crossed cube”, Journal of Information Sciences, Vol. 178, pp. 2396–2405, 2008.
C.P. Chang, T.Y. Sung, L.H. Hsu, “Edge congestion and topological properties of crossed cube”, IEEE Transactions on Parallel and Distributed Systems, Vol. 11, pp. 64–80, 2000.
E.V. Mendia, D. Sarkar, “Optimal broadcasting on the star graph”, IEEE Transactions on Parallel and Distributed Systems, Vol. 3, pp. 389–396, 1992.