Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Zhou W, Fan J, Jia X, Zhang S (2011) The spined cube: a new hypercube variant with smaller diameter. Inf Process Lett 111:561–567
Johnsson SL (1987) Communication efficient basic linear algebra computations on hypercube architectures. J Parallel Distrib Comput 16:133–172
Mendia VE, Sarkar D (1992) Optimal broadcasting on the star graph. IEEE Trans Parallel Distrib Syst 3(4):389–396
Albader B, Bose B, Flahive M (2012) Efficient communication algorithms in hexagonal mesh interconnection networks. IEEE Trans Parallel Distrib Syst 23(1):69–77
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(2):1–17
Carle J, Myoupo J-F, Seme D (1999) All-to-all broadcasting algorithms on honeycomb networks and applications. Parallel Process Lett 9(4):539–550
Deazevedo MM, Bagherzadeh N, Latifi S (1995) Broadcasting algorithms for the star-connected cycles interconnection network. J Parallel Distrib Comput 25:209–222
Farah RN, Othman M (2014) Broadcasting communication in high degree modified chordal rings networks. Appl Math Inf Sci 8(1):229–233
Mkwawa IM, Kouvatsos DD (2003) An optimal neighborhood broadcasting scheme for star interconnection networks. J Interconnect Netw 4(1):103–112
Stewart IA (2014) Interconnection networks of degree three obtained by pruning two-dimensional tori. IEEE Trans Comput 63(10):2473–2486
Thomson A, Zhou S (2014) Frobenius circulant graphs of valency six, Eisenstein–Jacobi networks, and hexagonal meshes. Eur J Comb 38:61–78
Yang X, Wang L, Yang L (2012) Optimal broadcasting for locally twisted cubes. Inf Process Lett 112:129–134
Seo JH, Lee HO (2009) One-to-all broadcasting in Petersen-torus networks for SLA and MLA model. ETRI J 31(3):327–329
Dally W, Seitz C (1986) The torus routing chip. Distrib Comput 1:187–196
Chen MS, Shin KG (1990) Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans Comput 39(1):10–18
Tang KW, Padubidri SA (1994) Diagonal and toroidal mesh networks. IEEE Trans Comput 43(7):815–826
Stojmenovic I (1997) Honeycomb network: topological properties and communication algorithms. IEEE Trans Parallel Distrib Syst 8(10):1036–1042
Arabnia HR, Oliver MA (1989) A transputer network for fast operations on digitised images. Int J Eurograph Assoc (Computer Graphics Forum) 8(1):3–12
Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized tmages using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188–193
Bhandarkar SM, Arabnia HR (1995) The REFINE multiprocessor: theoretical properties and algorithms. Parallel Comput 21(11):1783–1806
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–357
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–571
Seo JH, Sim H, Park DH, Park JW, Lee YS (2011) One-to-one embedding between honeycomb mesh and Petersen-torus networks. Sensors 11:1959–1971
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:133–139
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–539
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–544
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–255
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–308
Holton DA, Sheehan J (1993) The Petersen graph. Australian Mathematical Society lecture notes, vol 7. Cambridge University Press, London
Acknowledgments
We thank the reviewers for their comments and suggestions which have substantially improved our presentation. This work was supported by the 2012 Yeungnam University Research Grant. Also, this research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology(2012R1A1A4A01014439).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kim, JS., Lee, HO., Kim, M. et al. The new Petersen-torus networks. J Supercomput 71, 894–908 (2015). https://doi.org/10.1007/s11227-014-1342-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-014-1342-3