Development of a Routing Method for Networks-on-chip Based on Circulant Topologies

The possibility of using circulant topologies as the topology of networks on a crystal is considered. A brief theoretical background on the theory of circulant graphs is proposed. In addition, the work contains necessary explanations about the arrangement of systems and networks on a chip. The development of a routing method in networks on a chip based on circulant graphs was carried out. The mathematical substantiation of the algorithm for choosing the direction of motion of packets in a network on a chip, pseudo-code, is given. The optimal structure of the package is proposed for this algorithm. Implemented the method at the program level using the programming language Python 2.7. To analyze the results obtained, the effectiveness of the proposed method and existing algorithms is compared, for which the explanation of such shortest path search algorithms in the graph as a width search algorithm, the Dijkstra algorithm, and the algorithm A* is also given.