Analytical Routing Algorithm for Networks-on-Chip with the Three-dimensional Circulant Topology

For analytically defined families of three-dimensional circulant networks with a parametric description, an analytical algorithm for finding shortest paths which has a common scheme for all networks of the family based on a given generating function was developed. A comparative analysis of three routing algorithms (analytical Two-terminal routing algorithm, Coefficients search on graph generators, and Dijkstra’s algorithm) for a variety of circulant networks from an analytically defined family was carried out. Estimates of the effectiveness of the considered routing algorithms for use in networks-on-chip were obtained.