Проектирование сетей на кристалле с топологией кольцевой циркулянт с тремя образующими: разработка алгоритмов маршрутизации

Информационные технологии. 2019. Т. 25. № 9. С. 522–530.

Romanov A., Ведмидь Е. А., Монахова Э. А.

This paper presents implementation of several dynamic routing algorithms designed for using in networks-on-chip based on circulant topology of type C(N; 1,  s2,  s3)  to search for the shortest routes between nodes. The developed algorithms can be implemented as RTL state machine for choosing the direction of packets in routers. Algorithms were tested on various sets of optimal triple loop circulants and compared in terms of efficiency, speed, and resources held in memory. The relationship between efficiency and the difference between the two generatrices was obtained, and the most effective one was found – the coefficient search algorithm. For all tested circulants, algorithm shows maximum efficiency, but the execution time of this algorithm is significantly higher than its considered counterparts. In addition, the efficiency and speed of the algorithm directly depend on the chosen calculation coefficients. Compared with the classic Dijkstra algorithm, the proposed algorithms do not require calculation of the entire packet path, but determine 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 network-on-chip router.

Keywords: сеть на кристалле, network-on-chip, routing algorithm, алгоритмы маршрутизации, Dijkstra’s algorithm, triple loop circulant, алгоритм Дейкстры, кольцевой циркулянт с тремя образующими

Publication based on the results of: Проектирование сетей на кристалле на основе циркулянтных топологий (2018)