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

Heliyon. 2019. Vol. 5. No. 4. P. 1–23.

Aleksandr Yu. Romanov

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.

Keywords: mesh topology, сеть на кристалле, топология mesh, network-on-chip, torus topology, топология torus, routing algorithm, циркулянтная топология, circulant topology, circulant graph, ring circulant topology

Publication based on the results of: Synthesis of circulant topologies for use in networks-on-chip (2018)