Improved extra group network: a new fault-tolerant multistage interconnection network

详细信息    查看全文

• 作者：Fathollah Bistouni (1)
  Mohsen Jahanshahi (2)
  
• 关键词：Parallel processing ; Multistage interconnection network ; Fault tolerance ; Reliability ; Extra group network
• 刊名：The Journal of Supercomputing
• 出版年：2014
• 出版时间：July 2014
• 年：2014
• 卷：69
• 期：1
• 页码：161-199
• 全文大小：4,169 KB
• 参考文献：1. Blake JT, Trivedi KS (1989) Reliability analysis of interconnection networks using hierarchical composition. Reliab IEEE Tran 38(1):111-20 CrossRef
  2. Agrawal DP (1983) Graph theoretical analysis and design of multistage interconnection networks. Computers IEEE Trans 100(7):637-48 CrossRef
  3. Massini A (2003) All-to-all personalized communication on multistage interconnection networks. Discrete Appl Math 128(2):435-46 CrossRef
  4. Adams III GB, Howard JS (1982) The extra stage cube: a fault-tolerant interconnection network for supersystems. Computers IEEE Trans 100(5):443-54
  5. Blake JT, Trivedi KS (1989) Multistage interconnection network reliability. Computers IEEE Trans 38(11):1600-604 CrossRef
  6. 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-6
  7. 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-31
  8. Bhuyan LN, Yang Q, Agrawal DP (1989) Performance of multiprocessor interconnection networks. Computer 22(2):25-7
  9. Newman P (1989) Fast packet switching for integrated services., Computer LaboratoryUniversity of Cambridge, Cambridge
  10. Bansal PK, Joshi RC, Kuldip S (1994) On a fault-tolerant multistage interconnection network. Computers Electr Eng 20(4):335-45
  11. 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-86
  12. Kumar VP, Reddy SM (1987) Augmented shuffle-exchange multistage interconnection networks. In: IEEE Computer, June 1987, pp 30-0
  13. 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
  14. Bansal PK et al (1991) Fault tolerant double tree multistage interconnection network. In: INFOCOM-1. Proceedings. Tenth Annual Joint Conference of the IEEE computer and communications societies. Networking in the 90s, IEEE
  15. Zarandi MA et al (2012) Performance analysis of a fault tolerant multistage interconnection network with backpressure blocking mechanism. J Am Sci 8(7):127-34
  16. 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)
  17. 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-76
  18. Aggarwal R, Kaur L (2008) On reliability analysis of fault-tolerant multistage interconnection networks. Int J Computer Sci Sec (IJCSS) 2(4):01-8
  19. Aggarwal RR (2012) Design and performance evaluation of a new irregular fault-tolerant multistage interconnection network. Int J Computer Sci 9
  20. Das N, Mukhopadhyaya K, Dattagupta J (2000) O(n) routing in rearrangeable networks. J Syst Arch 46:529-42
  21. Jena S et al (2012) Reliability analysis of multi path multistage interconnection networks. Int J Computer Sci Inf Technol 4(1):63-4
  22. 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-80 CrossRef
  23. Gunawan I (2008) Reliability analysis of shuffle-exchange network systems. Reliab Eng Syst Saf 93(2):271-76 CrossRef
  24. Gupta A, Bansal PK (2011) Proposed fault tolerant new irregular augmented shuffle network. Malaysian J Computer Sci 24(1):47
  25. Kaur K, Kaur P, Sadawarti H (2011) Performance analysis of new irregular multistage interconnection network. Int J Adv Eng Sci Technol 9:82-6
  26. 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-084
  27. 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-3
  28. 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-37
  29. 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-46
  30. Diab H, Tabbara H, Mansour N (2000) Simulation of dynamic input buffer space in multistage interconnection networks. Adv Eng Softw 31(1):13-4 CrossRef
  31. Benes VE (1965) Mathematical theory of connecting networks and telephone traffic, vol 68. Academic press, New York
  32. Du DZ (2001) Analysis of shuffle. Exchange networks under permutation trafic. Switch Net: Recent Adv 5:215 CrossRef
  33. ?am H (2003) Rearrangeability of (2n-)-stage shuffle-exchange networks. SIAM J Comput 32(3):557-85
  34. Dai H, Shen X (2008) Rearrangeability of 7-stage 16 \(\times \) 16 shuffle exchange networks. Front Electr Electron Eng China 3(4):440-58
  35. Clos C (1953) A study of non-blocking switching networks. Bell Syst Tech J 32(2):406-24
  36. Veglis A, Pomportsis A (2001) Dependability evaluation of interconnection networks. Computers Electr Eng 27(3):239-63 CrossRef
  37. Sibai FN (2011) Design and evaluation of low latency interconnection networks for real-time many-core embedded systems. Computers Electr Eng 37(6):958-72
  38. Chadi AA et al (2006) A universal performance factor for multi-criteria evaluation of multistage interconnection networks. Future Gen Computer Syst 22.7:794-04
  39. Cuda D, Giaccone P, Montalto M (2012) Design and control of next generation distribution frames. Computer Netw 56(13):3110-122
  40. Sheu TL, Lin W, Das CR (1995) Distributed fault diagnosis in multistage network-based multiprocessors. IEEE Trans Computers 44(9):1085-095 CrossRef
  41. Leung YW (1993) On-line fault identification in multistage interconnection networks. Parallel Comput 19(6):693-02 CrossRef
  42. 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-52). IEEE
  43. Choi M, Park N, Lombardi F (2003) Modeling and analysis of fault tolerant multistage interconnection networks. IEEE Trans Instrum Meas 52(5):1509-519 CrossRef
  44. Gunawan I (2008) Redundant paths and reliability bounds in gamma networks. Appl Math Model 32(4):588-94
  45. Koren I, Mani Krishna C (2010) Fault-tolerant systems. Morgan Kaufmann Publishers Inc. San Francisco, CA
  46. Fard NS, Gunawan I (2006) Reliability bounds for large multistage interconnection networks. Appl Parallel Comput. Springer, Berlin Heidelberg
  47. Bansal PK, Kuldip S, Joshi RC (1993) Reliability and performance analysis of a modular multistage interconnection network. Microelectron Reliab 33(4):529-34 CrossRef
  48. Shooman ML (2001) Reliability of computer systems and networks: fault tolerance, Analysis, and design. Wiley-Interscience, New York
  49. Wang W, Mingxiao J (2004) Generalized decomposition method for complex systems. In: Reliability and maintainability, 2004 Annual Symposium-RAMS. IEEE
  50. Distefano S (2009) Reliability and dependability modeling and analysis of dynamic aspects in complex systems. In: Dpendable, autonomic and secure computing, 2009. DASC-9. Eighth IEEE International Conference on IEEE
  51. Birolini A (2007) Reliability engineering: theory and practice. Springer, Berlin Heidelberg
  52. Tutsch D, Hommel G (2008) MLMIN: a multicore processor and parallel computer network topology for multicast. Computers Oper Res 35(3):3807-821 CrossRef
  53. Yang Y, Wang J (2005) A new design for wide-sense nonblocking multicast switching networks. IEEE Trans Commun 53(3):497-04 CrossRef
  
• 作者单位：Fathollah Bistouni (1)
  Mohsen Jahanshahi (2)
  
  1. Department of Electrical, Computer and Biomedical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
  2. Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran
  
• ISSN：1573-0484

文摘

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.