Login Register Cart 0
Generic placeholder image

Recent Advances in Electrical & Electronic Engineering

Editor-in-Chief

ISSN (Print): 2352-0965
ISSN (Online): 2352-0973

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

A Survey of Multistage Interconnection Networks

Author(s): Amit Prakash, Dilip K. Yadav* and Arvind Choubey

Volume 13, Issue 2, 2020

Page: [165 - 183] Pages: 19

DOI: 10.2174/1872212113666190215145815

Price: $65

Abstract

Background: Multistage interconnection networks are being used in computer and communications. Multiprocessor architectures for parallel computing exercise these interconnection networks for connecting various processing elements and transfer data between sub-systems of a digital system. The vast diversity of the field poses an obstacle to realize different kinds of interconnection networks and their relationship.

Methods: This paper consists of an extensive survey of multistage interconnection networks.

Results: A broad classification of multistage interconnection networks based on network functionality, reliability and fault tolerance is presented in order to emphasize the important principles which differentiate the network architectures. For each class of network, significant results are given and the basic design principles are explained.

Conclusion: The various multistage interconnection networks design provide high performance, availability, throughput, lower latency, less power consumption along with improved fault-tolerance and reliability. However, there is a rising demand for new fault-tolerant and reliable multistage interconnection networks.

Keywords: Crossbar, network topology, interconnection network, multistage, fault-tolerance, reliability.

« Previous Next »
Graphical Abstract

