Моделирование специализированных алгоритмов маршрутизации в сетях на кристалле, представленных сериями семейств циркулянтных топологий

В качестве топологий сетей на кристалле рассмотрены серии семейств оптимальных по диаметру двумерных циркулянтных сетей с прямоугольным контуром укладки на плоскости. Прямоугольный контур укладки графа межмодульных соединений даёт возможность компоновки элементов в сетях на кристалле с минимальным количеством пересечений связей и ограниченной длиной максимальной из них, не зависящей от размера сети. Для серий семейств циркулянтных сетей с прямоугольным контуром укладки проведены исследование и моделирование в сети на кристалле новых алгоритмов маршрутизации, использующих координаты трёх соседних нулей укладки графов на плоскости для расчётов кратчайших путей. Отличительной особенностью новых алгоритмов маршрутизации является минимальное количество входных данных для расчёта кратчайших путей. В симуляторе сети на кристалле Noxim на оптимальных графах семейств реализованы четыре алгоритма маршрутизации: новый аналитический алгоритм, классический алгоритм Дейкстры, алгоритм маршрутизации с виртуальными координатами и алгоритм обхода по часовой стрелке. Сравнение алгоритмов проведено при различных профилях трафика по трём метрическим показателям – средней и максимальной задержкам и пропускной способности сети. Результаты моделирования показали преимущество по затратам памяти новых алгоритмов маршрутизации, специализированных для топологий циркулянтных сетей с прямоугольным контуром укладки, по сравнению с другими алгоритмами для всех рассмотренных профилей трафика при схожих или лучших метрических показателях.

1. Hwang F.K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299, Nos 1–3. P. 107–121. https://doi.org/10.1016/s0304-3975(01)00341-3.

2. Liu H., Li X., Wang S. Construction of dual optimal bidirectional double-loop networks for optimal routing // Mathematics. 2022. V. 10, No 21. Art. 4016. https://doi.org/10.3390/math10214016.

3. P´erez-Ros´es H., Bras-Amor´os M., Seradilla-Merinero J.M. Greedy routing in circulant networks // Graphs Combinatorics. 2022. V. 38, No 3. Art. 86. https://doi.org/10.1007/s00373-022-02489-9.

4. Huang X., Ramos A.F., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78, No 11. P. 13491–13510. https://doi.org/10.1007/s11227-022-04396-5.

5. Martinez C., Vallejo E., Beivide R., Izu C., Moret´o M. Dense Gaussian networks: Suitable topologies for on-chip multiprocessors // Int. J. Parallel Program. 2006. V. 34, No 3. P. 193–211. https://doi.org/10.1007/s10766-006-0014-1.

6. Pai K.-J., Yang J.-S., Chen G.-Y., Chang J.-M. Configuring protection routing via completely independent spanning trees in dense Gaussian on-chip networks // IEEE Trans. Network Sci. Eng. 2022. V. 9, No 2. P. 932–946. https://doi.org/10.1109/TNSE.2022.3140329.

7. Romanov A.Y. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Heliyon. 2019. V. 5, No 4. Art. e01516. https://doi.org/10.1016/j.heliyon.2019.e01516.

8. Монахов О.Г., Монахова Э.А. Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации для семейств оптимальных циркулянтных сетей степени четыре // Дискретн. анализ и исслед. опер. 2025. Т. 32, № 2. C. 88–106. https://doi.org/10.33048/daio.2025.32.808.

9. Deng Y., Guo M., Ramos A.F., Huang X., Xu Z., Liu W. Optimal low-latency network topologies for cluster performance enhancement // J. Supercomput. 2020. V. 76, No 12. P. 9558–9584. https://doi.org/10.1007/s11227-020-03216-y.

10. Camarero C., Martinez C., Beivide R. L-networks: A topological model for regular two-dimensional interconnection networks // IEEE Trans. Comput. 2013. V. 62, No 7. P. 1362–1375. https://doi.org/10.1109/TC.2012.77.

11. Монахова Э.А. Оптимальные циркулянтные графы с прямоугольным контуром укладки на плоскости // Сиб. электрон. матем. изв. 2025. Т. 22, № 2. C. 1538–1551. https://doi.org/10.33048/semi.2025.22.093.

12. Нестеренко Б.Б., Новотарский М.А. Клеточные нейронные сети на циркулянтных графах // Искусств. интеллект. 2009. Т. 3. C. 132–138.

13. Catania V., Mineo A., Monteleone S., Palesi M., Patti D. Noxim: An open, extensible and cycle-accurate network on chip simulator // Proc. IEEE 26th Int. Conf. on Application-Specific Systems, Architectures and Processors (ASAP). IEEE, 2015. P. 162–163. https://doi.org/10.1109/ASAP.2015.7245728.

14. Catania V., Mineo A., Monteleone S., Palesi M., Patti D. Cycle-accurate network on chip simulation with Noxim // ACM Trans. Model. Comput. Simul. 2017. V. 27, No 1. Art. 4. https://doi.org/10.1145/2953878.

15. Chen B.-X., Meng J.-X., Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // Jia X., Wu J., He Y. (Eds.) Mobile Ad-hoc and Sensor Networks. MSN 2005. Ser.: Lecture Notes in Computer Science. V. 3794. Berlin, Heidelberg: Springer, 2005. P. 308–316. https://doi.org/10.1007/11599463.31.

16. Jha P.K. Dimension-order routing algorithms for a family of minimal-diameter circulants // J. Interconnect. Networks. 2013. V. 14, No 1. Art. 1350002. https://doi.org/10.1142/s0219265913500023.

17. Сухов А.М., Романов А.Ю., Глушак Е.В. Маршрутизация в циркулянтных графах на основе виртуальной координатной системы // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2023. Т. 165, кн. 3. С. 282–293. https://doi.org/10.26907/2541-7746.2023.3.282-293.

18. Malikov M.A., Romanov A.Y. Traffic patterns in networks-on-chip: A survey // IEEE Access. 2025. V. 13. P. 148803–148815. https://doi.org/10.1109/ACCESS.2025.3601971.