In this paper, we investigate the joint construction of topologies of families of optimal diameter circulant networks C(N; ±1, ±s2) and the routing algorithms of complexity O(1) implemented for them. The proposed routing algorithm is based on the use of scalable parameters of L-shaped dense graph packing patterns on the plane for families of optimal networks. Analytical formulas for the dependence of these parameters on the graph diameter of families of optimal networks C(N; ±1, ±s2) are determined, reducing the complexity of their calculation to O( 1). A comparison of the proposed algorithm with the routing algorithm on which it is based was carried out. In families of optimal graphs, the proposed algorithm showed an average two-fold decrease in execution time. The implementation of the investigated routing algorithm as the basis for a network-on-a-chip router is carried out in the hardware description language Verilog. The data of its comparison with other routing algorithms based on the occupied logical and memory resources have been obtained.
- Title Modeling and resource cost estimation of routing algorithms in networks on a chip with a two-dimensional circulant topology
- Headline Modeling and resource cost estimation of routing algorithms in networks on a chip with a two-dimensional circulant topology
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 71
- Date:
- DOI 10.17223/20710410/71/8
Keywords
undirected circulant network, routing algorithm, families of optimal circulant networks, network-on-a-chipAuthors
References
Hwang F. К. A survey on multi-loop networks // Theoret.Comput. Sci. 2003. No. 299. P. 107-121.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3(13). С. 92-115.
Huang X., Ramos A. F., and Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78. No. 11. P. 13491-13510.
Monakhova E. A., Romanov A. Y., and Lezhnev E. V. Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for Networks-on-Chip // IEEE Access. 2020. V.8. P.215010-215019.
Liu H., Li X., and Wang S. Construction of dual optimal bidirectional double-loop networks for optimal routing // Mathematics. 2022. V. 10. No. 21. Paper 4016.
Hoffmann R., Deserable D., and Seredynski F. Cellular automata rules solving the wireless sensor network coverage problem // Nat.Comput. 2022. V. 21. P.417-447.
Erickson A., Stewart I. A., Navaridas J., and Kiasari A.E. The stellar transformation // Comput.Netw. 2017. Y. 113. P.29-45.
Fei J. and Lu C. Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure // IEEE Trans. Neural Netw. Learn. Svst. 2018. V. 29. P. 1275-1286.
Monakhova E. A., Monakhov O. G., and Romanov A. Yu. Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip // IEEE Trans.Network Sci. Eng. 2023. V. 10. No. 1. P.413-425.
Deng Y., Guo M., Ramos A. F., et al. Optimal low-latency network topologies for cluster performance enhancement // J. Supercomput. 2020. V. 76. No. 12. P.9558-9584.
Muhsen Y.R., Husin N. A., Zolkepli M. B., et al. 181Routing techniques in network-on-chip based multiprocessor-svstem-on-chip for IOT: A systematic review // Iraqi J.Comput. Sci. Math. 2024. V. 5. Iss. 1. Article 16.
Beivide R., Herrada E., Balcazar J. L., and Arruabarrena A. Optimal distance networks of low degree for parallel computers // IEEE Trans.Comput. 1991. V. 40. No. 10. P. 1109-1124.
Jha P. K. Dimension-order routing algorithms for a family of minimal-diameter circulants // J.Inter.Networks. 2013. V. 14. No. 1. P. 1350002.
Chen B.-X., Meng J.-X., and Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // LNCS. 2005. V.3794. P.308-316.
Camarero C., Martinez C., and Beivide R. L-networks: a topological model for regular twodimensional interconnection networks // IEEE Trans.Comput. 2013. V. 62. No. 7. P.13621375.
Hwang F. K. A complementary survey on double-loop networks // Theoret.Comput. Sci. 2001. No. 263. P.211-229.
Fiol M. A., Yebra J. L. A., Alegre I., and Valero M. A discrete optimization problem in local networks and data alignment // IEEE Trans.Comput. 1987. V. 36. No. 6. P.702-713.
Wong С. K. and Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc.Comput. Mach. 1974. V.21. No.3. P.392-402.
Монахов О. Г., Монахова Э.А. Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации для семейств оптималвных циркулянтных сетей степени четыре // Дискретн. анализ и исслед. опер. 2025. Т. 32. №2. С. 88-106.
Beivide R., Herrada Е., Balcazar J. L., and Labarta J. Optimized mesh-connected networks for SIMD and MIMD architectures // Proc. ISCA’87. Pittsburgh, Pennsylvania, USA, 1987. P. 163-170.
Lav, F. С. M. and Chen G. Optimal layouts of midimew networks // IEEE Trans. Parallel Distrib. Svst. 1996. V.7. No.9. P.954-961.
Lezhnev E., Zunin V., Amerikanov A., and Romanov A. Electronic computeraided design for low-level modeling of networks-on-chip // IEEE Access. 2024. V. 12. P.48750-48763.
Romanov A. Y. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Helivon. 2019. V. 5. No. 4. Paper e01516.
Modeling and resource cost estimation of routing algorithms in networks on a chip with a two-dimensional circulant topology | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/8
Download full-text version
Counter downloads: 41