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

Информационные технологии. 2020. Т. 26. № 1. С. 22–29.

Романов А.Ю., Сидоренко М.В., Монахова Э. А.

The paper presents the implementation of a dynamic routing algorithm intended for use in networks-on-chip with a three-dimensional circulant topology of type C(N; s1, s2, s3). Compared with the classical algorithms A* or Dijkstra, the proposed algorithm does not require to calculate the entire path of the packet, but calculates the port number to which the packet should be sent so that it can reach the destination node. This makes it possible to significantly simplify the structure of the NoC router. The algorithm can be implemented as RTL state machine in routers for NoCs for finding the shortest routes between any two network nodes.

The proposed algorithm was tested on sets of optimal circulants. For this set, it is equal to 0.973 which is a sufficient indicator of efficiency of the algorithm for the task of implementing the algorithm in HDL at the level of a network-on-chip router, since this algorithm has linear complexity and can be easily implemented.

In 95 % of the cases considered, for a set of graphs with the number of vertices less than 300, the algorithm showed a result similar to that obtained using the Dijkstra algorithm. The computational time complexity of the created algorithm is similar to the complexity of the Dijkstra algorithm which is considered to be the reference when finding routes in networks-on-chip. When the number of vertices is more than 300, the algorithm becomes inefficient, since the diameters, calculated by “Sequent” algorithm, can be ten times higher than the optimal diameters calculated by the Dijkstra algorithm.

Keywords: сеть на кристалле, network-on-chip, routing algorithm, алгоритм маршрутизации, алгоритм Дейкстры, Dijkstra algorithm, three-dimensional circulant, трехмерный циркулянт

Publication based on the results of: Development of a hybrid model for the design and simulation of networks-on-chip (2020)