Abstract
A two-dimensional (2D) Petersen-torus network is a mesh-class fixed-degree network designed using a Petersen graph, which has a maximum of 10 nodes when the degree is 3 and the diameter is 2 in a (d,k)-graph problem. Here, I propose a new three-dimensional (3D) Petersen-torus network that extends the 2D Petersen-torus network without increasing the degree. The 3D Petersen-torus has the same number of nodes (N). The 3D Petersen-torus is better than the well-known 3D torus and 3D honeycomb mesh in terms of diameter and network cost. The 3D Petersen-torus network is better than the hypercube-like and star graph-like networks in terms of extendibility. Hence, the proposed network may serve as the foundation for realizing a high-performance multicomputer. In this paper, the optimal routing algorithm, Hamilton cycle, and several basic attributes are discussed. Furthermore, a comparison with a mesh-class fixed-degree 3D network is made for degree, diameter, and network cost.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ergu D, Kou G, Peng Y, Shi Y, Shi Y (2011) The analytic hierarchy process: Task scheduling and resource allocation in cloud computing environment. J Supercomput. doi:10.1007/s11227-011-0625-1
Parhami B, Kwai D-M (2001) A unified formulation of honeycomb and diamond networks. IEEE Trans Parallel Distrib Syst 12(1):74–80
Ni LM, McKinley PK (1993) A survey of wormhole routing techniques in direct networks. IEEE Comput 26(2):62–76
Parhami B, Rakov M (2005) Perfect difference networks and related interconnection structures for parallel and distributed systems. IEEE Trans Parallel Distrib Syst 16(8):714–724
Parhami B, Yeh C-H (2000) Why network diameter is still important. In: Proc int’l conf comm in computing, pp 271–274
Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Comput 37(7):867–872
Mendia VE, Sarkar D (1992) Optimal broadcasting on the star graph. IEEE Trans Parallel Distrib Syst 3(4):389–396
Tang KW, Padubidri SA (1994) Diagonal and toroidal mesh networks. IEEE Trans Comput 43(7):815–826
Latifi S, Srimani PK (1998) A fixed degree regular networks for massively parallel systems. J Supercomput 12(3):277–291
Zhou S, Du N, Chen B (2006) A new family of interconnection networks of odd fixed degrees. J Parallel Distrib Comput 66(5):698–704
Moraveji R, Sarbazi-Azad H, Zomaya AY (2011) Performance modeling of Cartesian product networks. J Parallel Distrib Comput 71(1):105–113
Ghose K, Desai KR (1995) Hierarchical cubic network. IEEE Trans Parallel Distrib Syst 6(4), 427–435
EI-Amawy A, Latifi S (1991) Properties and performances of folded hypercubes. IEEE Trans Parallel Distrib Syst 2(1):31–42
Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40(11):1312–1316
Park J-H (1992) Circulant graphs and their application to communication networks. PhD Thesis, Dept of Computer Science, KAIST, Taejon, Korea
Yeh C-H, Varvarigos E (1996) Macro-star networks: Efficient low-degree alternatives to star graphs for large-scale parallel architectures. In: Frontier’96, symp on the frontiers of massively parallel computation
Latifi S, Srimani PK (1996) Transposition networks as a class of fault-tolerant robust networks. IEEE Trans Comput 45(2):230–238
Lee HO, Kim JS, Park KW, Seo JH (2005) Matrix star graphs: A new interconnection network based on matrix operations. In: ACSAC 2005. LNCS, vol 3740, pp 478–487
Stojmenovic I (1997) Honeycomb network: Topological properties and commnication algorithms. IEEE Trans Parallel Distrib Syst 8(10):1036–1042
Chen MS, Shin KG (1990) Addressing, routing, and broadcasting in hexagonal mesh multiprocessors. IEEE Trans Comput 39(1):10–18
Decayeux C, Seme D (2005) 3D hexagonal network: Modeling, topological properties, addressing scheme, and optimal routing algorithm. IEEE Trans Parallel Distrib Syst 16(9):875–884
Scott SL, Thorson G (1996) The Cray T3E network: Adaptive routing in a high performance 3D toms. In: HOT interconnects IV, Stanford University
Carle J, Myoupo JF, Stojmenovic I (2001) Higher dimensional honeycomb networks. J Interconnect Netw 2(4):391–420
Nguyen J, Pezaris J, Pratt GA, Ward S (1994) Three-dimensional network topologies. In: Proceedings of the first international workshop on parallel computer routing and communication, pp 101–115
Cray Inc (2008) Cray XT3 datasheet. http://www.cray.com/downloads/Cray_XT3_Datasheet.pdf
Cray Inc (2008) Cray XT4 datasheet. http://www.cray.com/downloads/Cray_XT4_Datasheet.pdf
Choo H, Yoo S-M, Youn HY (2000) Processor scheduling and allocation for 3d torus multicomputer systems. IEEE Trans Parallel Distrib Syst 11(5):475–484
Seo JH, Lee HO, Jang MS (2008) Petersen-torus networks for multicomputer systems. In: Proc int’l conf of NCM2008, vol 1, pp 567–571
Seo JH, Lee HO (2009) One-to-one embedding between hyper Petersen and Petersen-torus networks. Int J Grid Distrib Comput 2(4):27–33
Seo JH, Lee HO, Jang MS (2008) Node mapping algorithm between torus and Petersen-torus networks. In: Proc int’l conf of NCM2008, vol 2, pp 540–544
Seo J-H, Lee H-O (2009) One-to-all broadcasting in Petersen-torus networks for SLA and MLA models. ETRI J 31(3):327–329
Chartrand G, Wilson RJ (1985) The Petersen graph. In: Harary F, Maybee JS (eds) Graphs and applications, pp 69–100
Camara JM, Moreto M, Vallejo E, Beivide R, Miguel-Alonso J, Martínez C, Navaridas J (2010) Twisted torus topologies for enhanced interconnection networks. IEEE Trans Parallel Distrib Syst 21(12):1765–1778
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Seo, Jh. Three-dimensional Petersen-torus network: a fixed-degree network for massively parallel computers. J Supercomput 64, 987–1007 (2013). https://doi.org/10.1007/s11227-011-0716-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-011-0716-z