Free Access
Fast Local Rules Based Switching and Routing Within Multidimensional Torus Interconnect
https://doi.org/10.1142/S0129626424500026Cited by:0 (Source: Crossref)
Abstract
Multidimensional torus networking topology has become widespread recently in the domain of high-performance computers, clusters, and grids, as well as in the domain of networks on chip. Torus represents an ideal communication structure with the shortest distance and multitude of alternative shortest paths between a pair of nodes. We study simple and powerful local packet forwarding (switching) rules that provide packet delivery with quasi-optimal load balancing and do not use tables of addresses (routes). Implementation of these rules in the form of micro-program code within switching nodes increases considerably network performance, security, and QoS. We use infinite Petri nets and reenterable models in the form of colored Petri nets for prototyping the multi-dimensional torus interconnect simulator to study and compare the packet forwarding rules. Then, an ad-hoc simulator of torus interconnect ts is implemented in the C language to provide high performance and the possibility of simulation over prolonged intervals of time. The simulation results acknowledge the advantages of local packet forwarding rules.
Communicated by Andrew Adamatzky
References
- 1. , Novel Practices and Trends in Grid and Cloud Computing (IGI Global, USA, 2019). Crossref, Google Scholar
- 2. The world’s top-level supercomputer: Supercomputer Fugaku, https://www.fujitsu.com/global/about/innovation/fugaku/. Google Scholar
- 3. J. Dongarra, Report on the Fujitsu Fugaku System. Tech Report ICL-UT-20-06, University of Tennessee, Knoxville, Oak Ridge National Laboratory, University of Manchester, USA (2020). Google Scholar
- 4. , TOFU: A 6D mesh/torus interconnect for exascale computers, Computer 42(11) (November 2009) 36–40. Crossref, Web of Science, Google Scholar
- 5. , Visualizing the topology and data traffic of multi-dimensional torus interconnect networks, IEEE Access 6 (2018) 57191–57204. Crossref, Web of Science, Google Scholar
- 6. , On-Chip Networks (Morgan and Claypool Publishers, 2017). Crossref, Google Scholar
- 7. , Verification of hyper-torus communication grids by infinite Petri nets and process algebra, IEEE/CAA Journal of Automatica Sinica 6(3) (2019) 733–742. https://doi.org/10.1109/JAS.2019.1911486 Crossref, Google Scholar
- 8. , Analysis of a hypertorus grid, in Proc. of IEEE 38th International Conference Electronics and Nanotechnology (ELNANO-2018),
Kyiv, Ukraine ,April 24–26, 2018 . NTUU “Igor Sikorsky Kyiv Polytechnic Institute”, 2018, pp. 56–59. https://doi.org/10.1109/EL-NANO.2018.8477554 Google Scholar - 9. , Security of grid structures under disguised traffic attacks, Cluster Computing 19(3) (2016) 1183–1200. https://doi.org/10.1007/s10586-016-0582-9 Crossref, Web of Science, Google Scholar
- 10. , Verification of computing grids with special edge conditions by infinite Petri nets, Automatic Control and Computer Sciences 47(7) (2013) 403–412. https://doi.org/10.3103/S0146411613070262 Crossref, Google Scholar
- 11. , Verification of hypercube communication structures via parametric Petri nets, Cybernetics and Systems Analysis 46(1) (2010) 105–114. https://doi.org/10.1007/s10559-010-9189-y Crossref, Google Scholar
- 12. , OutFlank routing: Increasing throughput in toroidal interconnection networks, in Proc. of 2013 International Conference on Parallel and Distributed Systems (ICPADS) (2013), pp. 216–223. Crossref, Google Scholar
- 13. , Fault-aware load-balancing routing for 2D-mesh and torus on-chip network topologies, IEEE Transactions on Computers 65(3) (2016) 873–887. Crossref, Google Scholar
- 14. , Mesh-of-Torus: A new topology for server-centric data center networks, The Journal of Supercomputing 75 (2019) 255. Crossref, Google Scholar
- 15. , P-Torus: Torus-based optical packet switching architecture for intra-data centre networks, in Proc. of 2018 Photonics in Switching and Computing (PSC),
Limassol, Cyprus ,2018 , pp. 1–3. https://doi.org/10.1109/PS.2018.8751276 Google Scholar - 16. , A generalized neighborhood for cellular automata, Theoretical Computer Science 666 (2017) 21–35. https://doi.org/10.1016/j.tcs.2016.11.002 Crossref, Web of Science, Google Scholar
- 17. N. P. Preve (Ed.), Grid Computing: Towards a Global Interconnected Infrastructure (Springer, 2011). Crossref, Google Scholar
- 18. , Hypercube Algorithms: With Application to Image Processing and Pattern Recognition (Springer, 2011). Google Scholar
- 19. , Plasma Physics and Controlled Nuclear Fusion (Springer, 2005). Google Scholar
- 20. , Colouring space – A coloured framework for spatial modelling in systems biology, in Proc. PETRI NETS 2013,
Milano, LNCS , Vol. 7927 (Springer, 2013), pp. 230–249. Google Scholar - 21. , Switching vs routing within multi-dimensional torus interconnect, in PIC&ST2020,
October 6–9, 2020 ,Kharkiv, Ukraine . Google Scholar - 22. , Infinite Petri nets: Part 1, Modeling square grid structures, Complex Systems 26(2) (2017) 157–195. https://doi.org/10.25088/ComplexSystems.26.2.157 Crossref, Google Scholar
- 23. , Infinite Petri nets: Part 2, Modeling triangular, hexagonal, hypercube and hypertorus structures, Complex Systems 26(4) (2017) 341–371. https://doi.org/10.25088/ComplexSystems.26.2.341 Crossref, Google Scholar
- 24. , The torus routing chip, Distrib. Comput. 1 (1986) 187–196. Crossref, Web of Science, Google Scholar
- 25. , Globally adaptive load-balanced routing on tori, IEEE Computer Architecture Letters 3(1) (January 2004) 2–2. Crossref, Google Scholar
- 26. , A novel globally adaptive load-balanced routing algorithm for torus interconnection networks, ETRI Journal 29 (2007) 405. Crossref, Web of Science, Google Scholar
- 27. ,
rHALB: A new load-balanced routing algorithm for k-ary n-cube networks , in Advanced Parallel Processing Technologies (APPT 2007), eds. M. Xu, Y. Zhan, J. Cao and Y. Liu,Lecture Notes in Computer Science , Vol. 4847 (Springer, 2007). Crossref, Google Scholar - 28. , A set-to-set disjoint paths routing algorithm in tori, International Journal of Networking and Computing 7(2) (July 2017) 173–186. Crossref, Google Scholar
- 29. , Reenterable colored Petri net models of networks, grids, and clouds: Case study for provider backbone bridge, in Proc. of 26th Telecommunications Forum (TELFOR 2018),
November 20–21, 2018 ,Belgrade, Serbia . https://doi.org/10.1109/TELFOR.2018.8611840 Google Scholar - 30. , Coloured Petri Nets: Modelling and Validation of Concurrent Systems (Springer, 2009). Crossref, Google Scholar
- 31. K. L. Utley, Re-enterable programming, IBM Technical Disclosure Bulletin 13(9) (1971) 2505–2507. Google Scholar
- 32. , Elements of ML Programming (Prentice-Hall, 1997). Google Scholar
- 33. CPN Tools, http://cpntools.org. Google Scholar
- 34. , Spatial specification of grid structures by Petri nets, micro-electronics and telecommunication engineering, in Proceedings of 4th ICMETE 2020, Lecture Notes in Networks and Systems, Vol. 179 (2021). Google Scholar
- 35. , Transformations of models of 2-dimensional grids colored Petri nets into infinite Petri nets and vise versa, in Proc. of 2018 International Conference on Information and Telecommunication Technologies and Radio Electronics (UkrMiCo),
Odessa, Ukraine ,September 10–14, 2018 , pp. 1–6. Google Scholar - 36. Cut-Through and Store-and-Forward Ethernet Switching for Low-Latency Environments, Cisco White Paper, 2008. Google Scholar
- 37. , Network Routing Algorithms, Protocols, and Architectures (Morgan Kaufmann, 2018), 1018 pp. Google Scholar
- 38. , Load-balancing fast rerouting model with providing fair priority-based traffic policing, in Proc. of 2019 IEEE International Scientific-Practical Conference Problems of Infocommunications, Science and Technology (PIC S&T),
Kyiv, Ukraine ,2019 , pp. 538–542. Google Scholar - 39. , Deadlock Resolution in Automated Manufacturing Systems (Springer, 2010). Google Scholar
- 40. , Petri Nets: Fundamental Models, Verification and Applications (John Wiley & Sons, 2013). Google Scholar
