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

Ученые записки Казанского университета. Серия: Физико-математические науки. 2026. Т. 168. № 2. С. 269–286.

Маликов М. А., Монахова Э. А., Rzaev E., Romanov A.

This article examines series of families of two-dimensional circulant networks with rectangular
L -shapes, optimal in diameter, as network-on-chip topologies with a minimal number of crossings
between the links and a bounded length of the maximum link that does not depend on the network
size. New network-on-chip routing algorithms, which use the coordinates of three adjacent zeros in
the planar graph embedding to calculate the shortest paths, were investigated and simulated. A key
advantage of the proposed routing algorithms is that they require minimal input data to calculate the
shortest paths. Four routing algorithms were implemented in the Noxim network-on-chip simulator
using the optimal graphs of the circulant network families under study: the new analytical algorithm,
the traditional Dijkstra algorithm, the routing algorithm with virtual coordinates, and the clockwise
routing algorithm. The above algorithms were compared under various traffic profiles across three
metrics: average and maximum latencies and network throughput. The simulation results showed that,
for all traffic profiles, the new routing algorithms designed for the topologies of circulant networks
with rectangular L -shapes outperform other algorithms with similar metrics in terms of memory
consumption.

Keywords: сеть на кристалле, routing algorithm, алгоритм маршрутизации, circulant network, network-on-chip, rectangular L -shape, minimal diameter, циркулянтная сеть, прямоугольный контур укладки, минимальный диаметр