Routing in triple loop circulants: A case of networks-on-chip

作     者：Romanov, Aleksandr Yu Starykh, Vladimir A. 

作者机构：Natl Res Univ Higher Sch Econ 34 Tallinskaya Ulitsa Moscow 123458 Russia 

出 版 物：《HELIYON》 (Heliyon)

年 卷 期：2020年第6卷第7期

页      面：e04427页

核心收录：

主　　题：Electrical engineering Topology Computer architecture Algorithm design Very-large-scale integration Computer-aided engineering Network-on-chip Dijkstra's algorithm Triple loop circulant Routing algorithm 

摘      要：In this paper we propose and analyze various approaches to organizing routing in a triple loop circulant topologies as applied to networks-on-chip: static routing based on universal graph search algorithms, such as Dijkstra s algorithm and a possible implementation using Table routing;algorithms created analytically based on an engineering approach with taking into account the structural features of triple loop circulant graphs (Advanced clockwise, Direction selection);an algorithm created on the basis of a mathematical analysis of graph structure and solving the problem of enumerating coefficients at generators (Coefficients finding algorithm). Efficiency, maximum graph paths, occupied memory resources, and calculation time of the algorithms developed are estimated. Comparison of various variants of the algorithms is made and recommendations on their application for the development of networks-on-chip with triple loop circulant topologies are given. It is shown that Advanced clockwise and Direction selection algorithms guarantee that the packet reaches the destination node, but often in more steps than the shortest path. Nevertheless, they themselves are simpler and require less hardware resources than other algorithms. In turn, Coefficients finding algorithm has great computational complexity, but is optimal and, in comparison with Dijkstra s algorithm, is much simpler for RTL implementation which reduces network-on-chip routers resources cost.