[1]
A. Pattavina, Switching theory: Architecture and performance in broadband ATM networks., John Wiley & Sons Ltd, pp. 53-54. 1998
[2]
J. Siegel, Interconnection networks for large-scale parallel processing: Theory and case studies.2nd Edition, McGraw-Hill, Inc.,United States: N.P.,, 1985
[3]
N. Peter, Thesis on fast packet switching for integrated services.Wolfson College University of Cambridge, 1988
[4]
"M.A.-E.-Barr", Design and analysis of reliable and fault-tolerant computer systems.. London: Imperial College Press, 2007
[5]
E.H. Rewini, and A.E.M. Barr, Adv. Comput. Architec. Parall. Process., John Wiley, 2005.
[6]
T. Lang, and H.S. Stone, "A shuffle-exchange network with simplified control", IEEE Trans. Comput., vol. 25, no. 1, pp. 55-65, 1976.
[7]
D.H. Lawrie, "Access and alignment of data in an array processor", IEEE Trans. Comput., vol. 24, no. 12, pp. 1154-1155, 1975.
[8]
J.H. Patel, "Processor-memory interconnection for multiprocessors", In: Proceedings of 6th Annual Symposium on Computer Architecture, 1979, pp. 168-177.
[9]
J. Duato, S. Yalamanchili, and L. Ni, “Interconnection networks: An engineering approach”, Morgan Kaufmann Publishers., Revised Printing, 2003.
[10]
I.R. Quadri, P. Boulet, and J.L. Dekeyser, Modeling of topologies of interconnection networks based on multidimensional multiplicity.HAL [Research Report] ‹inria-00149527v1›, 2007
[11]
L.R. Goke, and G.J. Lipovski, "Banyan networks for partitioning multiprocessor systems", In: Proceedings of 6th Annual Symposium on Computer Architecture, 1973, pp. 21-28.
[12]
C. Clos, "A study of non-blocking switching networks", Bell Syst. Tech, vol. 32, no. 2, pp. 406-424, 1953.
[13]
F. Bistouni, and M. Jahanshahi, "Scalable crossbar network: A non-blocking interconnection network for large-scale systems", J. Supercomput., vol. 71, no. 2, pp. 697-728, 2015.
[14]
V.E. Beneš, On rearrangeable three-stage connecting networks'.Bell. Syst.Tech.,, Vol. 41, no. 5, 1962.
[15]
D. Nassimi, and S. Sahni, A self-routing Beneš network and parallel permutation algorithms. IEEE Trans. Comput.,, 1981
[16]
G.B. Adams III, D.P. Agrawal, and H.J. Siegel, A survey and comparison of fault-tolerant multistage interconnection networks., IEEE Comput, 1987.
[17]
G.M. Masson, G.C. Gingher, and S. Nakamura, A sampler of circuit switching networks computer., IEEE Comput. Soc. Press: Los Alamitos, CA, USA, 1979.
[18]
G.B. Adams III, and H.J. Siegel, "A survey of fault-tolerant multistage networks and comparison to the extra stage cube", In: 17th Annual Hawaii International Conference on System Sciences, 1984.
[19]
M. Jeng, and H.J. Siegel, "A fault-tolerant multistage interconnection networks for multiprocessor systems using dynamic redundancy", In: 6th International Conference, Distributed Computing Systems, Computer Society Press, 1986.
[20]
T. Feng, A survey of interconnection networks.IEEE Comput.Mag.,, Vol. 14, no. 12, 1981
[21]
R. Mittal, D. Cherian, and P.J. Mohan, "Routing and performance of the double tree (DOT) network", IEEE Proceedings on Computers and Digital Techniques,. Vol. 142, no. 2, 1995.
[22]
R.J. McMillen, and H.J. Siegel, "Performance and fault tolerance improvements in the inverse augmented data manipulator network", In: 9th Symposium on Computer Architecture. ACM SIGARCH Computer Architecture News, , 1982
[23]
D. Malhotra, and R. Aggarwal, "Performance analysis of fault-tolerant irregular MINs", In: Proceedings of National Conference on Challenges and opportunities in Information Technologies (COIT-2007). RIMT-IET: 81-87, 2007.
[24]
P.K. Bansal, K. Singh, and R.C. Joshi, "Quad tree: A cost-effective fault-tolerant multistage interconnection network", Inter. Conf. IEEE INFOCOM. 1991
[25]
K.K. Cheema, and R. Aggarwal, "Design scheme and performance evaluation of a new fault-tolerant multistage interconnection network", Inter. J. Comput. Sci. Netw. Secur.. 2009
[26]
F. Bistouni, and M. Jahanshahi, "Scalable crossbar network: A non-blocking interconnection network for large-scale systems", J. Supercomput., 2014.
[27]
Nitin S. Garhwal., and N. Srivastava, "Designing a fault-tolerant fully-chained combining switches multi-stage interconnection network with disjoint paths", J. Supercomput., vol. 55, no. 3, pp. 400-431, 2011.
[28]
K.Y. Lee, and H. Yoon, "The PM22I interconnection network", IEEE Trans. Comput., vol. 38, no. 2, 1989.
[29]
K.Y. Lee, and W. Hegazy, "The extra stage gamma network", IEEE Trans. Comput., vol. 37, no. 11, 1988.
[30]
K.Y. Lee, and H. Yoon, "The B-network: A multistage interconnection network with backward links", IEEE Trans. Comput., vol. 39, no. 7, 1990.
[31]
C.W. Chen, N.P. Lu, T.F. Chen, and C.P. Chung, "Fault-tolerant gamma interconnection networks by chaining", IEEE Proc. Comput.Dig.Tech., . Vol. 147, no. 2, 2000.
[32]
R. Venkatesan, and H.T. Mouftah, "Balanced gamma network-A new candidate for broadband packet switch architectures", In: Proceedings-IEEE INFOCOM '92: The Conference on Computer Communications.Florence, Italy 1992
[33]
C.W. Chen, N.P. Lu, and C.P. Chung, "3 disjoint gamma interconnection networks", J. Syst. Softw., vol. 66, no. 2, 2003.
[34]
M.A. Borkar, "3D-CGIN: 3 disjoint paths CGIN with alternate source", Proc. Adv. Comput. Commun.,. 2011
[35]
S. Rajkumar, and N.K. Goyal, "Design of 4-disjoint gamma interconnection network layouts and reliability analysis of gamma interconnection networks", J. Supercomput., vol. 69, no. 1, pp. 468-491, 2014.
[36]
F. Bistouni, and M. Jahanshahi, "Improved extra group network: A new fault-tolerant multistage interconnection network", J. Supercomput., 2014.
[37]
F. Bistouni, and M. Jahanshahi, "“Pars network: A multistage interconnection network with fault-tolerance capability", J. Parall. Distrib.Comput.. 2014
[38]
M. Abd-El-Barr, K. Al-Tawil, H. Youssef, and T. Al-Jarad, "RAZAN: A high-performance switch architecture for ATM networks", Int. J. Commun. Syst., vol. 11, no. 4, pp. 275-285, 1998.
[39]
S. Rajkumar, and N.K. Goyal, "Fault tolerant interconnection network design’", IETE Tech. Rev., vol. 33, no. 4, pp. 396-404, 2016.
[40]
M. Jahanshahi, and F. Bistouni, "Improving the reliability of the Benes network for use in large-scale systems", Microelectron. Reliab., vol. 55, no. 3-4, pp. 679-695, 2015.
[41]
"G. Khanna, R. Mishra and S.K. Chaturvedi, “4DGIN-3: A new design Layout of 4-disjoint gamma interconnection network”,", J.parallel distrib. comput.,. VOL. 98, PP. 40-47, 2016.

Rights & Permissions Print Cite
Article Metrics
7
1
© 2024 Bentham Science Publishers | Privacy Policy