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

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.

Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies.

This work is devoted to the study of application of new topologies in the design of networks-on-chip (NoCs). It is proposed to use two-dimensional optimal circulant topologies for NoC design, and it is developed an optimized routing algorithm with the decreased memory usage. The proposed routing algorithm was compared with Table routing, Clockwise routing, and Adaptive routing algorithms, previously developed for ring circulant topologies, and specialized routing algorithm for multiplicative circulants. The results of synthesis of routers implementing proposed routing algorithms are presented. The cost of ALM and register resources for the implementation of communication subsystems in NoCs with circulant topologies is estimated.

Development of routing algorithms in networks-on-chip based on ring circulant topologies.

This work is devoted to the study of communication subsystem of networks-on-chip (NoCs) development with an emphasis on their topologies. The main characteristics of NoC topologies and the routing problem in NoCs with various topologies are considered. It is proposed to use two-dimensional circulant topologies for NoC design, since they have significantly better characteristics than most common mesh and torus topologies, and, in contrast to many other approaches to improving topologies, have a regular structure. The emphasis is on using ring circulants which although in some cases have somewhat worse characteristics than the optimal circulants, compensate by one-length first generatrix in such graphs that greatly facilitate routing in them. The paper considers three different approaches to routing in NoCs with ring circulant topology: Table routing, Clockwise routing, and Adaptive routing. The algorithms of routing are proposed, the results of synthesis of routers, based on them, are presented, and the cost of chip resources for the implementation of such communication subsystems in NoCs is estimated.