The new Petersen-torus networks

详细信息    查看全文

• 作者：Jong-Seok Kim (1)
  Hyeong-Ok Lee (2)
  Mihye Kim (3)
  Sung Won Kim (4)
  
  1. Department of Mathematics and Physics ; North Carolina Central University ; Durham ; NC ; 27707 ; USA
  2. Department of Computer Education ; Sunchon National University ; Sunchon ; Chonnam ; 540-742 ; South Korea
  3. Department of Computer Science Education ; Catholic University of Daegu ; Gyeongsan ; Gyeongbuk ; 712-702 ; South Korea
  4. Department of Information and Communication Engineering ; Yeungnam University ; Gyeongsan ; Gyeongbuk ; 712-749 ; South Korea
  
• 关键词：Petersen ; torus network ; New Petersen ; torus network ; Routing ; Diameter ; Broadcasting
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：71
• 期：3
• 页码：894-908
• 全文大小：384 KB
• 参考文献：1. Zhou, W, Fan, J, Jia, X, Zhang, S (2011) The spined cube: a new hypercube variant with smaller diameter. Inf Process Lett 111: pp. 561-567 2011.03.011" target="_blank" title="It opens in new window">CrossRef
  2. Johnsson, SL (1987) Communication efficient basic linear algebra computations on hypercube architectures. J Parallel Distrib Comput 16: pp. 133-172 2-5" target="_blank" title="It opens in new window">CrossRef
  3. Mendia, VE, Sarkar, D (1992) Optimal broadcasting on the star graph. IEEE Trans Parallel Distrib Syst 3: pp. 389-396 CrossRef
  4. Albader, B, Bose, B, Flahive, M (2012) Efficient communication algorithms in hexagonal mesh interconnection networks. IEEE Trans Parallel Distrib Syst 23: pp. 69-77 2011.112" target="_blank" title="It opens in new window">CrossRef
  5. Bai, L, Maeda, H, Ebara, H, Nakano, H (1998) A broadcasting algorithm with time and message optimum on arrangement graphs. J Graph Algorithms Appl 2: pp. 1-17 CrossRef
  6. Carle, J, Myoupo, J-F, Seme, D (1999) All-to-all broadcasting algorithms on honeycomb networks and applications. Parallel Process Lett 9: pp. 539-550 2/S0129626499000505" target="_blank" title="It opens in new window">CrossRef
  7. Deazevedo MM, Bagherzadeh N, Latifi S (1995) Broadcasting algorithms for the star-connected cycles interconnection network. J Parallel Distrib Comput 25:209鈥?22
  8. Farah, RN, Othman, M (2014) Broadcasting communication in high degree modified chordal rings networks. Appl Math Inf Sci 8: pp. 229-233 2785/amis/080128" target="_blank" title="It opens in new window">CrossRef
  9. Mkwawa, IM, Kouvatsos, DD (2003) An optimal neighborhood broadcasting scheme for star interconnection networks. J Interconnect Netw 4: pp. 103-112 2/S0219265903000751" target="_blank" title="It opens in new window">CrossRef
  10. Stewart IA (2014) Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Trans Comput 63(10):2473鈥?486
  11. Thomson, A, Zhou, S (2014) Frobenius circulant graphs of valency six, Eisenstein鈥揓acobi networks, and hexagonal meshes. Eur J Comb 38: pp. 61-78 2013.11.004" target="_blank" title="It opens in new window">CrossRef
  12. Yang, X, Wang, L, Yang, L (2012) Optimal broadcasting for locally twisted cubes. Inf Process Lett 112: pp. 129-134 2011.11.003" target="_blank" title="It opens in new window">CrossRef
  13. Seo, JH, Lee, HO (2009) One-to-all broadcasting in Petersen-torus networks for SLA and MLA model. ETRI J 31: pp. 327-329 218/etrij.09.0208.0418" target="_blank" title="It opens in new window">CrossRef
  14. Dally, W, Seitz, C (1986) The torus routing chip. Distrib Comput 1: pp. 187-196 CrossRef
  15. Chen, MS, Shin, KG (1990) Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans Comput 39: pp. 10-18 2.46277" target="_blank" title="It opens in new window">CrossRef
  16. Tang, KW, Padubidri, SA (1994) Diagonal and toroidal mesh networks. IEEE Trans Comput 43: pp. 815-826 2.293260" target="_blank" title="It opens in new window">CrossRef
  17. Stojmenovic, I (1997) Honeycomb network: topological properties and communication algorithms. IEEE Trans Parallel Distrib Syst 8: pp. 1036-1042 29486" target="_blank" title="It opens in new window">CrossRef
  18. Arabnia, HR, Oliver, MA (1989) A transputer network for fast operations on digitised images. Int J Eurograph Assoc (Computer Graphics Forum) 8: pp. 3-12 CrossRef
  19. Arabnia, HR (1990) A parallel algorithm for the arbitrary rotation of digitized tmages using process-and-data-decomposition approach. J Parallel Distrib Comput 10: pp. 188-193 28-N" target="_blank" title="It opens in new window">CrossRef
  20. Bhandarkar, SM, Arabnia, HR (1995) The REFINE multiprocessor: theoretical properties and algorithms. Parallel Comput 21: pp. 1783-1806 2-9" target="_blank" title="It opens in new window">CrossRef
  21. Arabnia HR, Smith JW (1993) A reconfigurable interconnection network for imaging operations and its implementation using a multi-stage switching box. In: Proceedings of the 7th annual international high performance computing conference. The 1993 high performance computing: new horizons supercomputing symposium, pp 349鈥?57
  22. Seo JH, Lee HO, Jang M (2008) Petersen-torus networks for multicomputer systems. In: Proceedings of the international conference on networked computing and advanced information management, pp 567鈥?71
  23. Seo, JH, Sim, H, Park, DH, Park, JW, Lee, YS (2011) One-to-one embedding between honeycomb mesh and Petersen-torus networks. Sensors 11: pp. 1959-1971 201959" target="_blank" title="It opens in new window">CrossRef
  24. Seo, JH, Jang, M, Kim, E, Ban, K, Ryu, N, Lee, HO (2009) One-to-one embedding between hyper Petersen and Petersen-torus networks. Commun Comput Inf Sci 63: pp. 133-139 2-10549-4_16" target="_blank" title="It opens in new window">CrossRef
  25. Seo JH, Lee HO, Jang M, Kim E (2008) Node mapping algorithm between hypercube and Petersen-torus networks. In: Proceedings of the international conference on networked computing and advanced information management, pp 535鈥?39
  26. Seo JH, Lee HO, Jang M, Han SH (2008) Node mapping algorithm between torus and Petersen-torus networks. In: Proceedings of the international conference on networked computing and advanced information management, pp 540鈥?44
  27. Seo JH, Lee HO, Jang M (2008) Constructing complete binary trees on Petersen-torus networks. In: Proceedings of the international conference on computer sciences and convergence information technology, pp 252鈥?55
  28. Seo JH, Lee HO, Jang M (2008) Optimal routing and hamiltonian cycle in Petersen-torus networks. In: Proceedings of the international conference on computer sciences and convergence information technology, pp 303鈥?08
  29. Holton DA, Sheehan J (1993) The Petersen graph. Australian Mathematical Society lecture notes, vol 7. Cambridge University Press, London
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

Routing and broadcasting are major parameters determining the performance of interconnection networks. In this paper, we propose a new Petersen-torus network \(\mathrm{NPT}(m, n)\) by modifying the external edge definitions of the Petersen-torus network to improve its diameter and broadcasting times. We also show one-to-all broadcasting algorithms in \(\mathrm{NPT}(m, n)\) using the single-link available and multiple-link available models.