ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 9. Vol. 25. 2019

DOI: 10.17587/it.25.522-530

A. Yu. Romanov, PhD, Associate Professor, e-mail: a.romanov@hse.ru, E. A. Vedmid, Student, e-mail: eavedmid@edu.hse.com, National Research University Higher School of Economics, Moscow, Russian Federation, E. A. Monakhova, PhD, Associate Professor, Senior Researcher, e-mail: emilia@rav.sscc.ru, ICMMG SB RAS, Novosibirsk, Russian Federation

Designing Networks-on-Chip Based on Triple Loop (Circulant) Networks: Routing Algorithm Development

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, s₂, s₃) 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, Dijkstra's algorithm, third loop circulants, routing algorithms

P.522-530

To the contents