Modeling and resource cost estimation of routing algorithms in networks on a chip with a two-dimensional circulant topology

In this paper, we investigate the joint construction of topologies of families of optimal diameter circulant networks $C(N; \pm 1, \pm s_2)$ 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; \pm 1, \pm s_2)$ 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.