Simulation of specialized routing algorithms in networks-on-chip represented by series of circulant topology families

Abstract

This article examines series of families of two-dimensional circulant networks with rectangular L-shapes, optimal in diameter, as network-on-chip topologies with a minimal number of crossings between the links and a bounded length of the maximum link that does not depend on the network size. New network-on-chip routing algorithms, which use the coordinates of three adjacent zeros in the planar graph embedding to calculate the shortest paths, were investigated and simulated. A key advantage of the proposed routing algorithms is that they require minimal input data to calculate the shortest paths. Four routing algorithms were implemented in the Noxim network-on-chip simulator using the optimal graphs of the circulant network families under study: the new analytical algorithm, the traditional Dijkstra algorithm, the routing algorithm with virtual coordinates, and the clockwise routing algorithm. The above algorithms were compared under various traffic profiles across three metrics: average and maximum latencies and network throughput. The simulation results showed that, for all traffic profiles, the new routing algorithms designed for the topologies of circulant networks with rectangular L-shapes outperform other algorithms with similar metrics in terms of memory consumption.