Abstract
Supersystems are shown to provide enough computational power to solve complex problems on a real-time basis. In all these systems, the computational parallelism is obtained from multiple processors. Multistage interconnection networks (MINs) play a vital role on the performance of these multiprocessor systems. This paper introduces a new fault-tolerant MIN named as improved extra group network (IEGN). IEGN is designed by existing extra group (EGN) network, which is a regular multipath network with limited fault tolerance. IEGN provides four times more paths between any source–destination pairs compared with EGN. The performance of IEGN has been evaluated in terms of permutation capability, fault tolerance, reliability, path length, and cost. It has also been proved that the IEGN can achieve better results in terms of fault tolerance, reliability, path length and cost-effectiveness, in comparison to known networks, namely, EGN, augmented baseline network, augmented shuffle-exchange network, fault-tolerant double tree, Benes network, and Replicated MIN.
Similar content being viewed by others
Abbreviations
- IN:
-
Interconnection network
- MIN:
-
Multistage interconnection network
- IEGN:
-
Improved extra group network
- EGN:
-
Extra group network
- ABN:
-
Augmented baseline network
- ASEN:
-
Augmented shuffle-exchange network
- MABN:
-
Modified augmented baseline network
- FDOT:
-
Fault-tolerant double tree network
- PCT:
-
Perfect connection techniques
- BP:
-
Basic path
- MP:
-
Main path
- AP:
-
Auxiliary path
- SE:
-
Switching element
- NOBP:
-
Number of basic path
- NOAP:
-
Number of auxiliary path
- LOMP:
-
Length of main path
- LOAP:
-
Length of auxiliary path
- LOBP:
-
Length of basic path
- PLE:
-
Path length-effectiveness
- SC:
-
Switching component
- MSFT:
-
Maximum number of switching components failures tolerated
- UB:
-
Upper bound
- LB:
-
Lower bound
- MUX:
-
Multiplexer
- DMUX:
-
Demultiplexer
- CE:
-
Cost-effectiveness
- RBD:
-
Reliability block diagram
References
Blake JT, Trivedi KS (1989) Reliability analysis of interconnection networks using hierarchical composition. Reliab IEEE Tran 38(1):111–120
Agrawal DP (1983) Graph theoretical analysis and design of multistage interconnection networks. Computers IEEE Trans 100(7):637–648
Massini A (2003) All-to-all personalized communication on multistage interconnection networks. Discrete Appl Math 128(2):435–446
Adams III GB, Howard JS (1982) The extra stage cube: a fault-tolerant interconnection network for supersystems. Computers IEEE Trans 100(5):443–454
Blake JT, Trivedi KS (1989) Multistage interconnection network reliability. Computers IEEE Trans 38(11):1600–1604
Bhardwaj VP, Nitin N (2013) Message broadcasting via a new fault tolerant irregular advance omega network in faulty and nonfaulty network environments. J Electr Computer Eng 6:1–16
Garhwal S, Srivastava N (2011) Designing a fault-tolerant fully-chained combining switches multi-stage interconnection network with disjoint paths. J Supercomput 55(3):400–431
Bhuyan LN, Yang Q, Agrawal DP (1989) Performance of multiprocessor interconnection networks. Computer 22(2):25–37
Newman P (1989) Fast packet switching for integrated services., Computer LaboratoryUniversity of Cambridge, Cambridge
Bansal PK, Joshi RC, Kuldip S (1994) On a fault-tolerant multistage interconnection network. Computers Electr Eng 20(4):335–345
Kumar VP, Reddy SM (1985) Design and analysis of fault-tolerant multistage interconnection networks with low link complexity. In: Proceedings of 12th International Symposium on Computer Architecture, June 1985, pp 376–386
Kumar VP, Reddy SM (1987) Augmented shuffle-exchange multistage interconnection networks. In: IEEE Computer, June 1987, pp 30–40
Wei S, Gyungho L (1988) Extra group network: a cost-effective fault-tolerant multistage interconnection network. In: ACM SIGARCH computer architecture news, vol 16, no. 2, IEEE Computer Society Press
Bansal PK et al (1991) Fault tolerant double tree multistage interconnection network. In: INFOCOM’91. Proceedings. Tenth Annual Joint Conference of the IEEE computer and communications societies. Networking in the 90s, IEEE
Zarandi MA et al (2012) Performance analysis of a fault tolerant multistage interconnection network with backpressure blocking mechanism. J Am Sci 8(7):127–134
Sadawarti H, Bansal PK (2007) Fault tolerant irregular augmented shuffle network. In: Proceedings of the 2007 annual Conference on International Conference on computer engineering and applications. World Scientific and Engineering Academy and Society (WSEAS)
Cheema KK, Rinkle A (2009) Design scheme and performance evaluation of a new fault-tolerant multistage interconnection network. Int J Computer Sci Netw Sec 9(9):270–276
Aggarwal R, Kaur L (2008) On reliability analysis of fault-tolerant multistage interconnection networks. Int J Computer Sci Sec (IJCSS) 2(4):01–08
Aggarwal RR (2012) Design and performance evaluation of a new irregular fault-tolerant multistage interconnection network. Int J Computer Sci 9
Das N, Mukhopadhyaya K, Dattagupta J (2000) O(n) routing in rearrangeable networks. J Syst Arch 46:529–542
Jena S et al (2012) Reliability analysis of multi path multistage interconnection networks. Int J Computer Sci Inf Technol 4(1):63–74
Subramanian A (2008) Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties. J Discrete Alg 6(3):353–380
Gunawan I (2008) Reliability analysis of shuffle-exchange network systems. Reliab Eng Syst Saf 93(2):271–276
Gupta A, Bansal PK (2011) Proposed fault tolerant new irregular augmented shuffle network. Malaysian J Computer Sci 24(1):47
Kaur K, Kaur P, Sadawarti H (2011) Performance analysis of new irregular multistage interconnection network. Int J Adv Eng Sci Technol 9:82–86
Ghai M, Vinay C, Karamjit KC (2010) Performance analysis of fault-tolerant irregular baseline multistage interconnection network. Int J Computer Sci Eng 2(9):3079–3084
Aggarwal R, Kaur L, Aggarwal H (2009) Design and reliability analysis of a new fault-tolerant multistage interconnection network. Icgst-cnir J 8(2):17–23
Vasiliadis DC, George ER, Costas V (2013) Modelling and performance study of finite-buffered blocking multistage interconnection networks supporting natively 2-class priority routing traffic. J Netw Computer Appl 36(2):723–737
Garofalakis J, Stergiou E (2011) Mechanisms and analysis for supporting multicast traffic by using multilayer multistage interconnection networks. Int J Netw Manag 21(2):130–146
Diab H, Tabbara H, Mansour N (2000) Simulation of dynamic input buffer space in multistage interconnection networks. Adv Eng Softw 31(1):13–24
Benes VE (1965) Mathematical theory of connecting networks and telephone traffic, vol 68. Academic press, New York
Du DZ (2001) Analysis of shuffle. Exchange networks under permutation trafic. Switch Net: Recent Adv 5:215
Çam H (2003) Rearrangeability of (2n–1)-stage shuffle-exchange networks. SIAM J Comput 32(3):557–585
Dai H, Shen X (2008) Rearrangeability of 7-stage 16\(\times \) 16 shuffle exchange networks. Front Electr Electron Eng China 3(4):440–458
Clos C (1953) A study of non-blocking switching networks. Bell Syst Tech J 32(2):406–424
Veglis A, Pomportsis A (2001) Dependability evaluation of interconnection networks. Computers Electr Eng 27(3):239–263
Sibai FN (2011) Design and evaluation of low latency interconnection networks for real-time many-core embedded systems. Computers Electr Eng 37(6):958–972
Chadi AA et al (2006) A universal performance factor for multi-criteria evaluation of multistage interconnection networks. Future Gen Computer Syst 22.7:794–804
Cuda D, Giaccone P, Montalto M (2012) Design and control of next generation distribution frames. Computer Netw 56(13):3110–3122
Sheu TL, Lin W, Das CR (1995) Distributed fault diagnosis in multistage network-based multiprocessors. IEEE Trans Computers 44(9):1085–1095
Leung YW (1993) On-line fault identification in multistage interconnection networks. Parallel Comput 19(6):693–702
Chaki N, Bhattacharya S (2000) High level net models: a tool for permutation mapping and fault detection in multistage interconnection network. In: TENCON 2000. Proceedings (vol 2, pp 248–252). IEEE
Choi M, Park N, Lombardi F (2003) Modeling and analysis of fault tolerant multistage interconnection networks. IEEE Trans Instrum Meas 52(5):1509–1519
Gunawan I (2008) Redundant paths and reliability bounds in gamma networks. Appl Math Model 32(4):588–594
Koren I, Mani Krishna C (2010) Fault-tolerant systems. Morgan Kaufmann Publishers Inc. San Francisco, CA
Fard NS, Gunawan I (2006) Reliability bounds for large multistage interconnection networks. Appl Parallel Comput. Springer, Berlin Heidelberg
Bansal PK, Kuldip S, Joshi RC (1993) Reliability and performance analysis of a modular multistage interconnection network. Microelectron Reliab 33(4):529–534
Shooman ML (2001) Reliability of computer systems and networks: fault tolerance, Analysis, and design. Wiley-Interscience, New York
Wang W, Mingxiao J (2004) Generalized decomposition method for complex systems. In: Reliability and maintainability, 2004 Annual Symposium-RAMS. IEEE
Distefano S (2009) Reliability and dependability modeling and analysis of dynamic aspects in complex systems. In: Dpendable, autonomic and secure computing, 2009. DASC’09. Eighth IEEE International Conference on IEEE
Birolini A (2007) Reliability engineering: theory and practice. Springer, Berlin Heidelberg
Tutsch D, Hommel G (2008) MLMIN: a multicore processor and parallel computer network topology for multicast. Computers Oper Res 35(3):3807–3821
Yang Y, Wang J (2005) A new design for wide-sense nonblocking multicast switching networks. IEEE Trans Commun 53(3):497–504
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bistouni, F., Jahanshahi, M. Improved extra group network: a new fault-tolerant multistage interconnection network. J Supercomput 69, 161–199 (2014). https://doi.org/10.1007/s11227-014-1132-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-014-1132-y